std::copy and others bypass _LIBCPP_ABI_BOUNDED_ITERATORS and other hardened iterators

[davidben]

std::copy has a memmove specialization for contiguous iterators. However, this specialization causes hardened iterator types, like _LIBCPP_ABI_BOUNDED_ITERATORS to lose their safety checks. This is particularly unfortunate because, as far as I can tell, the simplest way in C++20 to copy between spans is:

void copy_span(std::span<const int> src, std::span<int> dst) {
    std::ranges::copy(src, dst.begin());
}

This is bounds-safe with respect to src, because std::ranges takes care of ensuring we act on src.begin() and src.end() as a pair, but not with respect dst. There is no API that takes both input and output as range, as far as I can tell. That means our only option for safety is if dst.begin() returning an iterator type that is aware of its bounds. With libc++ bounded iterators, it does so. However, the specialization discards the optimization:

https://godbolt.org/z/scTvebr76

std::copy_n has a similar issue because it takes a count, so neither source nor destination pass their bounds.

Looking at libc++ internals, I think the problem is two-fold:

First, __bounded_iter does not check operator+, only operator*, so element-by-element dereference is the only hope we have to bounds-check things. But that's quite incompatible with the memcpy optimization. Also, as we see from copy_span2, Clang can't figure out to hoist the checks out of the loop. I suspect it doesn't help that __libcpp_verbose_abort forces different asserts to emit different messages. Although when I replace it with __builtin_trap, it still checks on every loop iteration.

Second, even if libc++ (or an external hardened iterator) checked operator+, it doesn't run operator+ on the output iterator before the memmove. We do actually run it after the memmove in __rewrap_iter, but by that point it's too late and we've written out of bounds.
https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/copy_move_common.h#L104-L108

So I think the way to fix this is:

1. Make __bounded_iter bounds-check operator+ and friends
2. Once we've determined the iterator is unwrappable, compute n = std::distance(first, last). Then compute __out_first + n and throw away the result. We're just trying to trigger hardening checks.
3. Optional: as a debug check (but not a hardening check because it should never happen and we don't want to actually emit it), assert that n matches the actual number of elements copied.

Update: In addition to the above issue, #78771 (comment) describes a second issue with the various __unwrap_iter optimizations.

[SanjayMarreddi]

Hi, I recently started fixing a few bugs in libc++ and thought of working on some complex tasks to familiarise myself with libc++ even more. I want to work on this if no one is yet.

PS: Pls let me know if this is an urgent task/way too complex!

[davidben]

Oh, I'm actually about to upload a PR for the first step here. :-)

[SanjayMarreddi]

Oh, I'm actually about to upload a PR for the first step here. :-)

No worries at all. Please continue. I will look into other issues. Thanks!

[davidben]

Looks like this also impacts the three-iterator std::equal which, like std::copy and std::move, implicitly sizes the second range by the first. In general, the issue comes up whenever we call __unwrap_iter on one half of a range but not the other half.

[davidben]

A second related issue: even when the algorithm unwraps a valid first/last pair, we lose all checking that the begin/end pair are consistent! This means buggy caller code like the following breaks:
https://godbolt.org/z/13cETfEx7

The best way I can see to fix this is to:

1. Introduce iterator compatibility checks on bounded_iter - bounded_iter, bounded_iter != bounded_iter, etc. This will also bring back some feature parity with the old debug iterators. See, e.g., debug.iterator.compare.pass.cpp
2. In __unwrap_range, compute std::distance(first, last) and throw it away, purely to trigger the compatibility checks
3. Fix all other __unwrap_iter calls to call __unwrap_range