Memory allocated was not freed for some reason - C

Question

I am currently writing a chess game in C as a project in my studies. I checked memory leaks with valgrind and found a few leaks. I examined the log of the valgrind test and found that there is always the same chain of functions in every leak that lead to the same points, I tried to debug and trace the leaks unfortunately without success.

Could anyone please look at the functions below and point out what could be the problem? Thanks.

edit: I found the leak in getAllMoves
Thanks all.

Here is the source code:

//THESE ARE THE STRUCTS//
typedef struct position {
    char x;
    int  y;
    struct position * next;
}position;

typedef struct move {
    position* current_pos;
    char* promotion;
    struct move * next;
}move;

typedef struct {
    move* head;
    move* tail;
}moves;
//END OF STRUCTS//

/*
* Freeing a list of positions
*/
void freePositions(position* pos){
    if (pos != NULL){
        freePositions(pos->next);
        free(pos);
    }
}
/*
* Freeing a list of moves
*/
void freeMoves(move* move){
    if (move != NULL){
        freePositions(move->current_pos);
        freeMoves(move->next);
        if (move->promotion != NULL){
            free(move->promotion);
        }
        free(move);
    }
}

/* Checking if there was a check performed by "playing_color" player */
int isCheck(char playing_color , char curr_board[BOARD_SIZE][BOARD_SIZE]){
    moves* player_moves = getAllMoves(playing_color, curr_board);
    move * head = player_moves->head;
    while (head != NULL) {
        int x = head->current_pos->next->x - 97;
        int y = head->current_pos->next->y - 1;
        if ((curr_board[y][x] == WHITE_K && playing_color == 'B') || (curr_board[y][x] == BLACK_K && playing_color == 'W')) {
            freeMoves(player_moves->head);
            free(player_moves);
            return 1;
        }
        head = head->next;
    }
    freeMoves(player_moves->head);
    free(player_moves);
    return 0;
}

/*
* Concating a move to a list of moves
*/
moves* concatMoves(moves* moves_1, move* move2){
    if (move2==NULL || move2->current_pos == NULL){
        return moves_1;
    }
    if (moves_1->tail == NULL){
        moves_1->head = move2;
        moves_1->tail = move2;
        move2 = move2->next;
    }
    if (move2 != NULL){
        moves_1->tail->next = move2;
        moves_1->tail = move2;
        move* next_move = move2;
        while (next_move->next != NULL) {
            next_move = next_move->next;
            moves_1->tail = next_move;
        }
    }

    return moves_1;
}

/*
* create a move from (x,y) to (x+ x_offset, y+ y_offset)
*/
move* CreateMove(position * current_pos, int x_offset , int y_offset) {
    position * start_pos = calloc(1, sizeof(position));
    validate(start_pos, "CreateMove");
    position * new_pos = calloc(1,sizeof(position));
    validate(new_pos, "CreateMove");
    initPosition(new_pos, current_pos->x+x_offset, current_pos->y+y_offset);
    initPosition(start_pos, current_pos->x , current_pos->y );
    move *new_move = calloc(1,sizeof(move));
    validate(new_move, "CreateMove");
    initMove(new_move);
    new_move->current_pos = start_pos;
    new_move->current_pos->next = new_pos;
    return new_move;
}

