[1a/3][ASan][compiler-rt] API for double ended containers

[AdvenamTacet]

Summary

This revision is a part of a series of patches extending AddressSanitizer C++ container overflow detection capabilities by adding annotations, similar to those existing in std::vector, to std::string and std::deque collections. These changes allow ASan to detect cases when the instrumented program accesses memory which is internally allocated by the collection but is still not in-use (accesses before or after the stored elements for std::deque, or between the size and capacity bounds for std::string).

The motivation for the 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.

This revision adds a new compiler-rt ASan sanitization API function sanitizer_annotate_double_ended_contiguous_container necessary to sanitize/annotate double ended contiguous containers. Note that that function annotates a single contiguous memory buffer (for example the std::deque's internal chunk). Such containers have the beginning of allocated memory block, beginning of the container in-use data, end of the container's in-use data and the end of the allocated memory block.
This also adds a new API function to verify if a double ended contiguous container is correctly annotated (__sanitizer_verify_double_ended_contiguous_container).

Since we do not modify the ASan's shadow memory encoding values, the capability of sanitizing/annotating a prefix of the internal contiguous memory buffer is limited – up to SHADOW_GRANULARITY-1 bytes may not be poisoned before the container's in-use data. This can cause false negatives (situations when ASan will not detect memory corruption in those areas).

On the other hand, API function interfaces are designed to work even if this caveat would not exist. Therefore implementations using those functions will poison every byte correctly, if only ASan
(and compiler-rt) is extended to support it. In other words, if ASan was modified to support annotating/poisoning of objects lying on addresses unaligned to SHADOW_GRANULARITY (so e.g. prefixes of those blocks), which would require changing its shadow memory encoding, this would not require any changes in the libcxx std::string/deque code which is added in further commits of this patch series.

If you have any questions, please email:
[e-mail]
[e-mail]

[philnik]

Just so you know, this will most likely interfere with my current work on std::deque and std::__split_buffer. See D132081 and D132028.

[AdvenamTacet]

Fixing comments.

[vitalybuka]

can you please add a test here compiler-rt/test/asan/TestCases/contiguous_container.cpp ?

compiler-rt/include/sanitizer/common_interface_defs.h

162–165

[vitalybuka]

compiler-rt/include/sanitizer/common_interface_defs.h

186–190

maybe just a single function?

void __sanitizer_annotate_de_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);

188

inconsistency
here order "new, old"
and below is "old, new" (I would prefer if we stick with existing this one)

214

Would be nice to find something better than _de_ in the name, double_ended ?

compiler-rt/lib/asan/asan_poisoning.cpp

400

maybe
beg_p -> storage_beg_p
end_p -> storage_end_p

421

this check and blow is hard to read, can we improve this
maybe

(beg <= con_end_p && con_end_p <= end) &&
(beg <= new_con_beg && new_con_beg <= con_end_p) &&
(beg <= old_con_beg_p && old_con_beg_p <= con_end_p)

433–434

instead of Min/max, probably better to simplify and sink them into corresponding branches below.

472

IsAligned

500

same with if restructuring.

[vitalybuka]

compiler-rt/lib/asan/asan_poisoning.cpp

357–362

to my taste this is CHECK() case, but no need to change in this patch
can simplify this in later (on in before) patch

[AdvenamTacet]

Changes based on the review.
Next update will contain:

• test in compiler-rt/test/asan/TestCases/contiguous_container.cpp
• argument order change

[AdvenamTacet]

Formatting.

[AdvenamTacet]

compiler-rt/include/sanitizer/common_interface_defs.h

186–190

That was my first idea, but after some thinking I decided against it.

• I see almost zero situations when one may want to change the beginning and the end at the same time, so there is no point.
• It may be very small, but it may have a bad impact on performance.
• It's less important, but it would be harder to remember the correct order and some mistakes may not be noticed instantly.

// Intended:
__sanitizer_annotate_de_contiguous_container(0x8, 0x1000, 0x10, 0x11, 0x99, 0x100);
// Mistake:
__sanitizer_annotate_de_contiguous_container(0x8, 0x1000, 0x10, 0x99, 0x11, 0x100);

I feel that it just complicates usage of those functions and brings no benefits, it's easier to just see _front and _back instead of checking what two arguments are the same.
One less function in API seems nice, but I suggest two.

Do you know any examples when changing the beginning and the end at the same time may be helpful?
Do you see any benefits, which I don't see?

188

I understand why suggested order may be confusing, so I will change it, but it is consistent with poisoning. (If we move beginning forward, we have to poison, if we move end forward, we have to unpoison). But I understand why having new/old in the same order also makes sense.

Maybe the best order is

void __sanitizer_annotate_de_contiguous_container_front(
                                                        const void *storage_beg,
                                                        const void *storage_end,
                                                        const void *old_con_beg,
                                                        const void *con_end,
                                                        const void *new_con_beg);

and in __sanitizer_annotate_de_contiguous_container_back:

const void *storage_beg,
const void *storage_end, 
const void *con_beg,
const void *old_con_end,
const void *new_con_end);

Instead of con_beg at the end?

What do you think?

Btw. I see additional _p in names, I will remove it with next update.

214

I didn't want to create very long names, but it's probably a good idea. I changed it.

compiler-rt/lib/asan/asan_poisoning.cpp

357–362

That function is not added by me, therefore I suggest leaving it for another patch. For consistency, I suggest leaving similar code in new functions and possibly changing them in a future patch.

But, I'm not sure how it's possible to use CHECK here, without decreasing feedback for users.

400

I changed it. I also changed _con_ -> _container_.

[AdvenamTacet]

Order of arguments changed, new order is:

• storage_beg
• storage_end
• old_container_beg
• old_container_end
• new_value (based on function beg/end)

[ldionne]

Thanks a lot for the patch series. I've been independently considering changes to our so-called "debug mode" recently where std::vector & friends would have special iterators that keep track of the size of the container they point into, and can trap when dereferenced at an out-of-bounds address. This could be achieved by storing the bounds of the vector's allocation at the beginning of the allocation itself, and then those bounds-aware iterators would basically have a pointer within the allocation, and a pointer to the header containing that metadata. This would have the benefit that iterators have access to the bounds information as long as they are not invalidated by reallocating the vector. But the vector object itself (not the contiguous memory + header it points to) could move around without impacting the iterators.

Okay, so this is mostly unrelated to this patch because it concerns only contiguous containers so far. However, since this patch expands the intersection between the library and AddressSanitizer, perhaps it is worth discussing the pros and cons of each approach. In particular, the typical slowdown for using ASAN is documented as roughly 2x. The goal I was aiming for with the design I drafted above would be to have a smaller performance impact than ASAN, with the goal of hopefully being able to even turn it on in production in some scenarios.

Having obviously done a lot of work and thinking in the intersection of the library and sanitizers, do you have thoughts about this?

[AdvenamTacet]

Hey @ldionne, thank you for your interest in my patches. I think your proposition is fundamentally different from ASan.

