https://github.com/llvmbot created
https://github.com/llvm/llvm-project/pull/155932
Backport 2ae4b92a1cf01b7d09f70ccc919eca2b5d02b080
Requested by: @ldionne
>From 6452ff38d23d8a3ac062517f86aa010fbcebaa50 Mon Sep 17 00:00:00 2001
From: Louis Dionne <ldionn...@gmail.com>
Date: Thu, 28 Aug 2025 18:07:59 -0400
Subject: [PATCH] [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`.
(cherry picked from commit 2ae4b92a1cf01b7d09f70ccc919eca2b5d02b080)
---
libcxx/include/__algorithm/sort.h | 3 +++
libcxx/include/__bit/bit_log2.h | 2 ++
libcxx/src/algorithm.cpp | 3 +++
3 files changed, 8 insertions(+)
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
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
