diff options
| author | Louis Dionne <ldionne.2@gmail.com> | 2025-08-28 18:07:59 -0400 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2025-08-28 18:07:59 -0400 |
| commit | 2ae4b92a1cf01b7d09f70ccc919eca2b5d02b080 (patch) | |
| tree | f2df05fc9d9ea1aa7431ac734fe910a0a660df96 | |
| parent | 6b4506009a0f90243b7a1a5ca619cbe52532ab86 (diff) | |
| download | llvm-2ae4b92a1cf01b7d09f70ccc919eca2b5d02b080.zip llvm-2ae4b92a1cf01b7d09f70ccc919eca2b5d02b080.tar.gz llvm-2ae4b92a1cf01b7d09f70ccc919eca2b5d02b080.tar.bz2 | |
[libc++] Fix broken precondition of __bit_log2 (#155476)
In #135303, we started using `__bit_log2` instead of `__log2i` inside
`std::sort`. However, `__bit_log2` has a precondition that `__log2i`
didn't have, which is that the input is non-zero. While it technically
makes no sense to request the logarithm of 0, `__log2i` handled that
case and returned 0 without issues.
After switching to `__bit_log2`, passing 0 as an input results in an
unsigned integer overflow which can trigger
`-fsanitize=unsigned-integer-overflow`. While not technically UB in
itself, it's clearly not intended either.
To fix this, we add an internal assertion to `__bit_log2` which catches
the issue in our test suite, and we make sure not to violate
`__bit_log2`'s preconditions before we call it from `std::sort`.
| -rw-r--r-- | libcxx/include/__algorithm/sort.h | 3 | ||||
| -rw-r--r-- | libcxx/include/__bit/bit_log2.h | 2 | ||||
| -rw-r--r-- | libcxx/src/algorithm.cpp | 3 |
3 files changed, 8 insertions, 0 deletions
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index 06cb5b8..8aa894e 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -860,6 +860,9 @@ __sort<__less<long double>&, long double*>(long double*, long double*, __less<lo template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { + if (__first == __last) // log(0) is undefined, so don't try computing the depth + return; + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __depth_limit = 2 * std::__bit_log2(std::__to_unsigned_like(__last - __first)); diff --git a/libcxx/include/__bit/bit_log2.h b/libcxx/include/__bit/bit_log2.h index 8077cd9..9ceeec1 100644 --- a/libcxx/include/__bit/bit_log2.h +++ b/libcxx/include/__bit/bit_log2.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___BIT_BIT_LOG2_H #define _LIBCPP___BIT_BIT_LOG2_H +#include <__assert> #include <__bit/countl.h> #include <__config> #include <__type_traits/integer_traits.h> @@ -23,6 +24,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Tp> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp __bit_log2(_Tp __t) _NOEXCEPT { static_assert(__is_unsigned_integer_v<_Tp>, "__bit_log2 requires an unsigned integer type"); + _LIBCPP_ASSERT_INTERNAL(__t != 0, "logarithm of 0 is undefined"); return numeric_limits<_Tp>::digits - 1 - std::__countl_zero(__t); } diff --git a/libcxx/src/algorithm.cpp b/libcxx/src/algorithm.cpp index d388fee..8157be6 100644 --- a/libcxx/src/algorithm.cpp +++ b/libcxx/src/algorithm.cpp @@ -13,6 +13,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class Comp, class RandomAccessIterator> void __sort(RandomAccessIterator first, RandomAccessIterator last, Comp comp) { + if (first == last) // log(0) is undefined, so don't try computing the depth + return; + auto depth_limit = 2 * std::__bit_log2(static_cast<size_t>(last - first)); // Only use bitset partitioning for arithmetic types. We should also check |