[1b/3][ASan][compiler-rt] API for annotating objects memory

[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 extends a compiler-rt ASan sanitization API function sanitizer_annotate_contiguous_container used to sanitize/annotate containers like std::vector to support different allocators and situations when granules are shared between objects. Those changes are necessary to support annotating objects' self memory (in contrast to annotating memory allocated by an object) like short std::basic_string (with short string optimization). That also allows use of non-standard memory allocators, as alignment requirement is no longer necessary.

This also updates an API function to verify if a double ended contiguous container is correctly annotated (__sanitizer_verify_contiguous_container).

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

[AdvenamTacet]

bool -> int

Removing bool type, because unit tests are failing.

[AdvenamTacet]

Fixing argument alignment (code formating).

[vitalybuka]

Can you please organize changes into a stack: "Edit related revisions" in Phabricator UI?

compiler-rt/lib/asan/asan_poisoning.cpp

389

We are looking into enabling StackStafety for asan (it's optimization)
which will make __sanitizer_annotate_contiguous_container not very useful for such short storages on the stack.

The problem with StackStafety that it assume that region of accessible memory of the stack object does not change over time, which is not true with __sanitizer_annotate_contiguous_container.

StackStafety will result in false negatives, when shadow set by __sanitizer_annotate_contiguous_container will not be checked.

So maybe investing into "short string" is not worth it?

395

Can we instead update __sanitizer_annotate_contiguous_container and friends to support this case

I guess we just need to load AddressIsPoisoned(beg-1) && AddressIsPoisoned(end) and make sure we do not poisoning them

[AdvenamTacet]

I stacked them, deque changes and string changes are independent.

compiler-rt/lib/asan/asan_poisoning.cpp

389

The motivation for the research and changes I am sending was a bug in 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 (so if iter1 was longer than iter2, we read out-of-bounds on iter2). While I agree this is a rare scenario, such a problem may still exist and so it may be beneficial to be able to detect it.

If we can't have both - annotating of short strings and StackSafety optimization, maybe we should have an option to enable one or another?

The work for annotating strings (both short and long including also the alternate string layout) has already been made. Removing just one case from it will generate more work.

395

No, it's not possible. Inside __sanitizer_annotate_contiguous_container there is not enough information. __sanitizer_is_annotable is necessary if object wants to poison self memory (not memory allocated by that object, but own memory), both on stack and heap.

Example when it's necessary (when alignment matters) is for example object in an array.

// SHADOW_GRANULARITY == 8
struct X { char buff[7];} // sizeof(X) == 7
X tab[2];

We cannot poison the first object in tab, because we will have to poison the first byte of the second object.

Therefore I believe that it's not possible to include it in __sanitizer_annotate_contiguous_container.

[vitalybuka]

can you please organize all of them into a stack? It supports multiple deps like for 3.
1a -> 2a

\
 --> 3
/

1b -> 2b

[vitalybuka]

compiler-rt/lib/asan/asan_poisoning.cpp

395

address_p and size_v are for container?

this info is provided into __sanitizer_annotate_contiguous_container
Simples way is just to have

static bool IsAnotateble();

void __sanitizer_annotate_contiguous_container() {
  // instead of CHECK
   if (!IsAnotateble) return;
}

No, it's not possible. Inside __sanitizer_annotate_contiguous_container there is not enough information. __sanitizer_is_annotable is necessary if object wants to poison self memory (not memory allocated by that object, but own memory), both on stack and heap.

Example when it's necessary (when alignment matters) is for example object in an array.

// SHADOW_GRANULARITY == 8
struct X { char buff[7];} // sizeof(X) == 7
X tab[2];

We cannot poison the first object in tab, because we will have to poison the first byte of the second object.

Therefore I believe that it's not possible to include it in __sanitizer_annotate_contiguous_container.

[AdvenamTacet]

compiler-rt/lib/asan/asan_poisoning.cpp

395

I believe, data provided into __sanitizer_annotate_contiguous_container is not sufficient, as there we do not know if memory is a separated buffer for containers content or part of a bigger object.

Let's look at it closer. For that example, SHADOW_GRANULARITY == 8.
Here are __sanitizer_annotate_contiguous_container arguments and the function do not have any other source of information:

void __sanitizer_annotate_contiguous_container(const void *beg_p,
                                               const void *end_p,
                                               const void *old_mid_p,
                                               const void *new_mid_p)

If we have a vector with allocated buffer of size 126 bytes (42 elements of size 3), distance between enp_p and beg_p is 126 (and 126 % 8 != 0). That's ok and we can poison that memory, but inside __sanitizer_annotate_contiguous_container we do not have information if it's allocated buffer or part of a bigger structure.

If object wants to poison self memory, size of the object has to be aligned. So, we cannot poison short string if sizeof(str)==126 bytes, we can annotate long string with external buffer of size 126.

Also, moving that check into __sanitizer_annotate_contiguous_container would have a bad performance effect. In std::vector, my patch for std::deque and long string case, there is only compile-time check if a standard allocator is used, and therefore it's not necessary to confirm that beg_p is aligned, in some scenarios (like short string) there is no way to check it compile time.

[vitalybuka]

compiler-rt/lib/asan/asan_poisoning.cpp

395

I am not concerned about alignment check cost, we have function call and memory writes already. This function is quite expensive.
In the case of aligned end_p we continue to work as is.
if not aligned, you can read shadow(end_p) and determine what is just after the buffer
this is slightly inefficient

If we open to extend API, alternative is an another version of sanitizer_annotate_contiguous_container
e.g. sanitizer_annotate_contiguous_container_unaligned() which never poisons unaligned tail/head granules

with __sanitizer_is_annotable() and sizeof(str)==126 you loose opportunity to check internal full granules.

[AdvenamTacet]

can you please organize all of them into a stack? It supports multiple deps like for 3.

Patch number 3 ([3/3][ASan] integration test for std::deque and std::basic_string annotations) is not public yet, but I will try to make it public soon. I have to include changes for patch 1a, 1b there.
Then I will stack it as well.

compiler-rt/lib/asan/asan_poisoning.cpp

395

address_p and size_v are for container?

It's for the memory controlled by the programmer. In our case it's address of the object (this) and the size of the object (sizeof(*this)). It may be also used for variables inside the class.

Inside that memory, programmer is responsible to make sure that every variable is accessible.

A good example is a short string with alternate string layout. Metadata byte is at the very end of the object and therefore is always poisoned, we turn off annotations in functions accessing that byte. (Similarly for optimized copy constructors.)
We use __sanitizer_is_annotable to make sure that we won't poison memory outside of the string object, where access may not be controlled by us.

We can use a function like sanitizer_annotate_contiguous_container_unaligned(...) suggested by you, we would just pass the beginning and the end of the object as the beginning and the end of the buffer - it has the same functionality wrapped in one function, I believe. If you prefer that solution, let me know.
However, I still believe that function just for that check is a better choice as it provides a bigger flexibility.

Also, if we go with sanitizer_annotate_contiguous_container_unaligned, should we create similar functions for double_ended containers, for consistency? That will double number of functions.

with __sanitizer_is_annotable() and sizeof(str)==126 you loose opportunity to check internal full granules.

Sorry, I'm not sure if I understand. Do you mean that buffer which we want to poison is aligned (size and address) and it's in a bigger object?
Isn't it the same with __sanitizer_is_annotable and sanitizer_annotate_contiguous_container_unaligned (once we just carefully choose address and size, once we carefully choose two addresses)?

if not aligned, you can read shadow(end_p) and determine what is just after the buffer
this is slightly inefficient

It looks a little bit risky and requires a lot of thinking about edge cases. I'm honestly not sure if I know how to implement it.

[vitalybuka]

compiler-rt/lib/asan/asan_poisoning.cpp

395

I am not concerned about alignment check cost, we have function call and memory writes already. This function is quite expensive.
In the case of aligned end_p we continue to work as is.
if not aligned, you can read shadow(end_p) and determine what is just after the buffer
this is slightly inefficient

If we open to extend API, alternative is an another version of sanitizer_annotate_contiguous_container
e.g. sanitizer_annotate_contiguous_container_unaligned() which never poisons unaligned tail/head granules

with __sanitizer_is_annotable() and sizeof(str)==126 you loose opportunity to check internal full granules.

395

Would prefer to do improve existing sanitizer_annotate_contiguous_container
note that you need to load unaligned shadow tail/head only when we about to poison tail/head granule.
so I am not concerned with perf.

[AdvenamTacet]

compiler-rt/lib/asan/asan_poisoning.cpp

395

Would prefer to do improve existing sanitizer_annotate_contiguous_container

I don't know how to do it without a new function in API.
I see the option I suggested or function like:

sanitizer_annotate_contiguous_container_unaligned(...) {
  if(!isAnnotable(...)) return;

  sanitizer_annotate_contiguous_container(...);
}

Possibly checking shadow memory around the buffer may be another solution, but I'm not sure how to implement it.
I'm quite sure that beg_p has to be aligned. If end_p is not aligned, possibly we can solve it with some ifs, but I'm not sure how exactly and what edge cases may happen.
If you have a clear idea, I will appreciate sharing details or implementation.

so I am not concerned with perf.

Ok, I'm not referring to performance in my previous answer.

[AdvenamTacet]

compiler-rt/lib/asan/asan_poisoning.cpp

395

I was thinking about it and I think I have a solution:

• beg_p has to be aligned (otherwise container is not annotated at all),
• if end_p is aligned, container is normally annotated,
• if end_p is not aligned, last granule is annotated if and only if all accessible bytes inside that granule are inside the container.

I believe it should work.

But I'm a little bit scared that there is some case I didn't think of. (Is it possible that some implementation break?)
Let me know what you think about it. If you believe that solution is correct and you would accept it, I can implement it instead of a new function in API.

Future improvement (I suggest another patch for it):

• First granule is not annotated when beg_p is not aligned, but all middle granules are. Therefore container may be partially annotated, even when beg_p is not aligned.

[AdvenamTacet]

This comment was removed by AdvenamTacet.

[AdvenamTacet]

Previous push was designed for a different revision. Sorry for it.

[AdvenamTacet]

Big change: now annotations work without changing API.

Annotation function is modified to support cases of not
aligned buffers and buffers in bigger structures.

That allows objets to annotate self memory.

[AdvenamTacet]

compiler-rt/lib/asan/asan_poisoning.cpp

395

It seems that it works, I implemented it and updated the revision.

[vitalybuka]

is this a bad rebase, I see stuff from D132090?

[AdvenamTacet]

Correct revision update, previous files are for deque...

Is there any way to automate updates to not make mistakes writing numbers?
To avoid writing arc diff --update <id>?

[vitalybuka]

In D132522#3807566, @AdvenamTacet wrote:

Correct revision update, previous files are for deque...

Is there any way to automate updates to not make mistakes writing numbers?
To avoid writing arc diff --update <id>?

I usually do "arc diff HEAD^" and it uploads to whatever is in the git commit description

[AdvenamTacet]

@vitalybuka yes, sorry for that. Now correct files are here. I think I have to change my workflow... now I have to be in a correct repo and write correct revision id in arc diff --update <id>, and clearly it's not easy for me. Sorry for the confusion.

[AdvenamTacet]

I will try your method, thank you!

[vitalybuka]

Please update

void TestContainer(size_t capacity, size_t off) {
  char *beg_alloc = new char[capacity + off];
  char *beg = beg_alloc;
  beg += off;

...

int main(int argc, char **argv) {
  int n = argc == 1 ? 128 : atoi(argv[1]);
  for (int i = 0; i <= n; i++)
    for (int j = 0; j < 8; j++)
      TestContainer(i, j);
  TestThrow();
}

As-is the patch fails check-asan

Please update compiler-rt/test/asan/TestCases/contiguous_container_crash.cpp

// RUN: %clangxx_asan -O %s -o %t
// RUN: not %run %t crash 2>&1 | FileCheck --check-prefix=CHECK-CRASH %s
// RUN: not %run %t bad-bounds 2>&1 | FileCheck --check-prefix=CHECK-BAD-BOUNDS %s
// RUN: not %run %t bad-alignment 2>&1 | FileCheck --check-prefix=CHECK-CRASH %s
// RUN: not %run %t bad-alignment-end 2>&1 | FileCheck --check-prefix=CHECK-CRASH %s
// RUN: %env_asan_opts=detect_container_overflow=0 %run %t crash
//
// Test crash due to __sanitizer_annotate_contiguous_container.

#include <assert.h>
#include <string.h>

extern "C" {
void __sanitizer_annotate_contiguous_container(const void *beg, const void *end,
                                               const void *old_mid,
                                               const void *new_mid);
}  // extern "C"

static volatile int one = 1;

int TestCrash() {
  long t[100];
  t[60] = 0;
  __sanitizer_annotate_contiguous_container(&t[0], &t[0] + 100, &t[0] + 100,
                                            &t[0] + 50);
// CHECK-CRASH: AddressSanitizer: container-overflow
// CHECK-CRASH: if you don't care about these errors you may set ASAN_OPTIONS=detect_container_overflow=0
  return (int)t[60 * one];  // Touches the poisoned memory.
}

void BadBounds() {
  long t[100];
// CHECK-BAD-BOUNDS: ERROR: AddressSanitizer: bad parameters to __sanitizer_annotate_contiguous_container
  __sanitizer_annotate_contiguous_container(&t[0], &t[0] + 100, &t[0] + 101,
                                            &t[0] + 50);
}

int BadAlignment() {
  int t[100];
  t[60] = 0;
  __sanitizer_annotate_contiguous_container(&t[1], &t[0] + 100, &t[0] + 100,
                                            &t[1] + 50);
  return (int)t[60 * one];  // Touches the poisoned memory.
}

int BadAlignmentEnd() {
  int t[99];
  t[60] = 0;
  __sanitizer_annotate_contiguous_container(&t[0], &t[0] + 99, &t[0] + 99,
                                            &t[0] + 50);
  return (int)t[60 * one];  // Touches the poisoned memory.
}

int main(int argc, char **argv) {
  assert(argc == 2);
  if (!strcmp(argv[1], "crash"))
    return TestCrash();
  else if (!strcmp(argv[1], "bad-bounds"))
    BadBounds();
  else if (!strcmp(argv[1], "bad-alignment"))
    return BadAlignment();
  else if (!strcmp(argv[1], "bad-alignment-end"))
    return BadAlignmentEnd();
  return 0;
}

compiler-rt/lib/asan/asan_poisoning.cpp

389

void __sanitizer_annotate_contiguous_container(const void *beg_p,
                                               const void *end_p,
                                               const void *old_mid_p,
                                               const void *new_mid_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)) {
    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.

  if (old_mid == new_mid)
    return;  // Nothing to do here.

  // Handle misaligned end and cut it off.
  if (UNLIKELY(!AddrIsAlignedByGranularity(end))) {
    uptr end_down = RoundDownTo(end, granularity);
    // Either new or old mid must be in the granule to affect it.
    if (new_mid > end_down) {
      if (AddressIsPoisoned(end)) {
        *(u8 *)MemToShadow(end_down) = static_cast<u8>(new_mid - end_down);
      } else {
        // Something after the container - don't touch.
      }
    } else if (old_mid > end_down) {
      if (AddressIsPoisoned(end)) {
        *(u8 *)MemToShadow(end_down) = kAsanContiguousContainerOOBMagic;
      } else {
        // Something after the container - don't touch.
      }
    }

    if (beg >= end_down)
      return;  // Same granule.

    old_mid = Min(end_down, old_mid);
    new_mid = Min(end_down, new_mid);
  }

  // Handle misaligned begin and cut it off.
  if (UNLIKELY(!AddrIsAlignedByGranularity(beg))) {
    uptr beg_up = RoundUpTo(beg, granularity);
    uptr beg_down = RoundDownTo(beg, granularity);
    // As soon as we add first byte into container we will not be able to
    // determine the state of the byte before the container. So we assume it's
    // always unpoison.

    // Either new or old mid must be in the granule to affect it.
    if (new_mid < beg_up) {
      *(u8 *)MemToShadow(beg_down) = static_cast<u8>(new_mid - beg_down);
    } else if (old_mid < beg_up) {
      *(u8 *)MemToShadow(beg_down) = 0;
    }

    old_mid = Max(beg_up, old_mid);
    new_mid = Max(beg_up, new_mid);
  }

  if (old_mid == new_mid)
    return;

  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:
  // [a, d1) is good, [d2, c) is bad, [d1, d2) is partially good.
  // Make a quick sanity check that we are indeed in this state.
  //
  // FIXME: Two of these three checks are disabled until we fix
  // https://github.com/google/sanitizers/issues/258.
  // if (d1 != d2)
  //  CHECK_EQ(*(u8*)MemToShadow(d1), old_mid - d1);
  if (a + granularity <= d1)
    CHECK_EQ(*(u8*)MemToShadow(a), 0);
  // if (d2 + granularity <= c && c <= end)
  //   CHECK_EQ(*(u8 *)MemToShadow(c - granularity),
  //            kAsanContiguousContainerOOBMagic);

  uptr b1 = RoundDownTo(new_mid, granularity);
  uptr b2 = RoundUpTo(new_mid, granularity);
  // New state:
  // [a, b1) is good, [b2, c) is bad, [b1, b2) is partially good.
  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);
  }
}

