SDL_qsort stack buffer overflow with non-transitive comparison function about sdl HOT 8 CLOSED

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.

from sdl.

@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).

from sdl.

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

from sdl.

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

from sdl.

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) {

from sdl.

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

from sdl.

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

from sdl.

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)

from sdl.