release/21.x: [libc++] Fix broken precondition of __bit_log2 (#155476) #155932
+8
−0
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
In llvm#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`. (cherry picked from commit 2ae4b92)
|
@philnik777 What do you think about merging this PR to the release branch? |
|
@llvm/pr-subscribers-libcxx Author: None (llvmbot) ChangesBackport 2ae4b92 Requested by: @ldionne Full diff: https://github.com/llvm/llvm-project/pull/155932.diff 3 Files Affected:
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
index 06cb5b8ce7057..8aa894e9228c6 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 8077cd91d6fd7..9ceeec1b2bc94 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 d388fee5f99cc..8157be6f7406e 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
|
philnik777
requested changes
Aug 29, 2025
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Backport 2ae4b92
Requested by: @ldionne