Thread: This code gives rise to segmentation fault

The following program is supposed to solve the coast problem:

Code:

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

bool **worldArray;
bool **removalMask;
bool **floodArray;
int nRows, nCols;
char *inputRow;

typedef struct {
    int x;
    int y;
} Pixel;

void allocateMemory();
void extractInput();
void resetMask();

int QUEUE_LENGTH = 10000;
Pixel *floodQueue;
int startQueue;
int maxQueue;
int endQueue;
void requeue();
void pushQueue(Pixel element);
Pixel popQueue();

void maskOcean(int row, int col);
bool isToBeMasked(int row, int col);

int evaluateCoastLength();



int main(int argc, const char * argv[]) {
    if(scanf("%d%d", &nRows, &nCols) == 2) {
        allocateMemory();
        extractInput();
        resetMask();
    } else {
        printf("Invalid map size!\n\n");
        return -1;
    }
    maskOcean(0,0);

    printf("%d\n", evaluateCoastLength());
    
    for (int i = 0; i < nRows + 2; ++i) {
        free(worldArray[i]);
        free(floodArray[i]);
        free(removalMask[i]);
    }
    free(floodQueue);
    free(floodArray);
    free(worldArray);
    free(removalMask);
    
    return 0;
}



void allocateMemory() {
    worldArray = (bool **) malloc((nRows + 2)* sizeof(bool *));
    removalMask = (bool **) malloc((nRows + 2)* sizeof(bool *));
    floodArray = (bool **) malloc((nRows + 2)* sizeof(bool *));
    floodQueue = (Pixel *) malloc(QUEUE_LENGTH * sizeof(Pixel));
    startQueue = 0;
    endQueue = 0;
    maxQueue = QUEUE_LENGTH - 1;
    for(int i = 0; i <= nRows + 1; ++i) {
        worldArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
        floodArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
        removalMask[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
    }
}

void extractInput() {
    for(int row = 0; row < nRows; ++row) {
        inputRow = (char *) malloc (nCols * sizeof(char));
        if(!(scanf("%s", inputRow))) {
            printf("Input error!\n");
        }
        for(int col = 0; col < nCols; ++col) {
            if(inputRow[col] == '0')
                worldArray[row+1][col+1] = false;
            else
                worldArray[row+1][col+1] = true;
        }
        // Zeros along vertical borders
        worldArray[row+1][nCols+1] = false;
        worldArray[row+1][0] = false;
        free(inputRow);
    }
    // Zeros along horizontal borders
    for(int col = 0; col <= nCols+1; ++col) {
        worldArray[0][col] = false;
        worldArray[nRows+1][col] = false;
    }
}

void resetMask() {
    for(int i = 0; i <= nRows+1; ++i)
        for(int j = 0; j <= nCols+1; ++j) {
            removalMask[i][j] = false;
            floodArray[i][j] = false;
        }
}

int evaluateCoastLength() {
    int numSegs = 0;
    for(int row = 0; row < nRows + 1; ++row)
        for(int col = 0; col < nCols+1; ++col)
            if(removalMask[row][col] != removalMask[row][col+1])
                ++numSegs;
    for(int col = 0; col < nCols + 1; ++col)
        for(int row = 0; row < nRows+1; ++row)
            if(removalMask[row][col] != removalMask[row+1][col])
                ++numSegs;
    return numSegs;
}

void requeue() {
    if(startQueue > 0) {
        int counter = 0;
        for (int i = startQueue; i < endQueue; ++i)
            floodQueue[counter++] = floodQueue[i];
        startQueue = 0;
        endQueue = counter;
    }
}

void pushQueue(Pixel element) {
    for(int q = startQueue; q < endQueue; ++q)
       if(element.x == floodQueue[q].x)
          if(element.y == floodQueue[q].y)
             return;
    if(endQueue == maxQueue) {
        if(startQueue == 0)
            popQueue();
        requeue();
    }
    floodQueue[endQueue] = element;
    ++endQueue;
}

Pixel popQueue() {
    if(startQueue < endQueue) {
        ++startQueue;
        return floodQueue[startQueue -1];
    } else {
        printf("Empty queue, popQueue() abuse!\n");
        Pixel nonPixel;
        nonPixel.x = -1;
        nonPixel.y = -1;
        return nonPixel;
    }
}

void maskOcean(int row, int col) {
    Pixel pushElement;
    pushElement.x = row;
    pushElement.y = col;
    pushQueue(pushElement);
    while(startQueue < endQueue) {
        Pixel popElement;
        popElement = popQueue();
        removalMask[popElement.x][popElement.y] = true;
        int offset[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0;i < 4;++i) {
            if(isToBeMasked(popElement.x + offset[i][0], popElement.y + offset[i][1])) {
                pushElement.x = popElement.x + offset[i][0];
                pushElement.y = popElement.y + offset[i][1];
                pushQueue(pushElement);
            }
        }
    }
}
bool isToBeMasked(int row, int col) {
    if((row >= 0)&&(row<=nRows+1))
        if((col >= 0)&&(col<=nCols+1))
            return !(worldArray[row][col]) && !removalMask[row][col];
    return false;
}

The data-file to be evaluated may look like so:

PHP Code:

10 10
0100010100
0111001100
1000110010
0011100011
0111111110
0100000010
0111110000
0000011000
0111110000
0000000100 


A typical run is done by having that matrix in a text file and running:

coastProgram < dataFile.txt

So this is supposed to look like an archipelago where the 1s denote land and 0s denote water. These elements are shaped as squares in a grid and the length of the coastline is to be evaluated with lakes inside the landmasses omitted. The grid size varies between 1x1 and 1000 x 1000.

I think I have solved the problem and it does the job on all the data I have tried.

But there is some data where it crashes with a segmentation fault. I don't have access to that data unfortunately. Does anyone know what potential weakness in the code that may give rise to the segmentation fault?

It works for the most part in a Linux environment using gcc but crashes almost all the time in Visual Studio 2013.

A quick look suggests you may not be respecting your borders.
Should the initial maskOcean call be 0,0?
Should the evaluateCoastLength function be starting row and col at 0?

I'm unable to troubleshoot with the debugger because I don't have access to the data that gives rise to the exception. The program is compiled and tested on a website and all you get is whether it failed or succeeded on the tests (26 of them).

So instead of

Code:

bool **worldArray;
    worldArray = (bool**) malloc((nRows + 2)* sizeof(bool*));
       for(int i = 0; i <= nRows + 1; ++i)
            worldArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
...

I should use:

Code:

bool **worldArray;
bool (*worldArray)[nRows+2] = malloc(sizeof * bool[nRows+2] * (nCols+2)));
...

