[libcxx]: vector: Use < instead of != to improve failure mode

[dexonsmith]

Summary

The following program is obviously broken:

#include <vector>
int main(int argc, const char * argv[]) {
    std::vector<int> v;
    v.push_back(0);
    v.pop_back();
    v.pop_back();
    return 0;
}

The failure mode at -O0 is pretty painful though. There's no crash;
instead std::vector<int>::~vector() hits an infinite loop in
std::__vector_base<int>::destruct_at_end(). In the following snippet,
__new_last starts *smaller* than __end_:

while (__new_last != __end_)
    __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_));

Note that __alloc_traits::destroy() is a no-op because int is POD,
so we don't get any bad memory accesses here. ASan does not catch this.

This patch changes the condition to:

while (__new_last < __end_)
    __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_));

making the infinite loop less likely. Since __new_last and __end_
are raw pointers, < should be the same cost as !=.

Unfortunately, I'm not sure how to add a test for this change.

I'm also not confident this is the best approach; suggestions welcome.
Maybe someone can even argue that the infinite loop is *better*...?

[mclow.lists]

Undefined behavior is just that, undefined.

I'm not that interested in "fixing" this; I don't think it's broken.

[dexonsmith]

I'm not sure I disagree. What got me slightly motivated was seeing
that UBSan doesn't catch this.

[mclow.lists]

Since __new_last and __end_ are raw pointers, < should be the same cost as !=.

pointer is an alias for allocator_traits<_Alloc>::pointer, which might not be a raw pointer.

[dexonsmith]

Ah, so the cost isn't necessarily the same. I don't think this
is worth it then. (Although, paradoxically, it opens up an avenue
for testing, via a custom allocator which counts </!= comparisons.)

Any other ideas for improving the failure mode?

[EricWF]

Maybe if we want to improve the failure mode we can add a _LIBCPP_ASSERT(__new_last <= __end, "invalid range")?

[EricWF]

This review seems stuck and dead. Resigning as a reviewer. Please re-add me if you want this revision to proceed.

[dexonsmith]

In D17053#632700, @EricWF wrote:

Maybe if we want to improve the failure mode we can add a _LIBCPP_ASSERT(__new_last <= __end, "invalid range")?

I suspect this assertion would get optimized out, since if __new_last > __end it's undefined behaviour to compare them. Whereas the loop condition won't get optimized away.

@ldionne, pointing you at this in case you have an idea (maybe specializing for raw pointers?), but I'm not planning to move this forward.

[ldionne]

In D17053#2315384, @dexonsmith wrote:

In D17053#632700, @EricWF wrote:

Maybe if we want to improve the failure mode we can add a _LIBCPP_ASSERT(__new_last <= __end, "invalid range")?

I suspect this assertion would get optimized out, since if __new_last > __end it's undefined behaviour to compare them. Whereas the loop condition won't get optimized away.

@ldionne, pointing you at this in case you have an idea (maybe specializing for raw pointers?), but I'm not planning to move this forward.

Thanks for the heads up. We already have _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector"); in vector::pop_back(), but it doesn't trigger because assertions in libc++ are tied to whether the debug mode is enabled, and by default, it's not enabled at all. I believe that fixing this instead is the right way to go, since we'll get this improvement but also several additional assertions that are already in place in libc++. It is on my roadmap to improve that situation.

[ldionne]

Also, regarding allocator::pointer vs raw pointers -- if someone defines a fancy pointer type whose operator< is significantly more costly than operator!=, I think this loop in libc++ is not the first thing that's going to bite them. I don't think that's the right motive to drop this patch, instead I think it's about the debug mode like I explained above.

include/vector

void __move_assign_alloc(__vector_base&, false_type)
         {}
 };
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
 {
-    while (__new_last != __end_)
+    while (__new_last < __end_)
         __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_));
 }
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 __vector_base<_Tp, _Allocator>::__vector_base()
         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
     : __begin_(nullptr),