C malloc valgrind invalid write of size

3
votes

I've had my fair share malloc invalid writes (and the many examples on this site) but I still have trouble pointing out what's causing some. Here I have an adjacency matrix to use for graphs and when allocating, I get the invalid write from valgrind (but no segmentation fault throughout the program). I also get invalid reads but I assume that's caused from the invalid write prior.

FYI adj_matrix is a typedef'd struct with an int type for number of vertices and a char** for the actual 2D array declared in the header file

Also, not included in my post is the test file, all it does is allocate space for the struct and call these functions.

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

#include "adj_matrix.h"

void adj_matrix_init(adj_matrix *matrix, const int num_vertices) {

    int i;
    char* temp;

    matrix->num_vertices = num_vertices;

    //INVALID WRITE & READ HERE
    if(!(matrix->matrix = malloc(num_vertices * sizeof(char *)))) { 
        fprintf(stderr, "Could not allocate space for the adjacency matrix.\n");
        exit(EXIT_FAILURE);
    }

    // THIS ONE WORKS THOUGH
    if(!(temp = calloc(num_vertices * num_vertices, sizeof(char)))) {
        fprintf(stderr, "Could not allocate space for the adjacency matrix.\n");
        exit(EXIT_FAILURE);
    }

    for(i = 0; i < num_vertices; i++) {
        (matrix->matrix)[i] = temp + (i * num_vertices); // INVALID READ
    }
}

void adj_matrix_destroy(adj_matrix *matrix) {

    free(matrix->matrix[0]); // INVALID READ
    free(matrix->matrix);
    free(matrix);
}

void adj_matrix_add_edge(adj_matrix *matrix, const int from_node, const int to_node) {
    matrix->matrix[from_node - 1][to_node - 1] = 1; // INVALID READ
}

void adj_matrix_remove_edge(adj_matrix *matrix, const int from_node, const int to_node) {
    matrix->matrix[from_node - 1][to_node -1] = 0;
}

bool adj_matrix_check_edge(const adj_matrix *matrix, const int from_node, const int to_node) {
    return (matrix->matrix[from_node - 1][to_node -1] ? true : false);
}

size_t adj_matrix_min(const size_t val1, const size_t val2) {
    return (val1 <= val2) ? val1 : val2;
}

size_t adj_matrix_to_string(const adj_matrix *matrix, char *buffer, const size_t buffer_size) {
    const size_t terminator = adj_matrix_min(buffer_size, (size_t)pow((matrix->num_vertices+1) + 1, 2));
    int i, j, count = 0;

    printf("Buffer size: %zd\nMatrix size (plus null character): %f\nMinimum: %zd\n", buffer_size, pow((matrix->num_vertices + 1), 2), terminator);

    for(i = 0; i < matrix->num_vertices; i++) {
        for(j = 0; j < matrix->num_vertices; j++) {
            printf("TEST1: %s\n info: %d\n", buffer, matrix->matrix[i][1]); // JUST TESTING VALUES
            if( (count - 1) < terminator) {
                if(matrix->matrix[i][j]) {
                    printf("Got in with true\n");
                    buffer[count++] = '1';
                } else {
                    printf("Got in with false\n");
                    buffer[count++] = '0';
                }
                buffer[count] = '\0';
            }
            else {
                buffer[buffer_size - 1] = '\0';
                return terminator;
            }
            printf("TEST2: %s\n", buffer);
        }
        if( (count - 1) < terminator ) {
            buffer[count++] = '\n';
            buffer[count] = '\0';
        }
        else {
            buffer[buffer_size - 1] = '\0';
            return terminator;
        }
    }
    return terminator;
}

VALGRIND:

==5590== Memcheck, a memory error detector
==5590== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==5590== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==5590== Command: ./test-adj_matrix
==5590== 
==5590== Invalid write of size 8
==5590==    at 0x40080C: adj_matrix_init (adj_matrix.c:16)
==5590==    by 0x400718: main (test_adjmatrix.c:12)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Invalid read of size 8
==5590==    at 0x400814: adj_matrix_init (adj_matrix.c:16)
==5590==    by 0x400718: main (test_adjmatrix.c:12)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Invalid read of size 8
==5590==    at 0x4008A7: adj_matrix_init (adj_matrix.c:27)
==5590==    by 0x400718: main (test_adjmatrix.c:12)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Invalid read of size 8
==5590==    at 0x400925: adj_matrix_add_edge (adj_matrix.c:39)
==5590==    by 0x40072E: main (test_adjmatrix.c:14)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Invalid read of size 8
==5590==    at 0x400925: adj_matrix_add_edge (adj_matrix.c:39)
==5590==    by 0x400744: main (test_adjmatrix.c:15)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Invalid read of size 8
==5590==    at 0x400925: adj_matrix_add_edge (adj_matrix.c:39)
==5590==    by 0x40075A: main (test_adjmatrix.c:16)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
Buffer size: 26
Matrix size (plus null character): 25.000000
Minimum: 26
==5590== Invalid read of size 8
==5590==    at 0x400A9F: adj_matrix_to_string (adj_matrix.c:62)
==5590==    by 0x400772: main (test_adjmatrix.c:18)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Conditional jump or move depends on uninitialised value(s)
==5590==    at 0x4E7D3B1: vfprintf (vfprintf.c:1630)
==5590==    by 0x4E858D8: printf (printf.c:35)
==5590==    by 0x400AD5: adj_matrix_to_string (adj_matrix.c:62)
==5590==    by 0x400772: main (test_adjmatrix.c:18)
==5590==  Uninitialised value was created by a heap allocation
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x4006F5: main (test_adjmatrix.c:8)
==5590== 
TEST1: 
 info: 1