?

Originally Posted by bot

The program is compiled and tested on a website

Can you give a link to the problem description on the website?
(And did you see my previous post?)

Originally Posted by john.c

A quick look suggests you may not be respecting your borders. Should the initial maskOcean call be 0,0? Should the evaluateCoastLength function be starting row and col at 0?

The variables nRows and nCols are the number of rows and columns of the map that is fed into the program. I let the program surround the the map with a border of 0's. So the actual matrix has (nRows+2) x (nCols+2) elements. The 0's mean that it starts from index 0. The 2Dimensional arrays have indices ranging from 0 to nCols+1 and 0 to nRows+1 respectively.

The program should respect these boundaries, the routine:

Code:

bool isToBeMasked(int row, int col) {
    if((row >= 0)&&(row<=nRows+1))
        if((col >= 0)&&(col<=nCols+1))
            return !(worldArray[row][col]) && !removalMask[row][col];
    return false;
}

ensures that, and the routine

Code:

int evaluateCoastLength() {
    int numSegs = 0;
    for(int row = 0; row < nRows + 1; ++row)
        for(int col = 0; col < nCols+1; ++col)
            if(removalMask[row][col] != removalMask[row][col+1])
                ++numSegs;
    for(int col = 0; col < nCols + 1; ++col)
        for(int row = 0; row < nRows+1; ++row)
            if(removalMask[row][col] != removalMask[row+1][col])
                ++numSegs;
    return numSegs;
}

only goes to nCols+1 because it compares element i with element i+1. It counts edges between land and water by sweeping horizontally and vertically on the masked coast that is generated by a flood fill algorithm.