[AdvenamTacet]

Suggestions from the code review implemented.

• Updated annotation function to support non-aligned beginning and end.
• Implemented tests for non-aligned buffers in compiler-rt/test/asan/TestCases/contiguous_container
  • objects before buffer with different sizes
  • objects after buffer with different sizes
  • objects accessible and poisoned
• Updated and fixed compiler-rt/test/asan/TestCases/contiguous_container_crash.cpp as requested.

[vitalybuka]

Simplify test

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))) {
+  if (!(beg <= old_mid && beg <= new_mid && old_mid <= end && new_mid <= end)) {
     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.
 
+  if (old_mid == new_mid)
+    return;  // Nothing to do here.
+
+  // Handle misaligned end and cut it off.
+  if (UNLIKELY(!AddrIsAlignedByGranularity(end))) {
+    uptr end_down = RoundDownTo(end, granularity);
+    // Either new or old mid must be in the granule to affect it.
+    if (new_mid > end_down) {
+      if (AddressIsPoisoned(end)) {
+        *(u8 *)MemToShadow(end_down) = static_cast<u8>(new_mid - end_down);
+      } else {
+        // Something after the container - don't touch.
+      }
+    } else if (old_mid > end_down) {
+      if (AddressIsPoisoned(end)) {
+        *(u8 *)MemToShadow(end_down) = kAsanContiguousContainerOOBMagic;
+      } else {
+        // Something after the container - don't touch.
+      }
+    }
+
+    if (beg >= end_down)
+      return;  // Same granule.
+
+    old_mid = Min(end_down, old_mid);
+    new_mid = Min(end_down, new_mid);
+  }
+
+  // Handle misaligned begin and cut it off.
+  if (UNLIKELY(!AddrIsAlignedByGranularity(beg))) {
+    uptr beg_up = RoundUpTo(beg, granularity);
+    uptr beg_down = RoundDownTo(beg, granularity);
+    // As soon as we add first byte into container we will not be able to
+    // determine the state of the byte before the container. So we assume it's
+    // always unpoison.
+
+    // Either new or old mid must be in the granule to affect it.
+    if (new_mid < beg_up) {
+      *(u8 *)MemToShadow(beg_down) = static_cast<u8>(new_mid - beg_down);
+    } else if (old_mid < beg_up) {
+      *(u8 *)MemToShadow(beg_down) = 0;
+    }
+
+    old_mid = Max(beg_up, old_mid);
+    new_mid = Max(beg_up, new_mid);
+  }
+
+  if (old_mid == new_mid)
+    return;
+
   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:
   // [a, d1) is good, [d2, c) is bad, [d1, d2) is partially good.
   // Make a quick sanity check that we are indeed in this state.
   //
if (b1 != b2) {
     *(u8*)MemToShadow(b1) = static_cast<u8>(new_mid - b1);
   }
 }
 
 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 granularity = ASAN_SHADOW_GRANULARITY;
   uptr beg = reinterpret_cast<uptr>(beg_p);
   uptr end = reinterpret_cast<uptr>(end_p);
+  uptr annotations_end =
+      (!AddrIsAlignedByGranularity(end) && !AddressIsPoisoned(end))
+          ? RoundDownTo(end, granularity)
+          : end;
   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.
   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;
+  uptr r2_end = Min(annotations_end, mid + kMaxRangeToCheck);
+  uptr r3_beg = Max(annotations_end - kMaxRangeToCheck, mid);
+  uptr r3_end = annotations_end;
   for (uptr i = r1_beg; i < r1_end; i++)
     if (AddressIsPoisoned(i))
       return reinterpret_cast<const void *>(i);
   for (uptr i = r2_beg; i < mid; i++)
     if (AddressIsPoisoned(i))
       return reinterpret_cast<const void *>(i);
   for (uptr i = mid; i < r2_end; i++)
     if (!AddressIsPoisoned(i))

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

 // RUN: %clangxx_asan -fexceptions -O %s -o %t && %env_asan_opts=detect_stack_use_after_return=0 %run %t
 //
 // Test __sanitizer_annotate_contiguous_container.
 
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
 #include <assert.h>
 #include <sanitizer/asan_interface.h>
 
-void TestContainer(size_t capacity) {
-  char *beg = new char[capacity];
+static constexpr size_t kGranularity = 8;
+
+static constexpr bool AddrIsAlignedByGranularity(uintptr_t a) {
+  return (a & (kGranularity - 1)) == 0;
+}
+
+static constexpr uintptr_t RoundDown(uintptr_t x) {
+  return x & ~(kGranularity - 1);
+}
+
+void TestContainer(size_t capacity, size_t off_begin, size_t off_end,
+                   bool off_poisoned) {
+  char *buffer = new char[capacity + off_begin + off_end];
+  char *buffer_end = buffer + capacity + off_begin + off_end;
+  if (off_poisoned)
+    __sanitizer_annotate_contiguous_container(buffer, buffer_end, buffer_end,
+                                              buffer);
+  char *beg = buffer + off_begin;
   char *end = beg + capacity;
-  char *mid = beg + capacity;
+  char *mid = off_poisoned ? beg : beg + capacity;
   char *old_mid = 0;
+  // If after the container, there is another object, last granule
+  // cannot be poisoned.
+  char *cannot_poison =
+      (off_end == 0) ? end : (char *)RoundDown((uintptr_t)end);
 
-  for (int i = 0; i < 10000; i++) {
+  for (int i = 0; i < 1000; i++) {
     size_t size = rand() % (capacity + 1);
     assert(size <= capacity);
     old_mid = mid;
     mid = beg + size;
     __sanitizer_annotate_contiguous_container(beg, end, old_mid, mid);
 
+    // If off buffer before the container was poisoned and we had to
+    // unpoison it, we won't poison it again as we don't have information,
+    // if it was poisoned.
+    for (size_t idx = 0; idx < off_begin && !off_poisoned; idx++)
+      assert(!__asan_address_is_poisoned(buffer + idx));
     for (size_t idx = 0; idx < size; idx++)
-        assert(!__asan_address_is_poisoned(beg + idx));
-    for (size_t idx = size; idx < capacity; idx++)
-        assert(__asan_address_is_poisoned(beg + idx));
+    for (size_t idx = size; beg + idx < cannot_poison; idx++)
+    for (size_t idx = 0; idx < off_end; idx++) {
+      if (!off_poisoned)
+        assert(!__asan_address_is_poisoned(end + idx));
+      else // off part after the buffer should be always poisoned
+        assert(__asan_address_is_poisoned(end + idx));
+    }
+
     assert(__sanitizer_verify_contiguous_container(beg, mid, end));
     assert(NULL ==
            __sanitizer_contiguous_container_find_bad_address(beg, mid, end));
-    if (mid != beg) {
-      assert(!__sanitizer_verify_contiguous_container(beg, mid - 1, end));
-      assert(mid - 1 == __sanitizer_contiguous_container_find_bad_address(
-                            beg, mid - 1, end));
+    size_t distance = (off_end > 0) ? kGranularity + 1 : 1;
+    if (mid >= beg + distance) {
+      assert(
+          !__sanitizer_verify_contiguous_container(beg, mid - distance, end));
+      assert(mid - distance ==
+             __sanitizer_contiguous_container_find_bad_address(
+                 beg, mid - distance, end));
     }
-    if (mid != end) {
-      assert(!__sanitizer_verify_contiguous_container(beg, mid + 1, end));
+
+    if (mid + distance <= end) {
+      assert(
+          !__sanitizer_verify_contiguous_container(beg, mid + distance, end));
       assert(mid == __sanitizer_contiguous_container_find_bad_address(
-                        beg, mid + 1, end));
+                        beg, mid + distance, end));
     }
   }
 
   // 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;
+  if (capacity == 0 && off_poisoned)
+    mid = buffer;
+  __sanitizer_annotate_contiguous_container(buffer, buffer_end, mid,
+                                            buffer_end);
+  for (size_t idx = 0; idx < capacity + off_begin + off_end; idx++)
+    assert(!__asan_address_is_poisoned(buffer + idx));
+  delete[] buffer;
 }
 
 __attribute__((noinline))
 void Throw() { throw 1; }
 
 __attribute__((noinline))
 void ThrowAndCatch() {
   try {
     Throw();
-  } catch(...) {
+  } catch (...) {
   }
 }
 
 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));
   __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]);
