Give up on qsort for sk_FOO_sort
OpenSSL's API constraints are such that sk_FOO_sort must take a
comparison function of type
int (*cmp)(const FOO *const *a, const FOO *const *b)
However qsort expects a comparison function of type
int (*cmp)(const void *a, const void *b)
In C, it is UB to cast a function pointer to a different type and call
it, even if the underlying calling conventions are the same. Moreover,
as qsort doesn't take a context parameter on its comparisons, we cannot
do the usual convention with closures in C.
qsort_r and qsort_s would avoid this, but they are unusable. Too many
libcs don't have them, and those that do define them inconsistently. See
https://stackoverflow.com/a/39561369
It seems this UB has finally hit a sanitizer in fxbug.dev/128274.
Irritating as it is to not even have a working sort function, I think
the easiest option is to just give up on qsort. As we did with bsearch
in https://boringssl-review.googlesource.com/c/boringssl/+/35304, just
implement an in-place heap sort ourselves.
Bug: fxbug.dev/128274
Change-Id: I9de6b4018bf635da0d0c5a680bd7811d297b0bb3
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/60507
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Bob Beck <bbe@google.com>
diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c
index a11533e..6b4f8bc 100644
--- a/crypto/stack/stack.c
+++ b/crypto/stack/stack.c
@@ -393,20 +393,52 @@
return NULL;
}
-#if defined(_MSC_VER)
-struct sort_compare_ctx {
- OPENSSL_sk_call_cmp_func call_cmp_func;
- OPENSSL_sk_cmp_func cmp_func;
-};
-
-static int sort_compare(void *ctx_v, const void *a, const void *b) {
- struct sort_compare_ctx *ctx = ctx_v;
- // |a| and |b| point to |void*| pointers which contain the actual values.
- const void *const *a_ptr = a;
- const void *const *b_ptr = b;
- return ctx->call_cmp_func(ctx->cmp_func, *a_ptr, *b_ptr);
+static size_t parent_idx(size_t idx) {
+ assert(idx > 0);
+ return (idx - 1) / 2;
}
-#endif
+
+static size_t left_idx(size_t idx) {
+ // The largest possible index is |PTRDIFF_MAX|, not |SIZE_MAX|. If
+ // |ptrdiff_t|, a signed type, is the same size as |size_t|, this cannot
+ // overflow.
+ assert(idx <= PTRDIFF_MAX);
+ static_assert(PTRDIFF_MAX <= (SIZE_MAX - 1) / 2, "2 * idx + 1 may oveflow");
+ return 2 * idx + 1;
+}
+
+// down_heap fixes the subtree rooted at |i|. |i|'s children must each satisfy
+// the heap property. Only the first |num| elements of |sk| are considered.
+static void down_heap(OPENSSL_STACK *sk, OPENSSL_sk_call_cmp_func call_cmp_func,
+ size_t i, size_t num) {
+ assert(i < num && num <= sk->num);
+ for (;;) {
+ size_t left = left_idx(i);
+ if (left >= num) {
+ break; // No left child.
+ }
+
+ // Swap |i| with the largest of its children.
+ size_t next = i;
+ if (call_cmp_func(sk->comp, sk->data[next], sk->data[left]) < 0) {
+ next = left;
+ }
+ size_t right = left + 1; // Cannot overflow because |left < num|.
+ if (right < num &&
+ call_cmp_func(sk->comp, sk->data[next], sk->data[right]) < 0) {
+ next = right;
+ }
+
+ if (i == next) {
+ break; // |i| is already larger than its children.
+ }
+
+ void *tmp = sk->data[i];
+ sk->data[i] = sk->data[next];
+ sk->data[next] = tmp;
+ i = next;
+ }
+}
void OPENSSL_sk_sort(OPENSSL_STACK *sk,
OPENSSL_sk_call_cmp_func call_cmp_func) {
@@ -415,25 +447,25 @@
}
if (sk->num >= 2) {
-#if defined(_MSC_VER)
- // MSVC's |qsort_s| is different from the C11 one.
- // https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/qsort-s?view=msvc-170
- struct sort_compare_ctx ctx = {call_cmp_func, sk->comp};
- qsort_s(sk->data, sk->num, sizeof(void *), sort_compare, &ctx);
-#else
- // sk->comp is a function that takes pointers to pointers to elements, but
- // qsort take a comparison function that just takes pointers to elements.
- // However, since we're passing an array of pointers to qsort, we can just
- // cast the comparison function and everything works.
- //
- // TODO(davidben): This is undefined behavior, but the call is in libc so,
- // e.g., CFI does not notice. |qsort| is missing a void* parameter in its
- // callback, while no one defines |qsort_r| or |qsort_s| consistently. See
+ // |qsort| lacks a context parameter in the comparison function for us to
+ // pass in |call_cmp_func| and |sk->comp|. While we could cast |sk->comp| to
+ // the expected type, it is undefined behavior in C can trip sanitizers.
+ // |qsort_r| and |qsort_s| avoid this, but using them is impractical. See
// https://stackoverflow.com/a/39561369
- int (*comp_func)(const void *, const void *) =
- (int (*)(const void *, const void *))(sk->comp);
- qsort(sk->data, sk->num, sizeof(void *), comp_func);
-#endif
+ //
+ // Use our own heap sort instead. This is not performance-sensitive, so we
+ // optimize for simplicity and size. First, build a max-heap in place.
+ for (size_t i = parent_idx(sk->num - 1); i < sk->num; i--) {
+ down_heap(sk, call_cmp_func, i, sk->num);
+ }
+
+ // Iteratively remove the maximum element to populate the result in reverse.
+ for (size_t i = sk->num - 1; i > 0; i--) {
+ void *tmp = sk->data[0];
+ sk->data[0] = sk->data[i];
+ sk->data[i] = tmp;
+ down_heap(sk, call_cmp_func, 0, i);
+ }
}
sk->sorted = 1;
}
diff --git a/crypto/stack/stack_test.cc b/crypto/stack/stack_test.cc
index 7900fc9..228182b 100644
--- a/crypto/stack/stack_test.cc
+++ b/crypto/stack/stack_test.cc
@@ -24,6 +24,7 @@
#include <gtest/gtest.h>
#include <openssl/mem.h>
+#include <openssl/rand.h>
// Define a custom stack type for testing.
@@ -481,3 +482,38 @@
sk_TEST_INT_set_cmp_func(sk.get(), nullptr);
EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
}
+
+TEST(StackTest, Sort) {
+ constexpr size_t kMaxLength = 100;
+ constexpr int kIterations = 500;
+ for (size_t len = 0; len < kMaxLength; len++) {
+ SCOPED_TRACE(len);
+ for (int iter = 0; iter < kIterations; iter++) {
+ // Make a random input list.
+ std::vector<int> vec(len);
+ RAND_bytes(reinterpret_cast<uint8_t *>(vec.data()),
+ sizeof(int) * vec.size());
+ SCOPED_TRACE(testing::PrintToString(vec));
+
+ // Convert it to a |STACK_OF(TEST_INT)|.
+ bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
+ ASSERT_TRUE(sk);
+ for (int v : vec) {
+ auto value = TEST_INT_new(v);
+ ASSERT_TRUE(value);
+ ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
+ }
+
+ // Sort it with our sort implementation.
+ sk_TEST_INT_sort(sk.get());
+ std::vector<int> result;
+ for (const TEST_INT *v : sk.get()) {
+ result.push_back(*v);
+ }
+
+ // The result must match the STL's version.
+ std::sort(vec.begin(), vec.end());
+ EXPECT_EQ(vec, result);
+ }
+ }
+}