Taking a closer look this time, I note that you are making inputRow 1 char too small. Since you're reading it as a string, it needs a space for the terminating '\0'.

Originally Posted by bot

I find it rather strange that it doesn't crash consistently in a Linux environment.

It's a mystery! And a pain in the, well, just a pain.

You probably want to malloc inputRow before the loop and free it afterwards. And you may as well make it local. You should, of course, make pretty much all of your variables local, but you probably know that. And we often use shortcuts when solving programming contest problems.

You can allocate your 2D arrays more efficiently like this (allocating the data portion contiguously and then assigning the row pointers). And by callocing the data, you don't need to manually zero out the worldArray border (or "reset" floodArray and removalMask).

Code:

void allocateMemory() {
    floodQueue = malloc(QUEUE_LENGTH * sizeof *floodQueue);
    startQueue = 0;
    endQueue = 0;
    maxQueue = QUEUE_LENGTH - 1;

    int NROWS = nRows + 2, NCOLS = nCols + 2;
    worldArray = malloc(NROWS * sizeof *worldArray); // row pointer array
    worldArray[0] = calloc(NROWS * NCOLS, sizeof *worldArray[0]); // data
    floodArray = malloc(NROWS * sizeof *floodArray);
    floodArray[0] = calloc(NROWS * NCOLS, sizeof *floodArray[0]);
    removalMask = malloc(NROWS * sizeof *removalMask);
    removalMask[0] = calloc(NROWS * NCOLS, sizeof *removalMask[0]);
    for(int i = 1; i < NROWS; ++i) { // assign row pointers
        worldArray[i] = worldArray[i - 1] + NCOLS;
        floodArray[i] = floodArray[i - 1] + NCOLS;
        removalMask[i] = removalMask[i - 1] + NCOLS;
    }
}

Then in main, you free them like this:

Code:

    free(worldArray[0]);  // free data
    free(worldArray);     // free row pointers
    free(floodArray[0]);
    free(floodArray);
    free(removalMask[0]);
    free(removalMask);
    free(floodQueue);

Yes, I actually am in the process of optimizing the code. Something in the program that I was thinking that was using CPU cycles is the requeue() function. I was thinking that shuffling data back and forth all the time must cost CPU. So I tried instead to use something that looks like a ringbuffer instead, i.e. replacing popQueue(), pushQueue() and requeue() with:

Code:

int queueLength = 0;

void pushQueue(Pixel element) {
    for(int q = startQueue; q < startQueue + queueLength; ++q)
       if(element.x == floodQueue[q % maxQueue].x)
          if(element.y == floodQueue[q % maxQueue].y)
             return;
    floodQueue[endQueue] = element;
    endQueue = ++endQueue % maxQueue;
    if(queueLength == maxQueue)
       startQueue = ++startQueue % maxQueue;
    else
       ++queueLength;
}


Pixel popQueue() {
    if(queueLength > 0) {
       --queueLength;
       int popIndex = startQueue;
       startQueue = ++startQueue % maxQueue;
       return floodQueue[popIndex];
    } else {
        printf("Empty queue, popQueue() abuse!\n");
        Pixel nonPixel;
        nonPixel.x = -1;
        nonPixel.y = -1;
        return nonPixel;
    }
}

But that lowered performance instead. The first program takes 0.4 seconds to compute and with the replacement it now takes 2.4 seconds to compute! I don't understand the slowdown. It seems that frequent calls to the modulus operator hogs more CPU than calling to memory. I tried unwinding that for-loop that checks for element uniqueness in the queue, i.e.:

Code:

void pushQueue(Pixel element) {
    int queueExtension = startQueue + queueLength;
    if (queueExtension > maxQueue) {
       int endPoint = queueExtension % maxQueue;
        for(int q = startQueue; q < maxQueue; ++q)
           if(element.x == floodQueue[q].x)
              if(element.y == floodQueue[q].y)
                 return;
        for(int q = 0; q < endPoint; ++q)
           if(element.x == floodQueue[q].x)
              if(element.y == floodQueue[q].y)
                 return;
    else
        for(int q = startQueue; q < endQueue; ++q)
           if(element.x == floodQueue[q].x)
              if(element.y == floodQueue[q].y)
                 return;
    }
    floodQueue[endQueue] = element;
    endQueue = ++endQueue % maxQueue;
    if(queueLength == maxQueue)
       startQueue = ++startQueue % maxQueue;
    else
       ++queueLength;
}