+  int n = argc == 1 ? 64 : atoi(argv[1]);
   for (int i = 0; i <= n; i++)
-    TestContainer(i);
+    for (int j = 0; j < 8; j++)
+      for (int k = 0; k < 8; k++)
+        for (int off = 0; off < 2; ++off)
+          TestContainer(i, j, k, off);
   TestThrow();
 }

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

 // RUN: %clangxx_asan -O %s -o %t
 // RUN: not %run %t crash 2>&1 | FileCheck --check-prefix=CHECK-CRASH %s
 // RUN: not %run %t bad-bounds 2>&1 | FileCheck --check-prefix=CHECK-BAD-BOUNDS %s
-// RUN: not %run %t bad-alignment 2>&1 | FileCheck --check-prefix=CHECK-BAD-ALIGNMENT %s
+// RUN: not %run %t odd-alignment 2>&1 | FileCheck --check-prefix=CHECK-CRASH %s
+// RUN: not %run %t odd-alignment-end 2>&1 | FileCheck --check-prefix=CHECK-CRASH %s
 // RUN: %env_asan_opts=detect_container_overflow=0 %run %t crash
 //
 // Test crash due to __sanitizer_annotate_contiguous_container.
 
 #include <assert.h>
 #include <string.h>
 
 extern "C" {

 
 void BadBounds() {
   long t[100];
 // CHECK-BAD-BOUNDS: ERROR: AddressSanitizer: bad parameters to __sanitizer_annotate_contiguous_container
   __sanitizer_annotate_contiguous_container(&t[0], &t[0] + 100, &t[0] + 101,
                                             &t[0] + 50);
 }
 
-void BadAlignment() {
+int OddAlignment() {
   int t[100];
-// CHECK-BAD-ALIGNMENT: ERROR: AddressSanitizer: bad parameters to __sanitizer_annotate_contiguous_container
-// CHECK-BAD-ALIGNMENT: ERROR: beg is not aligned by {{[0-9]+}}
-  __sanitizer_annotate_contiguous_container(&t[1], &t[0] + 100, &t[1] + 10,
+  t[60] = 0;
+  __sanitizer_annotate_contiguous_container(&t[1], &t[0] + 100, &t[0] + 100,
+                                            &t[1] + 50);
+  return (int)t[60 * one]; // Touches the poisoned memory.
+}
+
+int OddAlignmentEnd() {
+  int t[99];
+  t[60] = 0;
+  __sanitizer_annotate_contiguous_container(&t[0], &t[0] + 98, &t[0] + 98,
                                             &t[0] + 50);
+  return (int)t[60 * one]; // Touches the poisoned memory.
 }
 
 int main(int argc, char **argv) {
   assert(argc == 2);
   if (!strcmp(argv[1], "crash"))
     return TestCrash();
   else if (!strcmp(argv[1], "bad-bounds"))
     BadBounds();
-  else if (!strcmp(argv[1], "bad-alignment"))
-    BadAlignment();
+  else if (!strcmp(argv[1], "odd-alignment"))
+    return OddAlignment();
+  else if (!strcmp(argv[1], "odd-alignment-end"))
+    return OddAlignmentEnd();
+  return 0;
 }