Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 847d636

Browse filesBrowse files
davidbendavidben
committed
[libc++] Add some _LIBCPP_ASSUMEs for bounded iterators
Playing around, this seems to address #101370 for `std::vector<char>`, but not `std::vector<int>`. `std::vector<int>` I believe also needs a solution to #101372, which is an alignment issue. The root problem is that vector uses end_cap instead of end as the hardening fencepost. But user code (be it an actual `iter != vec.end()` check, or one synthesized by the language in a range-for loop) uses the container end as the fencepost. We would like the user fencepost to delete the hardening fencepost. For that to happen, the compiler must know that if you take your iterator and then steadily `++iter`, stopping at `iter == end`, you won't hit `iter == end_cap` along the way. To fgire this out, the compiler needs to know a few things: 1. `iter <= end <= end_cap` at the start 2. `iter`, `end`, and `end_cap` are all compatibly aligned, such that `++iter` cannot skip over `end` and then get to `end_cap`. The first of these is not obvious in `std::vector` for because `std::vector` stores three pointers, rather than one pointer and then sizes. That means the compiler never sees `end` (or `end_cap`) computed as `begin + size` (or `begin + capacity`). Without type invariants, the compiler does not know that the three pointers have any relation at all. This PR addresses it by putting assumes in `__bounded_iter` itself. We could also place it in `std::vector::__make_iter`, but this invariant is important enough for reasoning about bounds that it seemed worth establishing it across the board. (Note this means we trust container implementations to use the bounded iterators correctly, which we already do. We're interested in catching bugs in user code, not the STL itself.) That alone is actually enough to handle this because constructing `vector::end()` is enough to tell the compiler that `begin <= end`, and loops usually start at `begin`. But since `__make_iter` is sometimes called on non-endpoint iterators, I added one extra invariant to `__make_iter`. The second issue is #101372. This PR does not address it but will (hopefully) take advantage of it once available. In working on this, I noticed that _LIBCPP_ASSUME silences -Wassume. Without that warning, I ended up spending a lot of time debugging silently no-op assumes. This seems to be a remnant of when _LIBCPP_ASSUME was part of _LIBCPP_ASSERT. Now that it's standalone, I think we shouldn't disable the warning by default. If we ever need to silence the warning, let's do it explicitly.
1 parent abe0dd1 commit 847d636
Copy full SHA for 847d636

File tree

Expand file treeCollapse file tree

3 files changed

+22
-4
lines changed
Filter options
Expand file treeCollapse file tree

3 files changed

+22
-4
lines changed

‎libcxx/include/__assert

Copy file name to clipboardExpand all lines: libcxx/include/__assert
+1-3Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -27,9 +27,7 @@
2727
// optimization intent. See https://discourse.llvm.org/t/llvm-assume-blocks-optimization/71609 for a
2828
// discussion.
2929
#if __has_builtin(__builtin_assume)
30-
# define _LIBCPP_ASSUME(expression) \
31-
(_LIBCPP_DIAGNOSTIC_PUSH _LIBCPP_CLANG_DIAGNOSTIC_IGNORED("-Wassume") \
32-
__builtin_assume(static_cast<bool>(expression)) _LIBCPP_DIAGNOSTIC_POP)
30+
# define _LIBCPP_ASSUME(expression) __builtin_assume(static_cast<bool>(expression))
3331
#else
3432
# define _LIBCPP_ASSUME(expression) ((void)0)
3533
#endif

‎libcxx/include/__iterator/bounded_iter.h

Copy file name to clipboardExpand all lines: libcxx/include/__iterator/bounded_iter.h
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,10 +89,22 @@ struct __bounded_iter {
8989
_LIBCPP_HIDE_FROM_ABI
9090
_LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __bounded_iter(_Iterator __current, _Iterator __begin, _Iterator __end)
9191
: __current_(__current), __begin_(__begin), __end_(__end) {
92+
// These are internal checks rather than hardening checks because the STL container is expected to ensure they are
93+
// in order.
9294
_LIBCPP_ASSERT_INTERNAL(
9395
__begin <= __current, "__bounded_iter(current, begin, end): current and begin are inconsistent");
9496
_LIBCPP_ASSERT_INTERNAL(
9597
__current <= __end, "__bounded_iter(current, begin, end): current and end are inconsistent");
98+
99+
// However, this order is important to help the compiler reason about bounds checks. For example, `std::vector` sets
100+
// `__end_ptr` to the capacity, not the true container end. To translate container-end fenceposts into hardening-end
101+
// fenceposts, we must know that container-end <= hardening-end. `std::__to_address` is needed because `_Iterator`
102+
// may be wrapped type, such that `operator<=` has side effects.
103+
pointer __begin_ptr = std::__to_address(__begin);
104+
pointer __current_ptr = std::__to_address(__current);
105+
pointer __end_ptr = std::__to_address(__end);
106+
_LIBCPP_ASSUME(__begin_ptr <= __current_ptr);
107+
_LIBCPP_ASSUME(__current_ptr <= __end_ptr);
96108
}
97109

98110
template <class _It>

‎libcxx/include/vector

Copy file name to clipboardExpand all lines: libcxx/include/vector
+9-1Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -850,6 +850,10 @@ private:
850850

851851
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator __make_iter(pointer __p) _NOEXCEPT {
852852
#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
853+
// `__bounded_iter` will tell the compiler that `__p` is bounded by `__begin_` and `__end_cap`, but nothing a priori
854+
// relates `__p` to `__end_`.
855+
_LIBCPP_ASSUME(__p <= this->__end_);
856+
853857
// Bound the iterator according to the capacity, rather than the size.
854858
//
855859
// Vector guarantees that iterators stay valid as long as no reallocation occurs even if new elements are inserted
@@ -870,7 +874,11 @@ private:
870874

871875
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(const_pointer __p) const _NOEXCEPT {
872876
#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR
873-
// Bound the iterator according to the capacity, rather than the size.
877+
// `__bounded_iter` will tell the compiler that `__p` is bounded by `__begin_` and `__end_cap`, but nothing a priori
878+
// relates `__p` to `__end_`.
879+
_LIBCPP_ASSUME(__p <= this->__end_);
880+
881+
// Bound the iterator according to the capacity, rather than the size. See above.
874882
return std::__make_bounded_iter(
875883
std::__wrap_iter<const_pointer>(__p),
876884
std::__wrap_iter<const_pointer>(this->__begin_),

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.