and that improved performance back to 0.49s, which is still worse than the first program. I know that this problem can be solved with a performance of 0.02s and I am far from that

I will look into the malloc/calloc routines tomorrow. Yes, I was taking a few shortcuts. Other enhancements would also be to handle exceptions etc, but here we assume that the input is always correct and focus on performance only.

I think you should use

Code:

worldArray[i] = worldArray[i - 1 + NCOLS];

instead of

Code:

worldArray[i] = worldArray[i - 1] + NCOLS;

As I understand, 2-dimensional arrays are stored as a 1-dimensional vector in memory, so the contents of the next row is located at worldArray[i - 1 + NCOLS]. But I don't understand that assignment; by that logic worldArray[i - 1 + NCOLS] should be equal worldArray[i - 1 + 2 * NCOLS] and so on which doesn't make any sense to me. Perhaps the assignment should be worldArray[i] = &worldArray[i - 1] + NCOLS ? I'm a bit confused here.


Anyway, your modification compiles and runs fine in a Windows environment but not in a Linux environment (segmentation fault), I'm baffled!


I have rewritten the code, I have found that floodArray is no longer needed, it is a remnant from another algorithm that I used that traced boundaries, an algorithm that I scrapped. And I found that oceanArray is a better name than removalMask which is another remnant from when the world was analyzed island by island that were removed one by one as the program worked its way through the world.




But still, I assume that this only improves performance of the memory allocation and not the computations, should it work properly in that Linux environment.

Originally Posted by bot

I think you should use

Code:

worldArray[i] = worldArray[i - 1 + NCOLS];

instead of

Code:

worldArray[i] = worldArray[i - 1] + NCOLS;

No. It's correct the way I originally demonstrated. Try it on Linux that way and it shouldn't crash. Even on Windows it's still an error the way you're doing it, but I guess it just doesn't happen to access unallocated memory. Or, if you're using two different machines, one could be 64 bit (presumably the Linux) and the other 32-bit. That might make a difference.

In your previous code (that you may not be using anymore) you had a sequence point error (possible undefined behavior). You're not allowed to modify an object more than once per sequence point, but this does so twice:

Code:

    endQueue = ++endQueue % maxQueue;

It should be recoded as:

Code:

    endQueue = (endQueue + 1) % maxQueue;

Same with the two other similar lines.

The way you're handling queueLength looks a little fishy to me. When it reaches maxQueue, that would seem to be an unrecoverable error, but you adjust startQueue and keep going.

Anyway, you should maybe post your current code.

Sorry but it doesn't compile at all on any platform with "worldArray[i] = worldArray[i - 1] + NCOLS;", I hope you are aware that this is an array of booleans, not integers. I had a little hope to gain some performance and lower memory usage by using booleans but perhaps this is not the case eh? The Windows environment is 64-bit but I could launch a 32 bit environment. The Linux environment uses gcc version gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609 with the following flags:

Code:

-g -O2 -std=gnu99 -static {files} -lm

and I cannot change that.

Replacing lines containing "endQueue = ++endQueue % maxQueue;" with "endQueue = (endQueue + 1) % maxQueue;" didn't improve performance one bit.

I'm not sure what's so fishy about queueLength. I have defined startQueue as the index at which the first element in the queue resides and endQueue as the index at which the next element will be added when calling pushQueue(element). That way these indices will know where to be if the queue is empty; startQueue == endQueue either means that the queue is full or is empty. So instead of rearranging the queue to prevent indices from exceeding the limit as shown above, I let the indices spinning round round round like in a ring without really touching the elements in the queue. But invoking the modulus for each index in the uniqueness test seems to hog a lot of CPU cycles.

So the fastest version of my program looks like this:

Code:

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


bool **worldArray;
bool **oceanArray;
int nRows, nCols;
char *inputRow;


