C - Function call itself causes segfault in recursive calls

Question

Im fighting a segfault error that I can't understand : I have a recursive function that expands on an array representing pixels : starting on an index, it exepands around the index to create groups of pixels by calling the same function left right up and down (aka index -1, index +1...). For debuging purposes, I have a printf call at the very first line of the function, and one just before each of the 4 recursive calls. What I dont get is, I end up with a segfault during the recursion at the recrusive call itself (I get the print that is just before the call, but not the one at function start).

void explore(Pixel * array, int j, Tache * cur_pound, int * it, Pixel previous){
    printf("%d\n", j); // I DONT GET THIS PRINT AT LAST RECURSIVE CALL
    // out of bounds
    if(j > sizeX * sizeY)
        return;

    // allready explored index
    if(array[j].explored == 1){
        return;
    }

   // to big of a color difference between this pixel and the reference one
   if(abs((int)array[j].r - previous.r) > SEUIL || abs((int)array[j].g - previous.g) > SEUIL || abs((int)array[j].b - previous.b) > SEUIL){
      return;
   }

   array[j].explored = 1;
   cur_pound->limits[* it] = j;
   (* it)++;

  // recursion
  if(j +1 < sizeX * sizeY && array[j+1].explored != 1){
        printf("before SF\n); // I GET THIS PRINTF
        explore(array, j + 1, cur_pound, it, previous);
  }
  // 3 other recursive calls removed for simplicity here
}

About my data structures : a Tache * is struct that contains 3 GLubytes and limits, an int * that represents every pixel index that belongs to this group. A Pixel contains 3 GLubytes and a char that represents if this pixel has already been visited by the function. The array given to the function as the first argument is an array of Pixel that represent my image. it is an int representing the index in the group so that my function knows where on the array it should add a new index. Limits are initialised at -1 outside this function and are allocated with malloc(size * sizeof(int)) where size is the width of the image multiplied by its height.

This is how the inital call is done :

void taches_de_couleur(Image *i){
    int j, k, y, size, it;
    GLubyte * im;
    Pixel * array;

    sizeX = i->sizeX;
    sizeY = i->sizeY;  
    k = 0;
    size = sizeX * sizeY;
    array = malloc(size * sizeof(Pixel));
    im = i->data;

   /* build the array from image data */
   for(j = 0; j < 3 * size; j+= 3){
       array[k].explored = 0;
       array[k].r = i->data[j];
       array[k].g = i->data[j + 1];
       array[k].b = i->data[j + 2];
       k++;
    }

    Tache * new_pound;
    new_pound = malloc(sizeof(Tache));
    new_pound->limits = malloc(size * sizeof(int));
    int x= 0;
    while(x < size){
        new_pound->limits[x] = -1;
        x++;
    }
    it = 0;
    explore(array, 0, new_pound, &it, array[0]);
}

Note that the program does not produce any SF when working with small images (biggest i could do was 512x384px). This thing has been giving me a headache for a week now, can't figure out what is causing this segfault and thats why im asking you guys if you can see anything obvious here. I can add the second function that calls explore if need be, but this part seems to be good.

EDIT : this is the output gdb gives me when I run it with a image too big :

Thread 1 "palette" received signal SIGSEGV, Segmentation fault.
0x00007ffff7b730be in __GI___libc_write (fd=1, buf=0x555555592770, 
nbytes=7)
at ../sysdeps/unix/sysv/linux/write.c:26
26  ../sysdeps/unix/sysv/linux/write.c: No such file or directory.

EDIT : Since im failing to provide enough ressources, see https://github.com/BruhP8/TachesDeCouleur for the full project Thanks in advance

Answer 1

What I dont get is, I end up with a segfault during the recursion at the recrusive call itself (I get the print that is just before the call, but not the one at function start).

That is an almost sure sign of stack exhaustion.

Run your program under debugger, and examine the instruction which causes segfault. Chances are, it will be one of stack manipulation instructions (CALL, PUSH), or a stack dereference instruction that follows stack decrement. You can also look at the value of $SP register, and compare it to the bounds of stack segment (from /proc/$pid/maps if you are on Linux).

The code you've shown does not appear to allocate any stack, so the problem is likely in the code you omitted.

Note that the program does not produce any SF when working with small images

That is another sign: you are probably allocating a new image on the stack, and the larger the image, the fewer levels of recursion you can achieve.

P.S. On Linux, default stack size is often 8MiB. Try ulimit -s unlimited -- if that allows the program to recur deeper, that would be a sure sign that my guess is correct. But don't use ulimit -s unlimited as a fix (it's not).

Update:

With the full source code, I was able to build the palette program. Each recursive call to explore only takes 48 bytes of stack (which isn't much).

But with default 8MiB stack, that limits the total recursion to (8 << 20) / 48 == 174762 levels deep.

TL;DR: if your recursive procedure requires one level of recursion per pixel, then you would not be able to process large images. You must rewrite the procedure to be iterative instead.

Answer 2

It seems the first boundary check in your code should be:

if( j >= sizeX * sizeY )

and not

if( j > sizeX * sizeY )

(As the last element of your array is array[size - 1] and not array[size])