• ASan is not designed to work on production and as far as I know, using it may increase attack surface.
• With ASan, almost every memory access is instrumented, while with "smart iterators" only accesses with those iterators are checked.

My idea to evaluate if there is a point in implementing "smart iterators" is estimating the percentage of container overflows with iterators and raw pointers.
It may be possible with the oss-fuzz project tracker (https://bugs.chromium.org/p/oss-fuzz/issues/list?q=container%20overflow&can=1).
Also, [almost] every memory bug detected by "smart iterator" should be detected by ASan as well (if the container is annotated).
But "smart iterators" may work faster and in more situations.

However, I did not think about that kind of patch and therefore I do not have an opinion.

the typical slowdown for using ASAN is documented as roughly 2x

As you mentioned performance, I want to point out that my changes shouldn't noticeably change it. My code creates additional overhead only for functions modifying deques/strings. Every memory access to those containers is instrumented in the same way with and without my changes, rest of the program is not modified.

[AdvenamTacet]

Update to API: only one new function added instead of two.

Now there is:
void __sanitizer_annotate_double_ended_contiguous_container(

const void *storage_beg_p, const void *storage_end_p,
const void *old_container_beg_p, const void *old_container_end_p,
const void *new_container_beg_p, const void *new_container_end_p)

A new test (for double ended containers) is added to
compiler-rt/test/asan/TestCases/contiguous_container.cpp

[AdvenamTacet]

compiler-rt/include/sanitizer/common_interface_defs.h

186–190

I implemented a single function, order of arguments is same as suggested by you.
At the moment, it does use functions _front and _back as auxiliary functions, but API is extended only by one function. Also, Error classes / printing functions are updated to support new design.

I hope it's ok and potential improvements may be done in future patches. The API is extended only by one function.

[vitalybuka]

compiler-rt/include/sanitizer/common_interface_defs.h

229

looks too long, please clang format

230

new line

compiler-rt/lib/asan/asan_errors.h

346

-_front ?

libcxx/include/__config

883 ↗

(On Diff #461436)

this should be in a separate patch, probably D132092

however we need to support the case when we build libcxx with older clang/compiler-rt when this function is not available
maybe you land D132090 and after some time, if it's not reverted
you land libcxx patch with _LIBCPP_CLANG_VER check?

how about gcc? it uses the same runtime

[vitalybuka]

libcxx/include/__config

883 ↗

(On Diff #461436)

Note: I assume that compiler-rt/clang version mismatch is possible, but is not required to support. I assume that libcxx clang mismatch is required to be supported.

[AdvenamTacet]

libcxx/include/__config

883 ↗

(On Diff #461436)

this should be in a separate patch, probably D132092

Right, I'm going to move it to D132092.

however we need to support the case when we build libcxx with older clang/compiler-rt

We do use checks for clang version there (_LIBCPP_CLANG_VER >= 16000) and I am going to guard that as well. It does work with old versions of llvm.

how about gcc? it uses the same runtime

I do not know about using libc++ with gcc, I think we can wait with supporting annotations for deque there. If I understand correctly, there should be no problems generated by that change in that scenario, just no annotations for deque.

If you ask about libstdc++, annotations for that implementation have to be created. We do have working PoC, but we are focused on upstreaming those changes for llvm at the moment. I'm not sure if we are going to work further on libstdc++, but we may consider making them public "as is".

maybe you land D132090 and after some time, if it's not reverted

Landing D132090 and D132522 (I'm about to make an update there) before libcxx patches is my plan, but I want to land D132092 and D132769 soon after to avoid further changes in std::deque or std::basic_string implementations.

[AdvenamTacet]

Clang format and moving libcxx part.

[AdvenamTacet]

Fixing naming and formatting.

[AdvenamTacet]

Hey, I believe I fixed all issues from the code review. Is there anything else to change? What else should I do before upstreaming? I would be very happy to close it, to fully focus on revisions depending on it.

[vitalybuka]

looks good in general, I will make another pass for details by tomorrow

compiler-rt/test/asan/TestCases/contiguous_container.cpp

50

we don't need version check as this code goes together with asan_poisoning.cpp and should not depend on compiler

56

I don't see TestDoubleEndedContainer is called

[AdvenamTacet]

Call to TestDoubleEndedContainer is now made.

Unnecessary check removed.

Annotations are fixed to pass the test and __sanitizer_verify_double_ended_contiguous_container
is modified to work with empty containers when beg != con_beg.

Locally, the test is failing on TestThrow, part not modified by that patch.

a.out: contiguous_container.cpp:112: void TestThrow(): Assertion `!__asan_address_is_poisoned(x + 14)' failed.
Aborted

Code there:

void TestThrow() {
  char x[32];
  __sanitizer_annotate_contiguous_container(x, x + 32, x + 32, x + 14);
  assert(!__asan_address_is_poisoned(x + 13));
  assert(__asan_address_is_poisoned(x + 14));
  ThrowAndCatch();
  assert(!__asan_address_is_poisoned(x + 13));
  assert(!__asan_address_is_poisoned(x + 14)); // Line 112

I'm going to look at it closer, but TestDoubleEndedContainer passed, therefore I believe
fixed implementation is working in every case (and not only for deque).

[vitalybuka]

Please confirm that you have no committer access.
If so after the next your update, I will cleanup nits, if any, accept and land the patch.

Please make sure that check-sanitizer and check-asan pass.

compiler-rt/lib/asan/asan_poisoning.cpp

399

both non interface "static void"

401

we don't use it old_container_end_p, new_container_end_p here,
only for reporting

lets's make non-interface functions all uptr params, remove unneded ones and move the following block into interface function

// Unchecked argument requirements:
// During unpoisoning memory of empty container (before first element is
// added):
// - old_container_end_p == old_container_beg_p
// During poisoning after last element was removed:
// - new_container_beg_p == container_end_p
if (!flags()->detect_container_overflow)
  return;
VPrintf(2, "de_contiguous_container (front): %p %p %p %p %p\n", storage_beg_p,
        storage_end_p, new_container_beg_p, old_container_beg_p,
        old_container_end_p);
uptr storage_beg = reinterpret_cast<uptr>(storage_beg_p);
uptr storage_end = reinterpret_cast<uptr>(storage_end_p);
uptr old_container_beg =
    reinterpret_cast<uptr>(old_container_beg_p);  // old container beginning
uptr old_container_end =
    reinterpret_cast<uptr>(old_container_end_p);  // container ending
uptr new_container_beg =
    reinterpret_cast<uptr>(new_container_beg_p);  // new container beginning
uptr new_container_end =
    reinterpret_cast<uptr>(new_container_end_p);  // new container ending

uptr granularity = ASAN_SHADOW_GRANULARITY;
if (!((storage_beg <= new_container_beg &&
       new_container_beg <= storage_end) &&
      (storage_beg <= old_container_beg &&
       old_container_beg <= storage_end) &&
      (old_container_beg <= old_container_end &&
       old_container_end <= storage_end) &&
      IsAligned(storage_beg, granularity) &&
      old_container_end_p == new_container_end_p)) {
  GET_STACK_TRACE_FATAL_HERE;
  ReportBadParamsToAnnotateDoubleEndedContiguousContainer(
      storage_beg, storage_end, old_container_beg, old_container_end,
      new_container_beg, new_container_end, &stack);
}
CHECK_LE(storage_end - storage_beg,
         FIRST_32_SECOND_64(1UL << 30, 1ULL << 40));  // Sanity check.

463

I assume after removing unneeded vars, we will have only old_container_end -> container_end

481

if either body or condition are multi-line, please wrap the body with {}

552

AddrIsAlignedByGranularity ,everywhere

562

new line after the function

566

we don't support !IsAligned(beg)
but please comment that we don't support !IsAligned(end) which shares the tail with something else

I assume we are not looking for intra object deque?

[vitalybuka]

I guess not strictly insist, but maybe cleanup descriptions a little-bit, here and other reviews.
Usually LLVM commits descriptions are high level overview of what is done, and why it's done.

E.g.

Not needed in the git commit?

Trail of Bits developed this as part of a research project where
we tried to find bugs using the oss-fuzz
(using llvm-14 with our modifications) harnesses.
Now, we want to upstream the llvm-15 port of this work.

Naming does not match, in description please keep only interface function:

This commit adds new compiler-rt ASan sanitization API functions:
sanitizer_annotate_de_contiguous_container_front and
sanitizer_annotate_de_contiguous_container_back, necessary to
sanitize/annotate double ended contiguous containers.

Not needed in the git commit, as known and unchanged?

SHADOW_GRANULARITY is usually 8 – that value describes how
many bytes has a block described by a single value in the
AddressSanitizer's shadow memory and is set during llvm/clang
compilation.

Not needed assuming we have a link to review with the "review stack"?

Structure of our patches:
[1a/3][ASan][compiler-rt] API for double ended containers
[1b/3][ASan][compiler-rt] API for annotating objects memory
[2a/3][ASan][libcxx] std::deque annotations
[2b/3][ASan][libcxx] std::basic_string annotations
[3/3][ASan] integration test for std::deque and std::basic_string annotations

Quoted Text

[AdvenamTacet]

Fixes:

• code style (suggested changes)
• removes additional (non-interface) functions
• AddrIsAlignedByGranularity used
• Comment descriptions updated

I do not have commiter acces, I didn't contribute before.
If there is anything else I should do, please, let me know.

[vitalybuka]

rebase, renames, comments

[vitalybuka]

Something is broken in this implementation see D138459
Also it does not support unaligned container.

I have a draft of more generic implementation sanitizer_annotate_double_ended_contiguous_container and sanitizer_annotate_contiguous_container, so I land the patch as-is and switch to the new implementaion later.

[vitalybuka]

In D132090#3942187, @vitalybuka wrote:

Something is broken in this implementation see D138459

Actually the D138459 is broken and this patch is correct.
But I will simplify, add unaligned case support and improve the test in D138773

compiler-rt/include/sanitizer/common_interface_defs.h

 /// \param end End of memory region.
 /// \param old_mid Old middle of memory region.
 /// \param new_mid New middle of memory region.
 void __sanitizer_annotate_contiguous_container(const void *beg,
                                                const void *end,
                                                const void *old_mid,
                                                const void *new_mid);
 
+/// Similar to <c>__sanitizer_annotate_contiguous_container</c>.
+///
+/// Annotates the current state of a contiguous container memory,
+/// such as <c>std::deque</c>'s single chunk, when the beginning is moved.
+///
+/// A contiguous chunk is a chunk that keeps all of its elements
+/// in a contiguous region of memory. The container owns the region of memory
+/// <c>[storage_beg, storage_end)</c>; the memory <c>[container_beg,
+/// container_end)</c> is used to store the current elements, and the memory
+/// <c>[storage_beg, container_beg), [container_end, storage_end)</c> is
+/// reserved for future elements (<c>storage_beg <= container_beg <=
+/// container_end <= storage_end</c>). For example, in <c> std::deque </c>:
+/// - chunk with a frist deques element will have container_beg equal to address
+///  of the first element.
+/// - in every next chunk with elements, true is  <c> container_beg ==
+/// storage_beg </c>.
+///
+/// Argument requirements:
+/// During unpoisoning memory of empty container (before first element is
+/// added):
+/// - container_end_p == old_container_beg_p
+/// During poisoning after last element was removed:
+/// - new_container_beg_p == container_end_p
+/// \param storage_beg Beginning of memory region (container may have many
+/// regions).
+/// \param storage_end End of memory region.
+/// \param old_container_beg Old beginning of used
+/// region.
+/// \param old_container_end End of used region.
+/// \param new_container_beg New beginning of used region.
+/// \param new_container_end New end of used region.
+/// Should be satisfied: new_container_end == container_end
+void __sanitizer_annotate_double_ended_contiguous_container_front(
+    const void *storage_beg, const void *storage_end,
+    const void *old_container_beg, const void *old_container_end,
+    const void *new_container_beg, const void *new_container_end);
+
+/// Similar to
+/// <c>__sanitizer_annotate_double_ended_contiguous_container_front</c>.
+///
+/// Annotates the current state of a contiguous container memory,
+/// such as <c>std::deque</c>'s single chunk, when the end is moved.
+///
+/// A contiguous chunk is a chunk that keeps all of its elements
+/// in a contiguous region of memory. The container owns the region of memory
+/// <c>[storage_beg, storage_end)</c>; the memory <c>[container_beg,
+/// container_end)</c> is used to store the current elements, and the memory
+/// <c>[storage_beg, container_beg), [container_end, storage_end)</c> is
+/// reserved for future elements (<c>storage_beg <= container_beg <=
+/// container_end <= storage_end</c>).
+///
+/// Argument requirements:
+/// During unpoisoning memory of empty container (before first element is
+/// added):
+/// - container_beg_p == old_container_end_p
+/// During poisoning after last element was removed (empty container case):
+/// - new_container_end_p == container_beg_p
+/// \param storage_beg Beginning of memory region (container may have many
+/// regions).
+/// \param storage_end End of memory region.
+/// \param old_container_beg Old beginning of used
+/// region.
+/// \param old_container_end End of used region.
+/// \param new_container_beg New beginning of used region.
+/// \param new_container_end New end of used region.
+/// Should be satisfied: new_container_beg == container_beg
+void __sanitizer_annotate_double_ended_contiguous_container_back(
+    const void *storage_beg, const void *storage_end,
+    const void *old_container_beg, const void *old_container_end,
+    const void *new_container_beg, const void *new_container_end);
+
+/// Similar to <c>__sanitizer_annotate_contiguous_container</c>.
+///
+/// Annotates the current state of a contiguous container memory,
+/// such as <c>std::deque</c>'s single chunk, when the boundries are moved.
+///
+/// A contiguous chunk is a chunk that keeps all of its elements
+/// in a contiguous region of memory. The container owns the region of memory
+/// <c>[storage_beg, storage_end)</c>; the memory <c>[container_beg,
+/// container_end)</c> is used to store the current elements, and the memory
+/// <c>[storage_beg, container_beg), [container_end, storage_end)</c> is
+/// reserved for future elements (<c>storage_beg <= container_beg <=
+/// container_end <= storage_end</c>). For example, in <c> std::deque </c>:
+/// - chunk with a frist deques element will have container_beg equal to address
+///  of the first element.
+/// - in every next chunk with elements, true is  <c> container_beg ==
+/// storage_beg </c>.
+///
+/// Argument requirements:
+/// During unpoisoning memory of empty container (before first element is
+/// added):
+/// - old_container_beg_p == old_container_end_p
+/// During poisoning after last element was removed:
+/// - new_container_beg_p == new_container_end_p
+/// \param storage_beg Beginning of memory region (container may have many
+/// regions).
+/// \param storage_end End of memory region.
+/// \param old_container_beg Old beginning of used
+/// region.
+/// \param old_container_end End of used region.
+/// \param new_container_beg New beginning of used region.
+/// \param new_container_end New end of used region.
+void __sanitizer_annotate_double_ended_contiguous_container(
+    const void *storage_beg, const void *storage_end,
+    const void *old_container_beg, const void *old_container_end,
+    const void *new_container_beg, const void *new_container_end);
+
 /// Returns true if the contiguous container <c>[beg, end)</c> is properly
 /// poisoned.
 ///
 /// Proper poisoning could occur, for example, with
 /// <c>__sanitizer_annotate_contiguous_container</c>), that is, if
 /// <c>[beg, mid)</c> is addressable and <c>[mid, end)</c> is unaddressable.
 /// Full verification requires O (<c>end - beg</c>) time; this function tries
 /// to avoid such complexity by touching only parts of the container around
 /// <c><i>beg</i></c>, <c><i>mid</i></c>, and <c><i>end</i></c>.
 ///
 /// \param beg Beginning of memory region.
 /// \param mid Middle of memory region.
 /// \param end Old end of memory region.
 ///
 /// \returns True if the contiguous container <c>[beg, end)</c> is properly
 ///  poisoned.
 int __sanitizer_verify_contiguous_container(const void *beg, const void *mid,
                                             const void *end);
 
+/// Returns true if the double ended contiguous
+/// container <c>[storage_beg, storage_end)</c> is properly poisoned.
+///
+/// Proper poisoning could occur, for example, with
+/// <c>__sanitizer_annotate_double_ended_contiguous_container</c>), that is, if
+/// <c>[storage_beg, container_beg)</c> is not addressable,  <c>[container_beg,
+/// container_end)</c> is addressable and <c>[container_end, end)</c> is
+/// unaddressable. Full verification requires O (<c>storage_end -
+/// storage_beg</c>) time; this function tries to avoid such complexity by
+/// touching only parts of the container around <c><i>storage_beg</i></c>,
+/// <c><i>container_beg</i></c>, <c><i>container_end</i></c>, and
+/// <c><i>storage_end</i></c>.
+///
+/// \param storage_beg Beginning of memory region (container may have many
+/// regions). \param container_beg Beginning of used region. \param
+/// container_end End of used region. \param storage_end End of memory region.
+///
+/// \returns True if the double-ended contiguous container <c>[storage_beg,
+/// container_beg, container_end, end)</c> is properly
+///  poisoned - only [container_beg; container_end) is addressable.
+int __sanitizer_verify_double_ended_contiguous_container(
+    const void *storage_beg, const void *container_beg,
+    const void *container_end, const void *storage_end);
+
 /// Similar to <c>__sanitizer_verify_contiguous_container()</c> but also
 /// returns the address of the first improperly poisoned byte.
 ///
 /// Returns NULL if the area is poisoned properly.
 ///
 /// \param beg Beginning of memory region.
 /// \param mid Middle of memory region.
 /// \param end Old end of memory region.

compiler-rt/lib/asan/asan_errors.h

ErrorBadParamsToAnnotateContiguousContainer(u32 tid,
         stack(stack_),
         beg(beg_),
         end(end_),
         old_mid(old_mid_),
         new_mid(new_mid_) {}
   void Print();
 };
 
+struct ErrorBadParamsToAnnotateDoubleEndedContiguousContainer : ErrorBase {
+  const BufferedStackTrace *stack;
+  uptr storage_beg, storage_end, old_container_beg, old_container_end,
+      new_container_beg, new_container_end;
+
+  ErrorBadParamsToAnnotateDoubleEndedContiguousContainer() = default;  // (*)
+  ErrorBadParamsToAnnotateDoubleEndedContiguousContainer(
+      u32 tid, BufferedStackTrace *stack_, uptr storage_beg_, uptr storage_end_,
+      uptr old_container_beg_, uptr old_container_end_, uptr new_container_beg_,
+      uptr new_container_end_)
+      : ErrorBase(tid, 10,
+                  "bad-__sanitizer_annotate_double_ended_contiguous_container"),
+        stack(stack_),
+        storage_beg(storage_beg_),
+        storage_end(storage_end_),
+        old_container_beg(old_container_beg_),
+        old_container_end(old_container_end_),
+        new_container_beg(new_container_beg_),
+        new_container_end(new_container_end_) {}
+  void Print();
+};
+
 struct ErrorODRViolation : ErrorBase {
   __asan_global global1, global2;
   u32 stack_id1, stack_id2;
 
   ErrorODRViolation() = default;  // (*)
   ErrorODRViolation(u32 tid, const __asan_global *g1, u32 stack_id1_,
                     const __asan_global *g2, u32 stack_id2_)
       : ErrorBase(tid, 10, "odr-violation"),
#define ASAN_FOR_EACH_ERROR_KIND(macro)         \
   macro(InvalidAlignedAllocAlignment)           \
   macro(InvalidPosixMemalignAlignment)          \
   macro(AllocationSizeTooBig)                   \
   macro(RssLimitExceeded)                       \
   macro(OutOfMemory)                            \
   macro(StringFunctionMemoryRangesOverlap)      \
   macro(StringFunctionSizeOverflow)             \
   macro(BadParamsToAnnotateContiguousContainer) \
+  macro(BadParamsToAnnotateDoubleEndedContiguousContainer) \
   macro(ODRViolation)                           \
   macro(InvalidPointerPair)                     \
   macro(Generic)
 // clang-format on
 
 #define ASAN_DEFINE_ERROR_KIND(name) kErrorKind##name,
 #define ASAN_ERROR_DESCRIPTION_MEMBER(name) Error##name name;
 #define ASAN_ERROR_DESCRIPTION_CONSTRUCTOR(name)                    \

compiler-rt/lib/asan/asan_errors.cpp

Report(
       (void *)beg, (void *)end, (void *)old_mid, (void *)new_mid);
   uptr granularity = ASAN_SHADOW_GRANULARITY;
   if (!IsAligned(beg, granularity))
     Report("ERROR: beg is not aligned by %zu\n", granularity);
   stack->Print();
   ReportErrorSummary(scariness.GetDescription(), stack);
 }
 
+void ErrorBadParamsToAnnotateDoubleEndedContiguousContainer::Print() {
+  Report(
+      "ERROR: AddressSanitizer: bad parameters to "
+      "__sanitizer_annotate_double_ended_contiguous_container:\n"
+      "      storage_beg        : %p\n"
+      "      storage_end        : %p\n"
+      "      old_container_beg  : %p\n"
+      "      old_container_end  : %p\n"
+      "      new_container_beg  : %p\n"
+      "      new_container_end  : %p\n",
+      (void *)storage_beg, (void *)storage_end, (void *)old_container_beg,
+      (void *)old_container_end, (void *)new_container_beg,
+      (void *)new_container_end);
+  uptr granularity = ASAN_SHADOW_GRANULARITY;
+  if (!IsAligned(storage_beg, granularity))
+    Report("ERROR: storage_beg is not aligned by %zu\n", granularity);
+  stack->Print();
+  ReportErrorSummary(scariness.GetDescription(), stack);
+}
+
 void ErrorODRViolation::Print() {
   Decorator d;
   Printf("%s", d.Error());
   Report("ERROR: AddressSanitizer: %s (%p):\n", scariness.GetDescription(),
          (void *)global1.beg);
   Printf("%s", d.Default());
   InternalScopedString g1_loc;
   InternalScopedString g2_loc;

compiler-rt/lib/asan/asan_poisoning.cpp

void __sanitizer_annotate_contiguous_container(const void *beg_p,
   if (!flags()->detect_container_overflow) return;
   VPrintf(2, "contiguous_container: %p %p %p %p\n", beg_p, end_p, old_mid_p,
           new_mid_p);
   uptr beg = reinterpret_cast<uptr>(beg_p);
   uptr end = reinterpret_cast<uptr>(end_p);
   uptr old_mid = reinterpret_cast<uptr>(old_mid_p);
   uptr new_mid = reinterpret_cast<uptr>(new_mid_p);
   uptr granularity = ASAN_SHADOW_GRANULARITY;
   if (!(beg <= old_mid && beg <= new_mid && old_mid <= end && new_mid <= end &&
         IsAligned(beg, granularity))) {
     GET_STACK_TRACE_FATAL_HERE;
     ReportBadParamsToAnnotateContiguousContainer(beg, end, old_mid, new_mid,
                                                  &stack);
   }
   CHECK_LE(end - beg,
            FIRST_32_SECOND_64(1UL << 30, 1ULL << 40)); // Sanity check.
 
   uptr a = RoundDownTo(Min(old_mid, new_mid), granularity);
   uptr c = RoundUpTo(Max(old_mid, new_mid), granularity);
   uptr d1 = RoundDownTo(old_mid, granularity);
   // uptr d2 = RoundUpTo(old_mid, granularity);
   // Currently we should be in this state:
void __sanitizer_annotate_contiguous_container(const void *beg_p,
   PoisonShadow(a, b1 - a, 0);
   PoisonShadow(b2, c - b2, kAsanContiguousContainerOOBMagic);
   if (b1 != b2) {
     CHECK_EQ(b2 - b1, granularity);
     *(u8*)MemToShadow(b1) = static_cast<u8>(new_mid - b1);
   }
 }
 
+// Annotates front for a double ended contiguous container like std::deque's
+// chunk. It allows detecting buggy accesses to allocated but not used begining
+// or end items of such a container
+void __sanitizer_annotate_double_ended_contiguous_container_front(
+    const void *storage_beg_p, const void *storage_end_p,
+    const void *old_container_beg_p, const void *old_container_end_p,
+    const void *new_container_beg_p, const void *new_container_end_p) {
+  // Unchecked argument requirements:
+  // During unpoisoning memory of empty container (before first element is
+  // added):
+  // - old_container_end_p == old_container_beg_p
+  // During poisoning after last element was removed:
+  // - new_container_beg_p == container_end_p
+  if (!flags()->detect_container_overflow)
+    return;
+  VPrintf(2, "de_contiguous_container (front): %p %p %p %p %p\n", storage_beg_p,
+          storage_end_p, new_container_beg_p, old_container_beg_p,
+          old_container_end_p);
+  uptr storage_beg = reinterpret_cast<uptr>(storage_beg_p);
+  uptr storage_end = reinterpret_cast<uptr>(storage_end_p);
+  uptr old_container_beg =
+      reinterpret_cast<uptr>(old_container_beg_p);  // old container beginning
+  uptr old_container_end =
+      reinterpret_cast<uptr>(old_container_end_p);  // container ending
+  uptr new_container_beg =
+      reinterpret_cast<uptr>(new_container_beg_p);  // new container beginning
+  uptr new_container_end =
+      reinterpret_cast<uptr>(new_container_end_p);  // new container ending
+
+  uptr granularity = ASAN_SHADOW_GRANULARITY;
+  CHECK_LE(storage_end - storage_beg,
+           FIRST_32_SECOND_64(1UL << 30, 1ULL << 40));  // Sanity check.
+
+  // There are two situations: we are poisoning or unpoisoning.
+  // WARNING: at the moment we do not poison prefixes of blocks described by one
+  // byte in shadow memory, so we have to unpoison prefixes of blocks with
+  // content. Up to 7 bytes not-in-use may not be poisoned.
+
+  if (new_container_beg < old_container_beg) {  // We are unpoisoning
+    uptr a = RoundDownTo(new_container_beg, granularity);
+    uptr c = RoundDownTo(old_container_beg, granularity);
+    // State at the moment is:
+    // [storage_beg, a] is poisoned and should remain like that.
+    // [a, c] is poisoned as well (may be empty if new_container_beg and
+    // old_container_beg are in the same block) if container is not empty, first
+    // element starts between [c, c+granularity]
+    //   because we do not poison prefixes, memory [c, container_end] is not
+    //   poisoned and we do not have to touch it.
+    // if container is empty, we have to unpoison memory for elements after c,
+    // so [c, container_end]
+    PoisonShadow(a, c - a, 0);
+    if (old_container_beg == old_container_end &&
+        !IsAligned(old_container_beg,
+                   granularity))  // is empty && ends in the middle of a block
+      *(u8 *)MemToShadow(c) = static_cast<u8>(old_container_end - c);
+
+    // else: we cannot poison prefix of a block with elements or there is
+    // nothing to poison.
+  } else {  // we are poisoning as beginning moved further in memory
+    uptr a = RoundDownTo(old_container_beg, granularity);
+    uptr c = RoundDownTo(new_container_beg, granularity);
+    // State at the moment is:
+    // [storage_beg, a] is poisoned and should remain like that.
+    // [a, c] is not poisoned (may be empty if new_container_beg and
+    // old_container_beg are in the same block) [c, container_end] is not
+    // poisoned If there are remaining elements in the container:
+    //   We have to poison [a, c], but because we do not poison prefixes, we
+    //   cannot poison memory after c (even that there are not elements of the
+    //   container). Up to granularity-1 unused bytes will not be poisoned.
+    // Otherwise:
+    //   We have to poison the last byte as well.
+    PoisonShadow(a, c - a, kAsanContiguousContainerOOBMagic);
+    if (new_container_beg == old_container_end &&
+        !IsAligned(new_container_beg,
+                   granularity))  // is empty && ends in the middle of a block
+      *(u8 *)MemToShadow(c) = static_cast<u8>(kAsanContiguousContainerOOBMagic);
+  }
+}
+
+// Annotates back for a double ended contiguous container like std::deque's
+// chunk. It allows detecting buggy accesses to allocated but not used begining
+// or end items of such a container
+void __sanitizer_annotate_double_ended_contiguous_container_back(
+    const void *storage_beg_p, const void *storage_end_p,
+    const void *old_container_beg_p, const void *old_container_end_p,
+    const void *new_container_beg_p, const void *new_container_end_p) {
+  // Unchecked argument requirements:
+  // During unpoisoning memory of empty container (before first element is
+  // added):
+  // - container_beg_p == old_container_end_p
+  // During poisoning after last element was removed (empty container case):
+  // - new_container_end_p == container_beg_p
+  if (!flags()->detect_container_overflow)
+    return;
+  VPrintf(2, "contiguous_container: %p %p %p %p %p\n", storage_beg_p,
+          storage_end_p, old_container_end_p, new_container_end_p,
+          old_container_beg_p);
+  uptr storage_beg = reinterpret_cast<uptr>(storage_beg_p);
+  uptr storage_end = reinterpret_cast<uptr>(storage_end_p);
+  uptr old_container_beg = reinterpret_cast<uptr>(old_container_beg_p);
+  uptr old_container_end = reinterpret_cast<uptr>(old_container_end_p);
+  uptr new_container_beg = reinterpret_cast<uptr>(new_container_beg_p);
+  uptr new_container_end = reinterpret_cast<uptr>(new_container_end_p);
+
+  uptr granularity = ASAN_SHADOW_GRANULARITY;
+
+  CHECK_LE(storage_end - storage_beg,
+           FIRST_32_SECOND_64(1UL << 30, 1ULL << 40));  // Sanity check.
+
+  if (old_container_end < new_container_end) {  // We are unpoisoning memory
+    uptr a = RoundDownTo(old_container_end, granularity);
+    uptr c = RoundDownTo(new_container_end, granularity);
+    // State at the moment is:
+    // if container_beg < a : [container_beg, a] is correct and we will not be
+    // changing it. else [a, container_beg] cannot be poisoned, so we do not
+    // have to think about it. we have to makr as unpoisoned [a, c]. [c, end] is
+    // correctly poisoned.
+    PoisonShadow(a, c - a, 0);
+    if (!IsAligned(new_container_end,
+                   granularity))  // ends in the middle of a block
+      *(u8 *)MemToShadow(c) = static_cast<u8>(new_container_end - c);
+  } else {  // We are poisoning memory
+    uptr a = RoundDownTo(new_container_end, granularity);
+    // State at the moment is:
+    // [storage_beg, a] is correctly addressable
+    // if container is empty after the removal, then a < container_beg and we
+    // will have to poison memory which is adressable only because we are not
+    // poisoning prefixes.
+    uptr a2 = RoundUpTo(new_container_end, granularity);
+    uptr c2 = RoundUpTo(old_container_end, granularity);
+    PoisonShadow(a2, c2 - a2, kAsanContiguousContainerOOBMagic);
+    if (!IsAligned(new_container_end,
+                   granularity)) {  // Starts in the middle of the block
+      if (new_container_end == old_container_beg)  // empty
+        *(u8 *)MemToShadow(a) = kAsanContiguousContainerOOBMagic;
+      else  // not empty
+        *(u8 *)MemToShadow(a) = static_cast<u8>(new_container_end - a);
+    }
+  }
+}
+// Annotates a double ended contiguous memory area like std::deque's chunk.
+void __sanitizer_annotate_double_ended_contiguous_container(
+    const void *storage_beg_p, const void *storage_end_p,
+    const void *old_container_beg_p, const void *old_container_end_p,
+    const void *new_container_beg_p, const void *new_container_end_p) {
+  uptr storage_beg = reinterpret_cast<uptr>(storage_beg_p);
+  uptr storage_end = reinterpret_cast<uptr>(storage_end_p);
+  uptr old_container_beg =
+      reinterpret_cast<uptr>(old_container_beg_p);  // old container beginning
+  uptr old_container_end =
+      reinterpret_cast<uptr>(old_container_end_p);  // container ending
+  uptr new_container_beg =
+      reinterpret_cast<uptr>(new_container_beg_p);  // new container beginning
+  uptr new_container_end =
+      reinterpret_cast<uptr>(new_container_end_p);  // new container ending
+
+  uptr granularity = ASAN_SHADOW_GRANULARITY;
+
+  if (!((storage_beg <= new_container_beg &&
+         new_container_beg <= storage_end) &&
+        (storage_beg <= old_container_beg &&
+         old_container_beg <= storage_end) &&
+        (old_container_beg <= old_container_end &&
+         old_container_end <= storage_end) &&
+        (storage_beg <= old_container_end &&
+         old_container_end <= storage_end) &&
+        (storage_beg <= new_container_end &&
+         new_container_end <= storage_end) &&
+        (storage_beg <= old_container_beg &&
+         old_container_beg <= old_container_end))) {
+    GET_STACK_TRACE_FATAL_HERE;
+    ReportBadParamsToAnnotateDoubleEndedContiguousContainer(
+        storage_beg, storage_end, old_container_beg, old_container_end,
+        new_container_beg, new_container_end, &stack);
+  }
+
+  if (!IsAligned(storage_beg, granularity))
+    return;
+
+  if (old_container_beg == old_container_end) {
+    old_container_beg = old_container_end = new_container_beg;
+    old_container_beg_p = old_container_end_p = new_container_beg_p;
+  } else if (new_container_end <= old_container_beg ||
+             old_container_end <= new_container_beg ||
+             new_container_beg == new_container_end) {
+    __sanitizer_annotate_double_ended_contiguous_container_back(
+        storage_beg_p, storage_end_p, old_container_beg_p, old_container_end_p,
+        old_container_beg_p, old_container_beg_p);
+    old_container_beg = old_container_end = new_container_beg;
+    old_container_beg_p = old_container_end_p = new_container_beg_p;
+  }
+
+  if (old_container_beg_p != new_container_beg_p) {
+    __sanitizer_annotate_double_ended_contiguous_container_front(
+        storage_beg_p, storage_end_p, old_container_beg_p, old_container_end_p,
+        new_container_beg_p, new_container_end_p);
+    old_container_beg = new_container_beg;
+    old_container_beg_p = new_container_beg_p;
+  }
+
+  if (old_container_end_p != new_container_end_p)
+    __sanitizer_annotate_double_ended_contiguous_container_back(
+        storage_beg_p, storage_end_p, old_container_beg_p, old_container_end_p,
+        new_container_beg_p, new_container_end_p);
+}
+
 const void *__sanitizer_contiguous_container_find_bad_address(
     const void *beg_p, const void *mid_p, const void *end_p) {
   if (!flags()->detect_container_overflow)
     return nullptr;
   uptr beg = reinterpret_cast<uptr>(beg_p);
   uptr end = reinterpret_cast<uptr>(end_p);
   uptr mid = reinterpret_cast<uptr>(mid_p);
   CHECK_LE(beg, mid);
   CHECK_LE(mid, end);
-  // Check some bytes starting from beg, some bytes around mid, and some bytes
-  // ending with end.
+  // Check some bytes starting from storage_beg, some bytes around mid, and some
+  // bytes ending with end.
   uptr kMaxRangeToCheck = 32;
   uptr r1_beg = beg;
   uptr r1_end = Min(beg + kMaxRangeToCheck, mid);
   uptr r2_beg = Max(beg, mid - kMaxRangeToCheck);
   uptr r2_end = Min(end, mid + kMaxRangeToCheck);
   uptr r3_beg = Max(end - kMaxRangeToCheck, mid);
   uptr r3_end = end;
   for (uptr i = r1_beg; i < r1_end; i++)

 
 int __sanitizer_verify_contiguous_container(const void *beg_p,
                                             const void *mid_p,
                                             const void *end_p) {
   return __sanitizer_contiguous_container_find_bad_address(beg_p, mid_p,
                                                            end_p) == nullptr;
 }
 
+int __sanitizer_verify_double_ended_contiguous_container(
+    const void *storage_beg_p, const void *container_beg_p,
+    const void *container_end_p, const void *storage_end_p) {
+  uptr granularity = ASAN_SHADOW_GRANULARITY;
+  // This exists to verify double ended containers.
+  // We assume that such collection's internal memory layout
+  // consists of contiguous blocks:
+  // [a; b) [b; c) [c; d)
+  // where
+  // a - beginning address of contiguous memory block,
+  // b - beginning address of contiguous memory in use
+  //      (address of the first element in the block)
+  // c - end address of contiguous memory in use
+  //      (address just after the last element in the block)
+  // d - end address of contiguous memory block
+  // [a; b) - poisoned
+  // [b; c) - accessible
+  // [c; d) - poisoned
+  // WARNING: We can't poison [a; b) fully in all cases.
+  // This is because the current shadow memory encoding
+  // does not allow for marking/poisoning that a prefix
+  // of an 8-byte block (or, ASAN_SHADOW_GRANULARITY sized block)
+  // cannot be used by the instrumented program. It only has the
+  // 01, 02, 03, 04, 05, 06, 07 and 00 encodings
+  // for usable/addressable memory
+  // (where 00 means that the whole 8-byte block can be used).
+  //
+  // This means that there are cases where not whole of the [a; b)
+  // region is poisoned and instead only the [a; RoundDown(b))
+  // region is poisoned and we may not detect invalid memory accesses on
+  // [RegionDown(b), b).
+  // This is an inherent design limitation of how AddressSanitizer granularity
+  // and shadow memory encoding works at the moment.
+
+  // If empty, storage_beg_p == container_beg_p == container_end_p
+
+  const void *a = storage_beg_p;
+  // We do not suport poisoning prefixes of blocks, so
+  // memory in the first block with data in us,
+  // just before container beginning cannot be poisoned, as described above.
+  const void *b = reinterpret_cast<const void *>(
+      RoundDownTo(reinterpret_cast<uptr>(container_beg_p), granularity));
+  const void *c = container_end_p;
+  const void *d = storage_end_p;
+  if (container_beg_p == container_end_p)
+    return __sanitizer_contiguous_container_find_bad_address(a, a, d) ==
+           nullptr;
+  if (a < b &&
+      __sanitizer_contiguous_container_find_bad_address(a, a, b) != nullptr)
+    return false;
+  if (b < d &&
+      __sanitizer_contiguous_container_find_bad_address(b, c, d) != nullptr)
+    return false;
+
+  return true;
+}
+
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 void __asan_poison_intra_object_redzone(uptr ptr, uptr size) {
   AsanPoisonOrUnpoisonIntraObjectRedzone(ptr, size, true);
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 void __asan_unpoison_intra_object_redzone(uptr ptr, uptr size) {
   AsanPoisonOrUnpoisonIntraObjectRedzone(ptr, size, false);
 }
 
 // --- Implementation of LSan-specific functions --- {{{1
 namespace __lsan {
 bool WordIsPoisoned(uptr addr) {
   return (__asan_region_is_poisoned(addr, sizeof(uptr)) != 0);
 }
 }

compiler-rt/lib/asan/asan_report.h

void ReportStringFunctionMemoryRangesOverlap(const char *function,
                                              const char *offset1, uptr length1,
                                              const char *offset2, uptr length2,
                                              BufferedStackTrace *stack);
 void ReportStringFunctionSizeOverflow(uptr offset, uptr size,
                                       BufferedStackTrace *stack);
 void ReportBadParamsToAnnotateContiguousContainer(uptr beg, uptr end,
                                                   uptr old_mid, uptr new_mid,
                                                   BufferedStackTrace *stack);
+void ReportBadParamsToAnnotateDoubleEndedContiguousContainer(
+    uptr storage_beg, uptr storage_end, uptr old_container_beg,
+    uptr old_container_end, uptr new_container_beg, uptr new_container_end,
+    BufferedStackTrace *stack);
 
 void ReportODRViolation(const __asan_global *g1, u32 stack_id1,
                         const __asan_global *g2, u32 stack_id2);
 
 // Mac-specific errors and warnings.
 void ReportMacMzReallocUnknown(uptr addr, uptr zone_ptr,
                                const char *zone_name,
                                BufferedStackTrace *stack);
 void ReportMacCfReallocUnknown(uptr addr, uptr zone_ptr,
                                const char *zone_name,
                                BufferedStackTrace *stack);
 
 }  // namespace __asan
 #endif  // ASAN_REPORT_H

compiler-rt/lib/asan/asan_report.cpp

void ReportBadParamsToAnnotateContiguousContainer(uptr beg, uptr end,
                                                   uptr old_mid, uptr new_mid,
                                                   BufferedStackTrace *stack) {
   ScopedInErrorReport in_report;
   ErrorBadParamsToAnnotateContiguousContainer error(
       GetCurrentTidOrInvalid(), stack, beg, end, old_mid, new_mid);
   in_report.ReportError(error);
 }
 
+void ReportBadParamsToAnnotateDoubleEndedContiguousContainer(
+    uptr storage_beg, uptr storage_end, uptr old_container_beg,
+    uptr old_container_end, uptr new_container_beg, uptr new_container_end,
+    BufferedStackTrace *stack) {
+  ScopedInErrorReport in_report;
+  ErrorBadParamsToAnnotateDoubleEndedContiguousContainer error(
+      GetCurrentTidOrInvalid(), stack, storage_beg, storage_end,
+      old_container_beg, old_container_end, new_container_beg,
+      new_container_end);
+  in_report.ReportError(error);
+}
+
 void ReportODRViolation(const __asan_global *g1, u32 stack_id1,
                         const __asan_global *g2, u32 stack_id2) {
   ScopedInErrorReport in_report;
   ErrorODRViolation error(GetCurrentTidOrInvalid(), g1, stack_id1, g2,
                           stack_id2);
   in_report.ReportError(error);
 }
 

compiler-rt/lib/sanitizer_common/sanitizer_common_interface.inc

 //===-- sanitizer_common_interface.inc ------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 // Sanitizer Common interface list.
 //===----------------------------------------------------------------------===//
 INTERFACE_FUNCTION(__sanitizer_acquire_crash_state)
 INTERFACE_FUNCTION(__sanitizer_annotate_contiguous_container)
+INTERFACE_FUNCTION(__sanitizer_annotate_double_ended_contiguous_container)
 INTERFACE_FUNCTION(__sanitizer_contiguous_container_find_bad_address)
 INTERFACE_FUNCTION(__sanitizer_set_death_callback)
 INTERFACE_FUNCTION(__sanitizer_set_report_path)
 INTERFACE_FUNCTION(__sanitizer_set_report_fd)
 INTERFACE_FUNCTION(__sanitizer_get_report_path)
 INTERFACE_FUNCTION(__sanitizer_verify_contiguous_container)
+INTERFACE_FUNCTION(__sanitizer_verify_double_ended_contiguous_container)
 INTERFACE_WEAK_FUNCTION(__sanitizer_on_print)
 INTERFACE_WEAK_FUNCTION(__sanitizer_report_error_summary)
 INTERFACE_WEAK_FUNCTION(__sanitizer_sandbox_on_notify)
 // Sanitizer weak hooks
 INTERFACE_WEAK_FUNCTION(__sanitizer_weak_hook_memcmp)
 INTERFACE_WEAK_FUNCTION(__sanitizer_weak_hook_strcmp)
 INTERFACE_WEAK_FUNCTION(__sanitizer_weak_hook_strncmp)
 INTERFACE_WEAK_FUNCTION(__sanitizer_weak_hook_strstr)

compiler-rt/lib/sanitizer_common/sanitizer_interface_internal.h

void __sanitizer_annotate_contiguous_container(const void *beg, const void *end,
                                                const void *new_mid);
 SANITIZER_INTERFACE_ATTRIBUTE
 int __sanitizer_verify_contiguous_container(const void *beg, const void *mid,
                                             const void *end);
 SANITIZER_INTERFACE_ATTRIBUTE
 const void *__sanitizer_contiguous_container_find_bad_address(const void *beg,
                                                               const void *mid,
                                                               const void *end);
+SANITIZER_INTERFACE_ATTRIBUTE
+void __sanitizer_annotate_double_ended_contiguous_container(
+    const void *storage_beg, const void *storage_end,
+    const void *old_container_beg, const void *old_container_end,
+    const void *new_container_beg, const void *new_container_end);
 
 SANITIZER_INTERFACE_ATTRIBUTE
 int __sanitizer_get_module_and_offset_for_pc(void *pc, char *module_path,
                                              __sanitizer::uptr module_path_len,
                                              void **pc_offset);
+SANITIZER_INTERFACE_ATTRIBUTE
+int __sanitizer_verify_double_ended_contiguous_container(
+    const void *storage_beg, const void *container_beg,
+    const void *container_end, const void *storage_end);
 
 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE void
 __sanitizer_cov_trace_cmp();
 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE void
 __sanitizer_cov_trace_cmp1();
 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE void
 __sanitizer_cov_trace_cmp2();
 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE void

compiler-rt/test/asan/TestCases/contiguous_container.cpp

void TestContainer(size_t capacity) {
 
   // Don't forget to unpoison the whole thing before destroying/reallocating.
   __sanitizer_annotate_contiguous_container(beg, end, mid, end);
   for (size_t idx = 0; idx < capacity; idx++)
     assert(!__asan_address_is_poisoned(beg + idx));
   delete[] beg;
 }
 
+// Define ASAN_SHADOW_GRANULARITY if granularity is different
+#ifndef ASAN_SHADOW_GRANULARITY
+#  define ASAN_SHADOW_GRANULARITY 8
+#endif
+
+void TestDoubleEndedContainer(size_t capacity) {
+  char *beg = new char[capacity];
+  char *end = beg + capacity;
+  char *con_beg = beg;
+  char *con_end = beg + capacity;
+  char *old_con_beg = 0;
+  char *old_con_end = 0;
+  const size_t granularity = ASAN_SHADOW_GRANULARITY;
+
+  for (int i = 0; i < 10000; i++) {
+    size_t size = rand() % (capacity + 1);
+    size_t skipped = rand() % (capacity - size + 1);
+    assert(size <= capacity);
+    old_con_beg = con_beg;
+    old_con_end = con_end;
+    con_beg = beg + skipped;
+    con_end = con_beg + size;
+
+    __sanitizer_annotate_double_ended_contiguous_container(
+        beg, end, old_con_beg, old_con_end, con_beg, con_end);
+    for (size_t idx = 0; idx < granularity * (skipped / granularity); idx++)
+      assert(__asan_address_is_poisoned(beg + idx));
+    for (size_t idx = 0; idx < size; idx++)
+      assert(!__asan_address_is_poisoned(beg + skipped + idx));
+    for (size_t idx = skipped + size; idx < capacity; idx++)
+      assert(__asan_address_is_poisoned(beg + idx));
+
+    assert(__sanitizer_verify_double_ended_contiguous_container(beg, con_beg,
+                                                                con_end, end));
+  }
+
+  // Don't forget to unpoison the whole thing before destroying/reallocating.
+  __sanitizer_annotate_double_ended_contiguous_container(beg, end, con_beg,
+                                                         con_end, beg, end);
+  for (size_t idx = 0; idx < capacity; idx++)
+    assert(!__asan_address_is_poisoned(beg + idx));
+  delete[] beg;
+}
+
 __attribute__((noinline))
 void Throw() { throw 1; }
 
 __attribute__((noinline))
 void ThrowAndCatch() {
   try {
     Throw();
   } catch(...) {
void TestThrow() {
   assert(!__asan_address_is_poisoned(x + 14));
   __sanitizer_annotate_contiguous_container(x, x + 32, x + 14, x + 32);
   assert(!__asan_address_is_poisoned(x + 13));
   assert(!__asan_address_is_poisoned(x + 14));
 }
 
 int main(int argc, char **argv) {
   int n = argc == 1 ? 128 : atoi(argv[1]);
-  for (int i = 0; i <= n; i++)
+  for (int i = 0; i <= n; i++) {
     TestContainer(i);
+    TestDoubleEndedContainer(i);
+  }
   TestThrow();
 }