typedef struct {
    int x;
    int y;
} Pixel;


void allocateMemory();
void extractInput();
void resetMask();


int QUEUE_LENGTH = 757;
Pixel *floodQueue;
int startQueue;
int maxQueue;
int endQueue;
void requeue();
void pushQueue(Pixel element);
Pixel popQueue();


void maskOcean(int row, int col);
bool isToBeMasked(int row, int col);


int evaluateCoastLength();




int main(int argc, const char * argv[]) {
    if(scanf("%d%d", &nRows, &nCols) == 2) {
        allocateMemory();
        extractInput();
        resetMask();
    } else {
        printf("Invalid map size!\n\n");
        return -1;
    }
    maskOcean(0,0);


    printf("%d\n", evaluateCoastLength());
    
    for (int i = 0; i < nRows + 2; ++i) {
        free(worldArray[i]);
        free(oceanArray[i]);
    }
    free(floodQueue);
    free(worldArray);
    free(oceanArray);
    
    return 0;
}


void allocateMemory() {
    worldArray = (bool **) malloc((nRows + 2)* sizeof(bool *));
    oceanArray = (bool **) malloc((nRows + 2)* sizeof(bool *));
    floodQueue = (Pixel *) malloc(QUEUE_LENGTH * sizeof(Pixel));
    startQueue = 0;
    endQueue = 0;
    maxQueue = QUEUE_LENGTH - 1;
    for(int i = 0; i <= nRows + 1; ++i) {
        worldArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
        oceanArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
    }
}


void extractInput() {
    for(int row = 0; row < nRows; ++row) {
        inputRow = (char *) malloc ((nCols + 1) * sizeof(char));
        if(!(scanf("%s", inputRow))) {
            printf("Input error!\n");
        }
        for(int col = 0; col < nCols; ++col) {
            if(inputRow[col] == '0')
                worldArray[row+1][col+1] = false;
            else
                worldArray[row+1][col+1] = true;
        }
        // Zeros along vertical borders
        worldArray[row+1][nCols+1] = false;
        worldArray[row+1][0] = false;
        free(inputRow);
    }
    // Zeros along horizontal borders
    for(int col = 0; col <= nCols+1; ++col) {
        worldArray[0][col] = false;
        worldArray[nRows+1][col] = false;
    }
}


void resetMask() {
    for(int i = 0; i <= nRows+1; ++i)
        for(int j = 0; j <= nCols+1; ++j) {
            oceanArray[i][j] = false;
        }
}


int evaluateCoastLength() {
    int numSegs = 0;
    for(int row = 0; row < nRows + 1; ++row)
        for(int col = 0; col < nCols+1; ++col)
            if(oceanArray[row][col] != oceanArray[row][col+1])
                ++numSegs;
    for(int col = 0; col < nCols + 1; ++col)
        for(int row = 0; row < nRows+1; ++row)
            if(oceanArray[row][col] != oceanArray[row+1][col])
                ++numSegs;
    return numSegs;
}


void requeue() {
    if(startQueue > 0) {
        int counter = 0;
        for (int i = startQueue; i < endQueue; ++i)
            floodQueue[counter++] = floodQueue[i];
        startQueue = 0;
        endQueue = counter;
    }
}


void pushQueue(Pixel element) {
    for(int q = startQueue; q < endQueue; ++q)
       if(element.x == floodQueue[q].x)
          if(element.y == floodQueue[q].y)
             return;
    if(endQueue == maxQueue) {
        if(startQueue == 0)
            popQueue();
        requeue();
    }
    floodQueue[endQueue] = element;
    ++endQueue;
}


Pixel popQueue() {
    if(startQueue < endQueue)
        return floodQueue[startQueue++];
    else {
        printf("Empty queue, popQueue() abuse!\n");
        Pixel nonPixel;
        nonPixel.x = -1;
        nonPixel.y = -1;
        return nonPixel;
    }
}


