diff --git a/compiler-rt/include/sanitizer/common_interface_defs.h b/compiler-rt/include/sanitizer/common_interface_defs.h --- a/compiler-rt/include/sanitizer/common_interface_defs.h +++ b/compiler-rt/include/sanitizer/common_interface_defs.h @@ -159,6 +159,40 @@ const void *old_mid, const void *new_mid); +/// Similar to __sanitizer_annotate_contiguous_container. +/// +/// Annotates the current state of a contiguous container memory, +/// such as std::deque'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 +/// [storage_beg, storage_end); the memory [container_beg, +/// container_end) is used to store the current elements, and the memory +/// [storage_beg, container_beg), [container_end, storage_end) is +/// reserved for future elements (storage_beg <= container_beg <= +/// container_end <= storage_end). For example, in std::deque : +/// - 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 container_beg == +/// storage_beg . +/// +/// 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. +/// \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 [beg, end) is properly /// poisoned. /// @@ -178,6 +212,31 @@ int __sanitizer_verify_contiguous_container(const void *beg, const void *mid, const void *end); +/// Returns true if the double ended contiguous +/// container [storage_beg, storage_end) is properly poisoned. +/// +/// Proper poisoning could occur, for example, with +/// __sanitizer_annotate_double_ended_contiguous_container), that is, if +/// [storage_beg, container_beg) is not addressable, [container_beg, +/// container_end) is addressable and [container_end, end) is +/// unaddressable. Full verification requires O (storage_end - +/// storage_beg) time; this function tries to avoid such complexity by +/// touching only parts of the container around storage_beg, +/// container_beg, container_end, and +/// storage_end. +/// +/// \param storage_beg Beginning of memory region. +/// \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 [storage_beg, +/// container_beg, container_end, end) 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 __sanitizer_verify_contiguous_container() but also /// returns the address of the first improperly poisoned byte. /// @@ -192,6 +251,20 @@ const void *mid, const void *end); +/// returns the address of the first improperly poisoned byte. +/// +/// Returns NULL if the area is poisoned properly. +/// +/// \param storage_beg Beginning of memory region. +/// \param container_beg Beginning of used region. +/// \param container_end End of used region. +/// \param storage_end End of memory region. +/// +/// \returns The bad address or NULL. +const void *__sanitizer_double_ended_contiguous_container_find_bad_address( + const void *storage_beg, const void *container_beg, + const void *container_end, const void *storage_end); + /// Prints the stack trace leading to this call (useful for calling from the /// debugger). void __sanitizer_print_stack_trace(void); diff --git a/compiler-rt/lib/asan/asan_errors.h b/compiler-rt/lib/asan/asan_errors.h --- a/compiler-rt/lib/asan/asan_errors.h +++ b/compiler-rt/lib/asan/asan_errors.h @@ -331,6 +331,28 @@ 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; @@ -398,6 +420,7 @@ macro(StringFunctionMemoryRangesOverlap) \ macro(StringFunctionSizeOverflow) \ macro(BadParamsToAnnotateContiguousContainer) \ + macro(BadParamsToAnnotateDoubleEndedContiguousContainer) \ macro(ODRViolation) \ macro(InvalidPointerPair) \ macro(Generic) diff --git a/compiler-rt/lib/asan/asan_errors.cpp b/compiler-rt/lib/asan/asan_errors.cpp --- a/compiler-rt/lib/asan/asan_errors.cpp +++ b/compiler-rt/lib/asan/asan_errors.cpp @@ -334,6 +334,26 @@ 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()); diff --git a/compiler-rt/lib/asan/asan_poisoning.cpp b/compiler-rt/lib/asan/asan_poisoning.cpp --- a/compiler-rt/lib/asan/asan_poisoning.cpp +++ b/compiler-rt/lib/asan/asan_poisoning.cpp @@ -472,6 +472,148 @@ } } +// Annotates a double ended contiguous memory area 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( + 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) { + if (!flags()->detect_container_overflow) + return; + + VPrintf(2, "contiguous_container: %p %p %p %p %p %p\n", storage_beg_p, + storage_end_p, old_container_beg_p, old_container_end_p, + new_container_beg_p, new_container_end_p); + + uptr storage_beg = reinterpret_cast(storage_beg_p); + uptr storage_end = reinterpret_cast(storage_end_p); + uptr old_beg = reinterpret_cast(old_container_beg_p); + uptr old_end = reinterpret_cast(old_container_end_p); + uptr new_beg = reinterpret_cast(new_container_beg_p); + uptr new_end = reinterpret_cast(new_container_end_p); + + constexpr uptr granularity = ASAN_SHADOW_GRANULARITY; + + if (!(storage_beg <= new_beg && new_beg <= storage_end) || + !(storage_beg <= new_end && new_end <= storage_end) || + !(storage_beg <= old_beg && old_beg <= storage_end) || + !(storage_beg <= old_end && old_end <= storage_end) || + !(old_beg <= old_end && new_beg <= new_end)) { + GET_STACK_TRACE_FATAL_HERE; + ReportBadParamsToAnnotateDoubleEndedContiguousContainer( + storage_beg, storage_end, old_beg, old_end, new_beg, new_end, &stack); + } + + // Right now, the function does not support: + // - unaligned storage beginning + // - situations when container ends in the middle of granule + // (storage_end is unaligned by granularity) + // and shares that granule with a different object. + if (!AddrIsAlignedByGranularity(storage_beg)) + return; + + if (old_beg == old_end) { + old_beg = old_end = new_beg; + } else if (new_end <= old_beg || old_end <= new_beg || new_beg == new_end) { + // Poisoining whole memory. + uptr a = RoundDownTo(old_beg, granularity); + uptr b = RoundUpTo(old_end, granularity); + PoisonShadow(a, b - a, kAsanContiguousContainerOOBMagic); + + old_beg = old_end = new_beg; + } + + if (old_beg != new_beg) { + 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 (granularity - 1) bytes not-in-use may not be poisoned. + + if (new_beg < old_beg) { // We are unpoisoning + uptr a = RoundDownTo(new_beg, granularity); + uptr c = RoundDownTo(old_beg, granularity); + // State at the moment is: + // [storage_beg, a] is poisoned and should remain like that. + // [a, c] is poisoned as well (interval may be empty if new_beg + // and old_beg are in the same block). If the container is not + // empty, first element starts somewhere in [c, c+granularity]. Because we + // do not poison prefixes, memory [c, container_end] is not poisoned and + // we won't change 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_beg == old_end && + !AddrIsAlignedByGranularity(old_beg)) { // was empty && ends in the + // middle of a block + *(u8 *)MemToShadow(c) = static_cast(old_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_beg, granularity); + uptr c = RoundDownTo(new_beg, granularity); + // State at the moment is: + // [storage_beg, a] is poisoned and should remain like that. + // [a, c] is not poisoned (interval may be empty if new_beg and + // old_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_beg == old_end && + !AddrIsAlignedByGranularity(new_beg)) { // is empty && ends in the + // middle of a block + *(u8 *)MemToShadow(c) = + static_cast(kAsanContiguousContainerOOBMagic); + } + } + + old_beg = new_beg; + } + + if (old_end != new_end) { + CHECK_LE(storage_end - storage_beg, + FIRST_32_SECOND_64(1UL << 30, 1ULL << 40)); // Sanity check. + + if (old_end < new_end) { // We are unpoisoning memory + uptr a = RoundDownTo(old_end, granularity); + uptr c = RoundDownTo(new_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 (!AddrIsAlignedByGranularity( + new_end)) // ends in the middle of a block + *(u8 *)MemToShadow(c) = static_cast(new_end - c); + } else { // We are poisoning memory + uptr a = RoundDownTo(new_end, granularity); + // State at the moment is: + // [storage_beg, a] is correctly annotated + // 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_end, granularity); + uptr c2 = RoundUpTo(old_end, granularity); + PoisonShadow(a2, c2 - a2, kAsanContiguousContainerOOBMagic); + if (!AddrIsAlignedByGranularity( + new_end)) { // Starts in the middle of the block + if (new_end == old_beg) // empty + *(u8 *)MemToShadow(a) = kAsanContiguousContainerOOBMagic; + else // not empty + *(u8 *)MemToShadow(a) = static_cast(new_end - a); + } + } + } +} + 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) @@ -486,8 +628,8 @@ uptr mid = reinterpret_cast(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); @@ -517,6 +659,71 @@ end_p) == nullptr; } +const void *__sanitizer_double_ended_contiguous_container_find_bad_address( + 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( + RoundDownTo(reinterpret_cast(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); + const void *result; + if (a < b && + (result = __sanitizer_contiguous_container_find_bad_address(a, a, b))) + return result; + if (b < d && + (result = __sanitizer_contiguous_container_find_bad_address(b, c, d))) + return result; + + return 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) { + return __sanitizer_double_ended_contiguous_container_find_bad_address( + storage_beg_p, container_beg_p, container_end_p, storage_end_p) == + nullptr; +} + extern "C" SANITIZER_INTERFACE_ATTRIBUTE void __asan_poison_intra_object_redzone(uptr ptr, uptr size) { AsanPoisonOrUnpoisonIntraObjectRedzone(ptr, size, true); diff --git a/compiler-rt/lib/asan/asan_report.h b/compiler-rt/lib/asan/asan_report.h --- a/compiler-rt/lib/asan/asan_report.h +++ b/compiler-rt/lib/asan/asan_report.h @@ -83,6 +83,10 @@ 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); diff --git a/compiler-rt/lib/asan/asan_report.cpp b/compiler-rt/lib/asan/asan_report.cpp --- a/compiler-rt/lib/asan/asan_report.cpp +++ b/compiler-rt/lib/asan/asan_report.cpp @@ -354,6 +354,18 @@ 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; diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common_interface.inc b/compiler-rt/lib/sanitizer_common/sanitizer_common_interface.inc --- a/compiler-rt/lib/sanitizer_common/sanitizer_common_interface.inc +++ b/compiler-rt/lib/sanitizer_common/sanitizer_common_interface.inc @@ -9,12 +9,16 @@ //===----------------------------------------------------------------------===// 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_double_ended_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) diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_interface_internal.h b/compiler-rt/lib/sanitizer_common/sanitizer_interface_internal.h --- a/compiler-rt/lib/sanitizer_common/sanitizer_interface_internal.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_interface_internal.h @@ -66,18 +66,30 @@ const void *old_mid, const void *new_mid); 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_verify_contiguous_container(const void *beg, const void *mid, const void *end); 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 const void *__sanitizer_contiguous_container_find_bad_address(const void *beg, const void *mid, const void *end); +SANITIZER_INTERFACE_ATTRIBUTE +const void *__sanitizer_double_ended_contiguous_container_find_bad_address( + const void *storage_beg, const void *container_beg, + const void *container_end, const void *storage_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 SANITIZER_WEAK_ATTRIBUTE void __sanitizer_cov_trace_cmp(); SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE void diff --git a/compiler-rt/test/asan/TestCases/contiguous_container.cpp b/compiler-rt/test/asan/TestCases/contiguous_container.cpp --- a/compiler-rt/test/asan/TestCases/contiguous_container.cpp +++ b/compiler-rt/test/asan/TestCases/contiguous_container.cpp @@ -79,6 +79,38 @@ delete[] buffer; } +void TestDoubleEndedContainer(size_t capacity) { + char *st_beg = new char[capacity]; + char *st_end = st_beg + capacity; + char *beg = st_beg; + char *end = st_beg + capacity; + + for (int i = 0; i < 10000; i++) { + size_t size = rand() % (capacity + 1); + size_t skipped = rand() % (capacity - size + 1); + assert(size <= capacity); + char *old_beg = beg; + char *old_end = end; + beg = st_beg + skipped; + end = beg + size; + + __sanitizer_annotate_double_ended_contiguous_container( + st_beg, st_end, old_beg, old_end, beg, end); + for (size_t idx = 0; idx < RoundDown(skipped); idx++) + assert(__asan_address_is_poisoned(st_beg + idx)); + for (size_t idx = 0; idx < size; idx++) + assert(!__asan_address_is_poisoned(st_beg + skipped + idx)); + for (size_t idx = skipped + size; idx < capacity; idx++) + assert(__asan_address_is_poisoned(st_beg + idx)); + + assert(__sanitizer_verify_double_ended_contiguous_container(st_beg, beg, + end, st_end)); + } + + __asan_unpoison_memory_region(st_beg, st_end - st_beg); + delete[] st_beg; +} + __attribute__((noinline)) void Throw() { throw 1; } __attribute__((noinline)) void ThrowAndCatch() { @@ -103,9 +135,13 @@ int main(int argc, char **argv) { int n = argc == 1 ? 64 : atoi(argv[1]); - for (int i = 0; i <= n; i++) - for (int j = 0; j < kGranularity * 2; j++) - for (int poison = 0; poison < 2; ++poison) + for (int i = 0; i <= n; i++) { + for (int j = 0; j < kGranularity * 2; j++) { + for (int poison = 0; poison < 2; ++poison) { TestContainer(i, j, poison); + } + } + TestDoubleEndedContainer(i); + } TestThrow(); }