SDL_qsort stack buffer overflow with non-transitive comparison function

[aikawayataro]

When using SDL_qsort with a non-transitive compare function, it is likely to cause a stack buffer overflow:
(taken from https://discourse.libsdl.org/t/sdl-rand-and-sigsev/52111)

#include <SDL3/SDL.h>

#define array_len 100

static int num_compare(const void *_a, const void *_b)
{
    int a = *((int *) _a);
    int b = *((int *) _b);
    return (a > b); // non-transitive
}

int main(int argc, char *argv[])
{
    int nums[array_len];
    for (int i = 0; i < array_len; i++) {
      nums[i] = (int)SDL_rand();
    }

    SDL_qsort(nums, array_len, sizeof (int), num_compare);

    for (int i = 0; i < array_len; i++) {
      SDL_Log("%i", nums[i]);
    }
    return 0;
}

./a.out
*** stack smashing detected ***: terminated
Aborted (core dumped)

The solution is to update the qsort implementation to https://www.mccaughan.org.uk/software/qsort.c-1.16 , which fixes the problem.

[sechshelme]

I just tested it, the error still exists.
The pure C version works.

Linux 64bit

// gcc main.c -o main

#include <stdio.h>
#include <stdlib.h>

#define array_len 100

static int num_compare(const void *_a, const void *_b)
{
    int a = *((int *) _a);
    int b = *((int *) _b);
    return (a > b); // non-transitive
}

int main(int argc, char *argv[])
{
    srand(time(NULL)); 

    int nums[array_len];
    for (int i = 0; i < array_len; i++) {
      nums[i] = (int)rand();
    }

    qsort(nums, array_len, sizeof (int), num_compare);

    for (int i = 0; i < array_len; i++) {
      printf("%i\n", nums[i]);
    }
    return 0;
}

[aikawayataro]

@sechshelme can you test with this patch?

diff --git a/src/stdlib/SDL_qsort.c b/src/stdlib/SDL_qsort.c
index c6a06dde9..a6e91fa61 100644
--- a/src/stdlib/SDL_qsort.c
+++ b/src/stdlib/SDL_qsort.c
@@ -506,7 +506,7 @@ fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)
     /* Find the right place for |first|. My apologies for var reuse */
     int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
     *(int*)pivot=*(int*)first;
-    for (;compare(userdata,pl,pivot)>0;pr=pl,--pl) {
+    for (;pl > (int*)base && compare(userdata,pl,pivot)>0;pr=pl,--pl) {
       *pr=*pl; }
     if (pr!=(int*)first) *pr=*(int*)pivot;
   }

[sechshelme]

Since the version on git is (still) too old, I added it myself.
The error seems to have gone away.

//    for (;compare(userdata,pl,pivot)>0;pr=pl,--pl) {
 for (;pl > (int*)base && compare(userdata,pl,pivot)>0;pr=pl,--pl) {

[sezero]

Can you make that into a pull request so that it gets reviewed and merged?

[aikawayataro]

Of course, but first I want to run some tests to make sure it doesn't break anything

[aikawayataro]

During testing, I found the same problem with out-of-bounds access in the Insertion macro (used by qsort_r_aligned and qsort_r_unaligned, but not by qsort_r_words).
I will submit a fix a bit later, I want to fuzz it to make sure nothing gets out of sight.

[DanielGibson]

That fix in upstream qsort 1.16 was about recursing on the smaller or bigger partition - that can prevent stack overflows, but only in very large arrays.
With only 50 or 100 elements, like in the case this bugreport is about, it doesn't matter what partition you recurse on, a callstack depth of 100 or so won't overflow it (on modern operating systems the stack usually is 8MB, on Windows it's 1MB and even that is more than enough for this usecase)

[aikawayataro]

@DanielGibson that's right! I was wrong when I debugged this change. (For some unknown reason, it was fixed for me, but fuzzing revealed the real problem see #10066).