void maskOcean(int row, int col) {
    Pixel pushElement;
    pushElement.x = row;
    pushElement.y = col;
    pushQueue(pushElement);
    while(startQueue < endQueue) {
        Pixel popElement;
        popElement = popQueue();
        oceanArray[popElement.x][popElement.y] = true;
        int offset[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0;i < 4;++i) {
            if(isToBeMasked(popElement.x + offset[i][0], popElement.y + offset[i][1])) {
                pushElement.x = popElement.x + offset[i][0];
                pushElement.y = popElement.y + offset[i][1];
                pushQueue(pushElement);
            }
        }
    }
}
bool isToBeMasked(int row, int col) {
    if((row >= 0)&&(row<=nRows+1))
        if((col >= 0)&&(col<=nCols+1))
            return !(worldArray[row][col]) && !oceanArray[row][col];
    return false;
}

I have made the queue length as small as possible. In order to use my ring buffer instead, remove the functions requeue(), popQueue() and pushQueue() and replace them with the functions in the first textbox in post #11 at the end. You may want to declare an int named queueLength = 0 at the top of the code. If you want to improve the ringbuffer as discussed, then replace the pushQueue() function with the function in the second textbox of post #11.

The new method of allocating memory looks like so:

Code:

...

bool **worldArray;
bool **oceanArray;
int nRows, nCols;

...


int main(int argc, const char * argv[]) {
    if(scanf("%d%d", &nRows, &nCols) == 2) {
        allocateMemory();


    ...
    
    printf("%d\n", evaluateCoastLength());
    
    free(worldArray[0]);
    free(oceanArray[0]);
    free(floodQueue);
    free(worldArray);
    free(oceanArray);
    
    return 0;
}

void allocateMemory() {
   int NROWS = nRows + 2, NCOLS = nCols + 2;
    worldArray = malloc(NROWS * sizeof *worldArray);
    worldArray[0] = malloc(NROWS * NCOLS, sizeof *worldArray[0]);
    oceanArray = malloc(NROWS * sizeof *oceanArray);
    oceanArray[0] = calloc(NROWS * NCOLS, sizeof *oceanArray[0]);
    
    startQueue = 0;
    endQueue = 0;
    maxQueue = QUEUE_LENGTH - 1;
    for(int i = 0; i < NROWS; ++i) {
        worldArray[i] = worldArray[i - 1 + NCOLS];
        oceanArray[i] = oceanArray[i - 1 + NCOLS];
    }
}

(no need to calloc the worldArray as it will be filled with data anyway, only the surrounding border indices need to. The oceanArray otoh needs to...)

Some relevant testdata can be found in the following beezipped tarball:

http://challenge.csc.kth.se/2011/testdata.tar.bz2

I never said that correcting the sequence point error would improve performance. It simply makes your program correct, if that kind of thing matters to you.

Obviously the change that you made could not possibly degrade performance as much as you say. The degradation must be due to something else. The only way I could possibly tell is if you posted both versions of your code.

I realize the queue is a ring buffer. But queueLength is apparently the total number of queue elements that are in use. If it is equal to queueSize then the queue is full. Please think about it before responding and don't get so snarky.

About the 2D array allocation. It is correct. You must be doing something wrong. Your way of doing it obviously makes no sense at all:

Code:

worldArray[i] = worldArray[i - 1 + NCOLS];

Think about it. The whole point is to calculate the next pointer value from the previous pointer value. The previous pointer value is worldArray[i - 1], which we therefore must add something to. The correct thing to add is NCOLS.

Try this:

Code:

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

#define NROWS  5
#define NCOLS 10

int main() {
    bool **a = malloc(NROWS * sizeof *a);
    a[0] = calloc(NROWS * NCOLS, sizeof **a);
    // Note that this loop must start at 1, not 0 !
    for (int i = 1; i < NROWS; i++)
        a[i] = a[i - 1] + NCOLS;

    for (int r = 0; r < NROWS; r++)
        for (int c = 0; c < NCOLS; c++)
            a[r][c] = (r % 2 + c % 2) % 2 == 0;

    for (int r = 0; r < NROWS; r++) {
        for (int c = 0; c < NCOLS; c++)
            printf("%2d ", (int)a[r][c]);
        putchar('\n');
    }

    free(a[0]);
    free(a);
    return 0;
}

Since you don't seem to appreciate my help, this is the last time I will look at this thread.
Good luck.