==5590== Conditional jump or move depends on uninitialised value(s)
==5590==    at 0x4E7D3B1: vfprintf (vfprintf.c:1630)
==5590==    by 0x4E858D8: printf (printf.c:35)
==5590==    by 0x40078B: main (test_adjmatrix.c:20)
==5590==  Uninitialised value was created by a heap allocation
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x4006F5: main (test_adjmatrix.c:8)
==5590== 
==5590== Invalid read of size 8
==5590==    at 0x400961: adj_matrix_remove_edge (adj_matrix.c:43)
==5590==    by 0x4007A1: main (test_adjmatrix.c:22)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
Buffer size: 26
Matrix size (plus null character): 25.000000
Minimum: 26
==5590== Invalid read of size 8
==5590==    at 0x400A9F: adj_matrix_to_string (adj_matrix.c:62)
==5590==    by 0x4007B9: main (test_adjmatrix.c:24)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Conditional jump or move depends on uninitialised value(s)
==5590==    at 0x4E7D3B1: vfprintf (vfprintf.c:1630)
==5590==    by 0x4E858D8: printf (printf.c:35)
==5590==    by 0x400AD5: adj_matrix_to_string (adj_matrix.c:62)
==5590==    by 0x4007B9: main (test_adjmatrix.c:24)
==5590==  Uninitialised value was created by a heap allocation
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x4006F5: main (test_adjmatrix.c:8)
==5590== 
TEST1: 
 info: 0
==5590== Invalid read of size 8
==5590==    at 0x4008E6: adj_matrix_destroy (adj_matrix.c:33)
==5590==    by 0x4007C5: main (test_adjmatrix.c:26)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Invalid read of size 8
==5590==    at 0x4008F9: adj_matrix_destroy (adj_matrix.c:34)
==5590==    by 0x4007C5: main (test_adjmatrix.c:26)
==5590==  Address 0x51f10a8 is 0 bytes after a block of size 8 alloc'd
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400703: main (test_adjmatrix.c:10)
==5590== 
==5590== Invalid free() / delete / delete[] / realloc()
==5590==    at 0x4C2A82E: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x4007D1: main (test_adjmatrix.c:28)
==5590==  Address 0x51f10a0 is 0 bytes inside a block of size 8 free'd
==5590==    at 0x4C2A82E: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x400910: adj_matrix_destroy (adj_matrix.c:35)
==5590==    by 0x4007C5: main (test_adjmatrix.c:26)
==5590== 
==5590== 
==5590== FILE DESCRIPTORS: 3 open at exit.
==5590== Open file descriptor 2: /dev/pts/4
==5590==    <inherited from parent>
==5590== 
==5590== Open file descriptor 1: /dev/pts/4
==5590==    <inherited from parent>
==5590== 
==5590== Open file descriptor 0: /dev/pts/4
==5590==    <inherited from parent>
==5590== 
==5590== 
==5590== HEAP SUMMARY:
==5590==     in use at exit: 26 bytes in 1 blocks
==5590==   total heap usage: 4 allocs, 4 frees, 82 bytes allocated
==5590== 
==5590== 26 bytes in 1 blocks are definitely lost in loss record 1 of 1
==5590==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5590==    by 0x4006F5: main (test_adjmatrix.c:8)
==5590== 
==5590== LEAK SUMMARY:
==5590==    definitely lost: 26 bytes in 1 blocks
==5590==    indirectly lost: 0 bytes in 0 blocks
==5590==      possibly lost: 0 bytes in 0 blocks
==5590==    still reachable: 0 bytes in 0 blocks
==5590==         suppressed: 0 bytes in 0 blocks

EDIT: test_adjmatrix.c

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

#include "adj_matrix.h"

int main() {
    char* temp = malloc((5*5+1)*sizeof(char));

    adj_matrix *matrix = malloc(sizeof(matrix));

    adj_matrix_init(matrix, 4);

    adj_matrix_add_edge(matrix, 2, 1);
    adj_matrix_add_edge(matrix, 1, 2);
    adj_matrix_add_edge(matrix, 3, 4);

    adj_matrix_to_string(matrix, temp, (5*5+1) * sizeof(char));

    printf("%s", temp);

    adj_matrix_remove_edge(matrix, 1, 2);

    adj_matrix_to_string(matrix, temp, (5*5+1) * sizeof(char));

    adj_matrix_destroy(matrix);

    free(matrix);
    return 0;
}
1
cmemory-managementmallocvalgrind
I'm guessing you made a mistake in allocating the struct. Show me line 10 of test_adjmatrix.c. – cha0site
The bug appears to be that main has not allocated enough space for the adj_matrix object passed to adj_matrix_init. But I can't be sure, because you didn't show main. Always provide a complete example program - one that we can compile, run, and see the problem for ourselves - when you ask questions like this! – zwol
added the file but i think i know what is wrong now that you mentioned that. I only allocated enough space for the struct not considering the 2d array that still needed to be allocated within it. – Pete Jodo
It would be interesting to know how adj_marixis defined. – alk
typedef struct { int num_vertices; char** matrix; } adj_matrix; – Pete Jodo

1 Answers

7
votes

The following does not seem correct:

adj_matrix *matrix = malloc(sizeof(matrix));

It is allocating 4 bytes (assuming 32-bit compiler). Probably should be sizeof( adj_matrix ).