/*
* get all possible bishop moves from the current position
*/
moves* getBishopMoves(char playing_color, char curr_board[BOARD_SIZE][BOARD_SIZE], position* current_pos){
    //flags that symbolizes we cannot move longer on the corresponding diagonal
    int moved_topRight_diag = 0; int moved_topLeft_diag = 0;
    int moved_downRight_diag = 0; int moved_downLeft_diag = 0;
    moves * bishop_moves = calloc(1, sizeof(moves));
    validate(bishop_moves, "getBishopMoves");
    for (int i = 1; i < BOARD_SIZE; i++) {
        if (moved_downLeft_diag && moved_topLeft_diag && moved_downRight_diag && moved_topRight_diag){
            break;
        }
        position next_pos = { current_pos->x + i, current_pos->y + i, NULL };
        move* new_move;
        //check if there is a legal  move from (x,y) to (x+i,y+i)
        if (!moved_topRight_diag && isValidPosition(next_pos)){
            if (IsEmpty(next_pos.x-97, next_pos.y-1, curr_board)){
                new_move = CreateMove(current_pos, i, i);
                concatMoves(bishop_moves, new_move);
            }
            else if (!isSameColor(playing_color, &next_pos, curr_board) && !IsEmpty(next_pos.x-97, next_pos.y-1, curr_board)){
                new_move = CreateMove(current_pos, i, i);
                concatMoves(bishop_moves, new_move);
                moved_topRight_diag = 1;
            }
            else {
                moved_topRight_diag = 1;
            }
        }
        //check if there is a legal non-capture move from (x,y) to (x+i,y-i)
        position next_pos1 = { current_pos->x + i, current_pos->y - i, NULL };
        if (!moved_downRight_diag && isValidPosition(next_pos1)){
            if (IsEmpty(next_pos1.x-97, next_pos1.y-1, curr_board)){
                new_move = CreateMove(current_pos, i, -i);
                concatMoves(bishop_moves, new_move);
            }
            else if (!isSameColor(playing_color, &next_pos1, curr_board) && !IsEmpty(next_pos1.x-97, next_pos1.y-1, curr_board)){
                new_move = CreateMove(current_pos, i, -i);
                concatMoves(bishop_moves, new_move);
                moved_downRight_diag = 1;
            }
            else {
                moved_downRight_diag = 1;
            }
        }
        //check if there is a legal non-capture move from (x,y) to (x-i,y-i)
        position next_pos2 = { current_pos->x - i, current_pos->y - i, NULL };
        if (!moved_downLeft_diag && isValidPosition(next_pos2)){
            if (IsEmpty(next_pos2.x-97, next_pos2.y-1, curr_board)){
                new_move = CreateMove(current_pos, -i, -i);
                concatMoves(bishop_moves, new_move);
            }
            else if (!isSameColor(playing_color, &next_pos2, curr_board) && !IsEmpty(next_pos2.x-97, next_pos2.y-1, curr_board)){
                new_move = CreateMove(current_pos, -i, -i);
                concatMoves(bishop_moves, new_move);
                moved_downLeft_diag = 1;
            }
            else {
                moved_downLeft_diag = 1;
            }
        }
        //check if there is a legal non-capture move from (x,y) to (x-i,y+i)
        position next_pos3 = { current_pos->x - i, current_pos->y + i, NULL };
        if (!moved_topLeft_diag && isValidPosition(next_pos3)){
            if (IsEmpty(next_pos3.x-97, next_pos3.y-1, curr_board)){
                new_move = CreateMove(current_pos, -i, i);
                concatMoves(bishop_moves, new_move);
            }
            else if (!isSameColor(playing_color, &next_pos3, curr_board) && !IsEmpty(next_pos3.x-97, next_pos3.y-1, curr_board)){
                new_move = CreateMove(current_pos, -i, i);
                concatMoves(bishop_moves, new_move);
                moved_topLeft_diag = 1;
            }
            else {
                moved_topLeft_diag = 1;
            }
        }

    }
    return bishop_moves;
}

/*
* get all possible queen moves from the current position , queen moves simply combine rook and bishop moves from a current position.
*/
moves * getQueenMoves(char playing_color, char curr_board[BOARD_SIZE][BOARD_SIZE], position* current_pos){
    moves * queen_moves = getBishopMoves(playing_color, curr_board, current_pos);
    moves* rook_moves = getRookMoves(playing_color, curr_board, current_pos);
    move* rooks_move_head = rook_moves->head;
    concatMoves(queen_moves, rooks_move_head);
    free(rook_moves);
    return queen_moves;
}

/*
* removing moves that end up with check the the playing color king
*/
void removeBadMoves(moves* all_moves, char playing_color, char curr_board[BOARD_SIZE][BOARD_SIZE]){
    move* curr_move = all_moves->head;

    while (curr_move != NULL){
        char temp_board[BOARD_SIZE][BOARD_SIZE];
        boardCopy(curr_board, temp_board);
        actualBoardUpdate(curr_move, temp_board, playing_color);
        if (curr_move == all_moves->head && isCheck(OppositeColor(playing_color), temp_board)) {
            all_moves->head = all_moves->head->next;
            freePositions(curr_move->current_pos);
            free(curr_move);
            curr_move = all_moves->head;
            continue;
        }
        else if (curr_move->next != NULL) {
            boardCopy(curr_board, temp_board);
            actualBoardUpdate(curr_move->next, temp_board, playing_color);
            if (isCheck(OppositeColor(playing_color), temp_board)){
                move* temp_move = curr_move->next;
                curr_move->next = curr_move->next->next;
                if (temp_move == all_moves->tail){
                    all_moves->tail = curr_move;
                }
                freePositions(temp_move->current_pos);
                free(temp_move);
                continue;
            }

        }
        curr_move = curr_move->next;
    }
}

