[clang-tools-extra] [libc++] Add assertions for potential OOB reads in std::nth_element (PR #67023)
https://github.com/danlark1 updated
https://github.com/llvm/llvm-project/pull/67023
>From 059bbfab50592026ce2785c5f7d98eaf5c9f8bd6 Mon Sep 17 00:00:00 2001
From: Daniel Kutenin
Date: Thu, 21 Sep 2023 14:55:11 +0100
Subject: [PATCH 1/7] Add bound checking in nth_element
---
libcxx/include/__algorithm/nth_element.h | 28 +++-
1 file changed, 22 insertions(+), 6 deletions(-)
diff --git a/libcxx/include/__algorithm/nth_element.h
b/libcxx/include/__algorithm/nth_element.h
index dbacf58f9ecdbc4..37e43ab0db8ca4f 100644
--- a/libcxx/include/__algorithm/nth_element.h
+++ b/libcxx/include/__algorithm/nth_element.h
@@ -116,10 +116,18 @@ __nth_element(_RandomAccessIterator __first,
_RandomAccessIterator __nth, _Rando
return;
}
while (true) {
-while (!__comp(*__first, *__i))
+while (!__comp(*__first, *__i)) {
++__i;
-while (__comp(*__first, *--__j))
-;
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__i != __last,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+}
+do {
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__j != __first,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+--__j;
+} while (__comp(*__first, *__j));
if (__i >= __j)
break;
_Ops::iter_swap(__i, __j);
@@ -146,11 +154,19 @@ __nth_element(_RandomAccessIterator __first,
_RandomAccessIterator __nth, _Rando
while (true)
{
// __m still guards upward moving __i
-while (__comp(*__i, *__m))
+while (__comp(*__i, *__m)) {
++__i;
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__i != __last,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+}
// It is now known that a guard exists for downward moving __j
-while (!__comp(*--__j, *__m))
-;
+do {
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__j != __first,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+--__j;
+} while (!__comp(*__j, *__m));
if (__i >= __j)
break;
_Ops::iter_swap(__i, __j);
>From 8e128c3ce6d8dc8afb94ba2465a2585fe3b8525a Mon Sep 17 00:00:00 2001
From: Daniel Kutenin
Date: Thu, 21 Sep 2023 15:22:18 +0100
Subject: [PATCH 2/7] Update nth_element out of bound test
---
.../assert.sort.invalid_comparator.pass.cpp | 77 +++
1 file changed, 61 insertions(+), 16 deletions(-)
diff --git
a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
index e5e417fe7bda2d4..b02ae2118ec5f47 100644
---
a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
+++
b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
@@ -50,27 +50,37 @@
#include "bad_comparator_values.h"
#include "check_assertion.h"
-void check_oob_sort_read() {
-std::map> comparison_results; //
terrible for performance, but really convenient
-for (auto line : std::views::split(DATA, '\n') |
std::views::filter([](auto const& line) { return !line.empty(); })) {
-auto values = std::views::split(line, ' ');
-auto it = values.begin();
-std::size_t left = std::stol(std::string((*it).data(), (*it).size()));
-it = std::next(it);
-std::size_t right = std::stol(std::string((*it).data(), (*it).size()));
-it = std::next(it);
-bool result = static_cast(std::stol(std::string((*it).data(),
(*it).size(;
-comparison_results[left][right] = result;
-}
-auto predicate = [&](std::size_t* left, std::size_t* right) {
+class ComparisonResults {
+public:
+ComparisonResults(std::string_view data) {
+for (auto line : std::views::split(data, '\n') |
std::views::filter([](auto const& line) { return !line.empty(); })) {
+auto values = std::views::split(line, ' ');
+auto it = values.begin();
+std::size_t left = std::stol(std::string((*it).data(),
(*it).size()));
+it = std::next(it);
+std::size_t right = std::stol(std::string((*it).data(),
(*it).size()));
+it = std::next(it);
+
[clang] [libc++] Add assertions for potential OOB reads in std::nth_element (PR #67023)
https://github.com/danlark1 updated
https://github.com/llvm/llvm-project/pull/67023
>From 059bbfab50592026ce2785c5f7d98eaf5c9f8bd6 Mon Sep 17 00:00:00 2001
From: Daniel Kutenin
Date: Thu, 21 Sep 2023 14:55:11 +0100
Subject: [PATCH 1/7] Add bound checking in nth_element
---
libcxx/include/__algorithm/nth_element.h | 28 +++-
1 file changed, 22 insertions(+), 6 deletions(-)
diff --git a/libcxx/include/__algorithm/nth_element.h
b/libcxx/include/__algorithm/nth_element.h
index dbacf58f9ecdbc4..37e43ab0db8ca4f 100644
--- a/libcxx/include/__algorithm/nth_element.h
+++ b/libcxx/include/__algorithm/nth_element.h
@@ -116,10 +116,18 @@ __nth_element(_RandomAccessIterator __first,
_RandomAccessIterator __nth, _Rando
return;
}
while (true) {
-while (!__comp(*__first, *__i))
+while (!__comp(*__first, *__i)) {
++__i;
-while (__comp(*__first, *--__j))
-;
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__i != __last,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+}
+do {
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__j != __first,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+--__j;
+} while (__comp(*__first, *__j));
if (__i >= __j)
break;
_Ops::iter_swap(__i, __j);
@@ -146,11 +154,19 @@ __nth_element(_RandomAccessIterator __first,
_RandomAccessIterator __nth, _Rando
while (true)
{
// __m still guards upward moving __i
-while (__comp(*__i, *__m))
+while (__comp(*__i, *__m)) {
++__i;
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__i != __last,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+}
// It is now known that a guard exists for downward moving __j
-while (!__comp(*--__j, *__m))
-;
+do {
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__j != __first,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+--__j;
+} while (!__comp(*__j, *__m));
if (__i >= __j)
break;
_Ops::iter_swap(__i, __j);
>From 8e128c3ce6d8dc8afb94ba2465a2585fe3b8525a Mon Sep 17 00:00:00 2001
From: Daniel Kutenin
Date: Thu, 21 Sep 2023 15:22:18 +0100
Subject: [PATCH 2/7] Update nth_element out of bound test
---
.../assert.sort.invalid_comparator.pass.cpp | 77 +++
1 file changed, 61 insertions(+), 16 deletions(-)
diff --git
a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
index e5e417fe7bda2d4..b02ae2118ec5f47 100644
---
a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
+++
b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
@@ -50,27 +50,37 @@
#include "bad_comparator_values.h"
#include "check_assertion.h"
-void check_oob_sort_read() {
-std::map> comparison_results; //
terrible for performance, but really convenient
-for (auto line : std::views::split(DATA, '\n') |
std::views::filter([](auto const& line) { return !line.empty(); })) {
-auto values = std::views::split(line, ' ');
-auto it = values.begin();
-std::size_t left = std::stol(std::string((*it).data(), (*it).size()));
-it = std::next(it);
-std::size_t right = std::stol(std::string((*it).data(), (*it).size()));
-it = std::next(it);
-bool result = static_cast(std::stol(std::string((*it).data(),
(*it).size(;
-comparison_results[left][right] = result;
-}
-auto predicate = [&](std::size_t* left, std::size_t* right) {
+class ComparisonResults {
+public:
+ComparisonResults(std::string_view data) {
+for (auto line : std::views::split(data, '\n') |
std::views::filter([](auto const& line) { return !line.empty(); })) {
+auto values = std::views::split(line, ' ');
+auto it = values.begin();
+std::size_t left = std::stol(std::string((*it).data(),
(*it).size()));
+it = std::next(it);
+std::size_t right = std::stol(std::string((*it).data(),
(*it).size()));
+it = std::next(it);
+
[clang-tools-extra] [libc++] Add assertions for potential OOB reads in std::nth_element (PR #67023)
danlark1 wrote: @ldionne, CI is green, please, merge Thanks for the feedback to everyone! https://github.com/llvm/llvm-project/pull/67023 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libc++] Add assertions for potential OOB reads in std::nth_element (PR #67023)
danlark1 wrote: @ldionne, CI is green, please, merge Thanks for the feedback to everyone! https://github.com/llvm/llvm-project/pull/67023 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang-tools-extra] [libc++] Add assertions for potential OOB reads in std::nth_element (PR #67023)
https://github.com/danlark1 updated
https://github.com/llvm/llvm-project/pull/67023
>From 059bbfab50592026ce2785c5f7d98eaf5c9f8bd6 Mon Sep 17 00:00:00 2001
From: Daniel Kutenin
Date: Thu, 21 Sep 2023 14:55:11 +0100
Subject: [PATCH 1/6] Add bound checking in nth_element
---
libcxx/include/__algorithm/nth_element.h | 28 +++-
1 file changed, 22 insertions(+), 6 deletions(-)
diff --git a/libcxx/include/__algorithm/nth_element.h
b/libcxx/include/__algorithm/nth_element.h
index dbacf58f9ecdbc4..37e43ab0db8ca4f 100644
--- a/libcxx/include/__algorithm/nth_element.h
+++ b/libcxx/include/__algorithm/nth_element.h
@@ -116,10 +116,18 @@ __nth_element(_RandomAccessIterator __first,
_RandomAccessIterator __nth, _Rando
return;
}
while (true) {
-while (!__comp(*__first, *__i))
+while (!__comp(*__first, *__i)) {
++__i;
-while (__comp(*__first, *--__j))
-;
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__i != __last,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+}
+do {
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__j != __first,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+--__j;
+} while (__comp(*__first, *__j));
if (__i >= __j)
break;
_Ops::iter_swap(__i, __j);
@@ -146,11 +154,19 @@ __nth_element(_RandomAccessIterator __first,
_RandomAccessIterator __nth, _Rando
while (true)
{
// __m still guards upward moving __i
-while (__comp(*__i, *__m))
+while (__comp(*__i, *__m)) {
++__i;
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__i != __last,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+}
// It is now known that a guard exists for downward moving __j
-while (!__comp(*--__j, *__m))
-;
+do {
+_LIBCPP_ASSERT_UNCATEGORIZED(
+__j != __first,
+"Would read out of bounds, does your comparator
satisfy the strict-weak ordering requirement?");
+--__j;
+} while (!__comp(*__j, *__m));
if (__i >= __j)
break;
_Ops::iter_swap(__i, __j);
>From 8e128c3ce6d8dc8afb94ba2465a2585fe3b8525a Mon Sep 17 00:00:00 2001
From: Daniel Kutenin
Date: Thu, 21 Sep 2023 15:22:18 +0100
Subject: [PATCH 2/6] Update nth_element out of bound test
---
.../assert.sort.invalid_comparator.pass.cpp | 77 +++
1 file changed, 61 insertions(+), 16 deletions(-)
diff --git
a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
index e5e417fe7bda2d4..b02ae2118ec5f47 100644
---
a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
+++
b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp
@@ -50,27 +50,37 @@
#include "bad_comparator_values.h"
#include "check_assertion.h"
-void check_oob_sort_read() {
-std::map> comparison_results; //
terrible for performance, but really convenient
-for (auto line : std::views::split(DATA, '\n') |
std::views::filter([](auto const& line) { return !line.empty(); })) {
-auto values = std::views::split(line, ' ');
-auto it = values.begin();
-std::size_t left = std::stol(std::string((*it).data(), (*it).size()));
-it = std::next(it);
-std::size_t right = std::stol(std::string((*it).data(), (*it).size()));
-it = std::next(it);
-bool result = static_cast(std::stol(std::string((*it).data(),
(*it).size(;
-comparison_results[left][right] = result;
-}
-auto predicate = [&](std::size_t* left, std::size_t* right) {
+class ComparisonResults {
+public:
+ComparisonResults(std::string_view data) {
+for (auto line : std::views::split(data, '\n') |
std::views::filter([](auto const& line) { return !line.empty(); })) {
+auto values = std::views::split(line, ' ');
+auto it = values.begin();
+std::size_t left = std::stol(std::string((*it).data(),
(*it).size()));
+it = std::next(it);
+std::size_t right = std::stol(std::string((*it).data(),
(*it).size()));
+it = std::next(it);
+
[clang] [libc++] Add assertions for potential OOB reads in std::nth_element (PR #67023)
danlark1 wrote: >Also @danlark1 if you rebase onto main the issues with macOS in the CI should >be fixed now. @ldionne, Done https://github.com/llvm/llvm-project/pull/67023 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang-tools-extra] [libc++] Add assertions for potential OOB reads in std::nth_element (PR #67023)
danlark1 wrote: >Also @danlark1 if you rebase onto main the issues with macOS in the CI should >be fixed now. @ldionne, Done https://github.com/llvm/llvm-project/pull/67023 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
