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>

crypto/stack/stack.c

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;
 }

crypto/stack/stack_test.cc

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);
+    }
+  }
+}