Segfault when trying to dynamicaly realocate a 2 dimensional array

Question

I'm working on a system that has several structs area that interact with each other, the areas are stored in a regular array called storage, which is dynamically reallocated whenever you need to add or remove them. The way I'm handling the interactions is with a 2-dimensional array called overlap, that stores 1 byte values. There are a column and a row for every single element of the storage. The value at overlap[x][y] represents the interaction that the element storage[x] had with the element storage[y].

The areas also have layers and layerMasks that control with which elements they can interact. For example, an area in layer 1 with the masks 2, 3, and 4. May interact only with areas in the layer 2, 3 and 4. And can only be interacted with by areas with mask 1. The layers range from 0 to 63.

In order to do this, I need to position the areas inside the storage and overlap in a way that I'll be able to distinguish the layers, and for that, I'll be using the array sPosthat stands for storage position. This array will have 65 elements, one for each layer plus one. The values in sPos are the position of the first area in the storage that is in a layer equal or bigger than the sPos' value's index, and sPos[64] is the size of the storage.

This is how I'm handling things:

area * addArea(area * toAdd) {
// realocating the storage and overlap.
    storage = realloc(storage, sizeof(area *) * (sPos[64] + 1));
    if (!storage) {error handling} // Error handling is a printf("addArea\n") and a return NULL.
    
    overlap = realloc(overlap, sizeof(unsigned char *) * (sPos[64] + 1));                       
    if (!overlap) {error handling}

// Realloc works as malloc for NULL pointers, so setting this to NULL will allocate it when reallocating the rows.
    overlap[sPos[64]] = NULL;      

// Moving the elements in layers greater than or equal to toAdd->layer.
    for (int i = sPos[64]; i > sPos[toAdd->layer]; i--) overlap[i + 1] = overlap[i];                                              
    
// reallocating the rows of the overlap, and moving their elements as well.
    for (int i = 0; i < sPos[64]; i++) {                                                 
        overlap[i] = realloc(overlap[i], sizeof(unsigned char) * sPos[64] + 1);
        if (!overlap[i]) {error handling}
        
        for (int j = sPos[64]; j > sPos[toAdd->layer]; j--) overlap[i][j + 1] = overlap[i][j];
    }

// Seting the new elements of overlap to 0 (no interaction).
    for (int i = 0; i <= sPos[64]; i++) {
        overlap[sPos[toAdd->layer]][i] = 0;
        overlap[i][sPos[toAdd->layer]] = 0;
    }

// Moving the elements in storage to place toAdd in the position sPos[toAdd->layer]
    for (int i = sPos[64]; i > sPos[toAdd->layer]; i--) storage[i] = storage[i - 1]; 
    
    storage[sPos[toAdd->layer]] = toAdd;

// Adding 1 to every element of sPos with an index greater than toAdd->layer.
    for (int i = toAdd->layer + 1; i <= 64; i++) sPos[i]++;
    
    return toAdd; // returns the argument, or NULL in case of error.
}

When adding areas with different layers, nothing bad seems to happen. But when I try to add areas in the same layer I get a segfault with no error warnings called. usually when having 4 or more elements and trying to add one in an occupied layer.

Using gdb, I figured that the error happens when reallocating the rows of overlap, but I can't quite understand why.

Answer 1

First, to improve the readability and debuggability of your code, don't try to inline a statement on the same line as a for-loop declaration.

That is, don't do this:

for (int i = 0; i < N; i++) doSomething(i);

Do this:

for (int i = 0; i < N; i++) {
    doSomething(i);
}

The above is just plain easier to use when stepping through in the debugger line by line.

Back to the original problem at hand. Your memory corruption issue.

You allocated this:

overlap = realloc(overlap, sizeof(Unsigned char *) * (sPos[64] + 1));

Let's imagine sPos[64] was equal to 10. Therefore you allocated 10+1 == 11 bytes.

Thus, valid array index values for overlap are from [0..10] inclusive.

Then you initialize your array as follows:

for (int i = sPos[64]; i > sPos[toAdd->layer]; i--) {
    overlap[i + 1] = overlap[i]; 
}

The first statement executed within the for loop would then be:

overlap[11] = overlap[10];

Oops! overlap[11] is out of range. Hence, undefined behavior when you write to that memory location. You probably corrupted the heap.

You probably want to something like this instead (I'm making assumptions about what you are really trying to do)

int lastIndex = sPos[64];
int firstIndex = toAdd->layer + 1;
for (int i = lastIndex; i >= firstIndex; i--) {
    overlap[i] = overlap[i-1]; 
}

Also, you could use memmove to do this work for you, provided you calculate the pointer math correctly. (Again, I'm making assumptions on your array boundaries):

memmove(overlap+firstIndex+1, overlap+firstInex, lastIndex-firstIndex);

I'm also going to point out that when you attempt to do this array shift to the right, there's absolutely no guarantee that overlap[i-1] doesn't point to garbage. If your realloc size is less than or equal to the original allocated length of that array, you're fine. But if it's "growing" the array, you should assume that realloc returned a completely new array and the original overlap array has been trashed.

My overall advice is for you to be cognizant of what the valid array indices are for each array you have allocated when you use them in a loop. It's quite possible this isn't your only "off by 1 error".