/*
* get all possible moves from a given positiion at the board
*/
moves* getMovesFromPosition(char playing_color, char curr_board[BOARD_SIZE][BOARD_SIZE], position* current_pos){
    char square = curr_board[current_pos->y - 1][current_pos->x - 97];
    moves* poss_moves = NULL;
    if (square != EMPTY){
        if (playing_color == 'W'){
            if (square == WHITE_R){
                poss_moves = getRookMoves(playing_color, curr_board, current_pos);
            }
            else if (square == WHITE_N){
                poss_moves = getKnightMoves(playing_color, curr_board, current_pos);
            }
            else if (square == WHITE_B){
                poss_moves = getBishopMoves(playing_color, curr_board, current_pos);
            }
            else if (square == WHITE_Q){
                poss_moves = getQueenMoves(playing_color, curr_board, current_pos);
            }
            else if (square == WHITE_K){
                poss_moves = getKingMoves(playing_color, curr_board, current_pos);
            }
            else {
                poss_moves = getPawnMoves(playing_color, curr_board, current_pos);
            }
        }
        else {
            if (square == BLACK_R){
                poss_moves = getRookMoves(playing_color, curr_board, current_pos);
            }
            else if (square == BLACK_N){
                poss_moves = getKnightMoves(playing_color, curr_board, current_pos);
            }
            else if (square == BLACK_B){
                poss_moves = getBishopMoves(playing_color, curr_board, current_pos);

            }
            else if (square == BLACK_Q){
                poss_moves = getQueenMoves(playing_color, curr_board, current_pos);

            }
            else if (square == BLACK_K){
                poss_moves = getKingMoves(playing_color, curr_board, current_pos);

            }
            else {
                poss_moves = getPawnMoves(playing_color, curr_board, current_pos);
            }
        }
    }
    return poss_moves;
}

/*
* Getting all possible moves for a current player
*/
moves* getAllMoves(char playing_color, char curr_board[BOARD_SIZE][BOARD_SIZE]){
    moves* all_moves = NULL;
    position* curr_pos = NULL;
    moves* pos_moves = NULL;
    move* temp_head = NULL;
    all_moves = calloc(1, sizeof(moves));
    validate(all_moves, "getMoves");

    for (int i = 0; i < BOARD_SIZE; i++){
        for (int j = 0; j < BOARD_SIZE; j++){
            curr_pos = calloc(1, sizeof(position));
            validate(curr_pos, "getMoves");
            initPosition(curr_pos, j + 97, i + 1);
            if (isSameColor(playing_color, curr_pos, curr_board)){
                pos_moves = getMovesFromPosition(playing_color, curr_board, curr_pos);
                if (pos_moves->head != NULL){
                    temp_head = pos_moves->head;
                    concatMoves(all_moves, temp_head);
                    free(pos_moves);
                }
            }
            freePositions(curr_pos);
        }
    }
    return all_moves;
}

/*
* Getting all possible legal moves for a current player
*/
moves * getMoves(char playing_color, char curr_board[BOARD_SIZE][BOARD_SIZE]) {
    moves * all_moves = getAllMoves(playing_color, curr_board);
    removeBadMoves(all_moves, playing_color, curr_board);
    return all_moves;
}

/*
* Checking if the game has ended in a Tie
*/
int isTie(char playing_color){
    moves* possible_moves = getMoves(playing_color, board);
    if (possible_moves->head == NULL && !isCheck(OppositeColor(playing_color),board)){
        free(possible_moves);
        return 1;
    }
    freeMoves(possible_moves->head);
    free(possible_moves);
    return 0;
}

/*
* Checking if the game has ended in a Mate or a Tie
*/
int gameOver(int print_bit){
    if (isMate('W', board)){
        if (print_bit){
            printf("Mate! White player wins the game\n");
        }
        return 1;
    }
    if (isMate('B', board)){
        if (print_bit){
            printf("Mate! Black player wins the game\n");
        }
        return 1;
    }
    if (isTie('W') || isTie('B')){
        if (print_bit){
            printf("The game ends in a tie\n");
        }
        return 1;
    }
    return 0;
}

Here is a log of the valgrind test I've performed
(All the leaks contain almost the same chain of functions, so I'll just post few of them):

==28961== HEAP SUMMARY:  
==28961==     in use at exit: 80,480 bytes in 5,030 blocks  
==28961==   total heap usage: 124,076 allocs, 119,046 frees, 2,096,919 bytes allocated  
==28961==   
==28961== Searching for pointers to 5,030 not-freed blocks  
==28961== Checked 1,055,792 bytes 

==28961== 16 bytes in 1 blocks are definitely lost in loss record 5 of 152  
==28961==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)  
==28961==    by 0x40AD14: getBishopMoves (chesslogic.c:712)  
==28961==    by 0x40B745: getQueenMoves (chesslogic.c:877)  
==28961==    by 0x40C779: getMovesFromPosition (chesslogic.c:1056)  
==28961==    by 0x40C974: getAllMoves (chesslogic.c:1109)  
==28961==    by 0x40C9FF: getMoves (chesslogic.c:1126)  
==28961==    by 0x40CA3C: isTie (chesslogic.c:1136)  
==28961==    by 0x409BBD: gameOver (chesslogic.c:273)  
==28961==    by 0x40917B: SettingsMode (gameflow.c:626)  
==28961==    by 0x40CFBB: main (main.c:26)  
==28961==   
==28961== 16 bytes in 1 blocks are definitely lost in loss record 6 of 152  
==28961==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)  
==28961==    by 0x40BF47: getKingMoves (chesslogic.c:966)  
==28961==    by 0x40C79E: getMovesFromPosition (chesslogic.c:1059)  
==28961==    by 0x40C974: getAllMoves (chesslogic.c:1109)  
==28961==    by 0x40C9FF: getMoves (chesslogic.c:1126)  
==28961==    by 0x40CA3C: isTie (chesslogic.c:1136)  
==28961==    by 0x409BBD: gameOver (chesslogic.c:273)  
==28961==    by 0x40917B: SettingsMode (gameflow.c:626)  
==28961==    by 0x40CFBB: main (main.c:26)  
==28961==   
==28961== 16 bytes in 1 blocks are definitely lost in loss record 7 of 152  
==28961==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)  
==28961==    by 0x40AD14: getBishopMoves (chesslogic.c:712)  
==28961==    by 0x40B745: getQueenMoves (chesslogic.c:877)  
==28961==    by 0x40C84E: getMovesFromPosition (chesslogic.c:1077)  
==28961==    by 0x40C974: getAllMoves (chesslogic.c:1109)  
==28961==    by 0x4099C9: isCheck (chesslogic.c:220)  
==28961==    by 0x40A6C4: removeBadMoves (chesslogic.c:604)  
==28961==    by 0x40CA19: getMoves (chesslogic.c:1127)  
==28961==    by 0x40CA3C: isTie (chesslogic.c:1136)  
==28961==    by 0x409BBD: gameOver (chesslogic.c:273)  
==28961==    by 0x40917B: SettingsMode (gameflow.c:626)  
==28961==    by 0x40CFBB: main (main.c:26)  
==28961==   
==28961== 16 bytes in 1 blocks are definitely lost in loss record 8 of 152  
==28961==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)  
==28961==    by 0x40BF47: getKingMoves (chesslogic.c:966)  
==28961==    by 0x40C870: getMovesFromPosition (chesslogic.c:1081)  
==28961==    by 0x40C974: getAllMoves (chesslogic.c:1109)  
==28961==    by 0x4099C9: isCheck (chesslogic.c:220)  
==28961==    by 0x40A6C4: removeBadMoves (chesslogic.c:604)  
==28961==    by 0x40CA19: getMoves (chesslogic.c:1127)  
==28961==    by 0x40CA3C: isTie (chesslogic.c:1136)  
==28961==    by 0x409BBD: gameOver (chesslogic.c:273)  
==28961==    by 0x40917B: SettingsMode (gameflow.c:626)  
==28961==    by 0x40CFBB: main (main.c:26)  

Answer 1

Just a comment on the your freePositions() and freeMoves() functions. There's unnecessary use of recursion here. It's much more efficient to do it iteratively.

void freePositions(position* pos){
    while (pos != NULL){
        position *next = pos->next;
        free(pos);
        pos = next;
    }
}

void freeMoves(move* move){
    while (move != NULL){
        move *next = move->next;
        freePositions(move->current_pos);
        if (move->promotion != NULL){
            free(move->promotion);
        }
        free(move);
        move = next;
    }
}

Answer 2

The player_moves pointer in isCheck is being freed.

The valgrind output is actually pointing you to an allocation you are doing with calloc in getBishopMoves (the contents of which you have not posted), so that's where you should look for the cause of the memory leak.

You haven't posted what the moves datatype is, but if it's a structure containing a pointer that you allocate memory for in getBishopMoves, then you should free that pointer before freeing the structure pointer itself.

Something like:

free(player_moves->ptr);
free(player_moves);

Answer 3

There's code missing so I'm only able to guess really. Plus I don't think stackoverflow is normally for outsourcing the debug of your code.

However, I think the problem is that player_moves is some kind of linked list structure, containing a number of allocated structures beneath (allocated in getAllMoves). free() will only free the player_moves object, and your leak is caused because the pointers referenced within that structure are lost. You should probably create a 'destroy' function for the structure which goes through and deletes each move linked against it. Maybe that's wrapped up in the line freePositions(curr_pos), I can't really tell from this snippet. It depends what freePositions and concatMoves are doing.

Generally speaking, I think you've got yourself in this bind by not following the 'whoever creates it destroys it' principle. That's easier to structure in OO languages like C++, but in this case I would be using functions to create and destroy objects (moves, pieces etc) and pass them in pre-created. For example, the getMovesFromPosition function allocating memory internally is not obvious. If it accepted an allocated object, it would be clearer that it required deleting after.