C 2D array corruption

Question

I'm having an issue in which my 2D array is becoming corrupted. Consider this code:

int **generate_clique_adjacency_matrix(const formula f) {
    int num_terms = f.num_clauses * kVarsPerClause;
    printf("\nnum_terms: %d\n", num_terms);

    // construct a 2D array of appropriate size
    int **compatible = malloc(sizeof(int) * num_terms);
    for (int i = 0; i < num_terms; i++) {
        compatible[i] = malloc(sizeof(int) * num_terms);
        // initialize every cell to 0
        for (int j = 0; j < num_terms; j++) {
            printf("writing 0 to (%d, %d)\n", i, j);
            compatible[i][j] = 0;
        }
    }

    printf("num_terms: %d\n", num_terms);
    printf("matrix:\n");
    for (int i = 0; i < num_terms; i++) {
        printf("row %d: ", i);
        for (int j = 0; j < num_terms; j++) {
            printf("%d ", compatible[i][j]);
        }
        printf("\n");
    }
    exit(0);
}

Which is producing the shocking output:

num_terms: 6
writing 0 to (0, 0)
writing 0 to (0, 1)
writing 0 to (0, 2)
writing 0 to (0, 3)
writing 0 to (0, 4)
writing 0 to (0, 5)
writing 0 to (1, 0)
writing 0 to (1, 1)
writing 0 to (1, 2)
writing 0 to (1, 3)
writing 0 to (1, 4)
writing 0 to (1, 5)
writing 0 to (2, 0)
writing 0 to (2, 1)
writing 0 to (2, 2)
writing 0 to (2, 3)
writing 0 to (2, 4)
writing 0 to (2, 5)
writing 0 to (3, 0)
writing 0 to (3, 1)
writing 0 to (3, 2)
writing 0 to (3, 3)
writing 0 to (3, 4)
writing 0 to (3, 5)
writing 0 to (4, 0)
writing 0 to (4, 1)
writing 0 to (4, 2)
writing 0 to (4, 3)
writing 0 to (4, 4)
writing 0 to (4, 5)
writing 0 to (5, 0)
writing 0 to (5, 1)
writing 0 to (5, 2)
writing 0 to (5, 3)
writing 0 to (5, 4)
writing 0 to (5, 5)
num_terms: 6
matrix:
row 0: 22661104 0 22661136 0 0 0 
row 1: 0 0 0 0 0 0 
row 2: 0 0 0 0 0 0 
row 3: 0 0 0 0 0 0 
row 4: 0 0 0 0 0 0 
row 5: 0 0 0 0 0 0 

How is my array getting corrupted? Obviously, the data in row 0 should be all zeroes. I even tried adding asserts to ensure malloc is succeeding. This is driving me nuts.

Answer 1

As pointed out in other answers, the first allocation needs to allocate space for pointers to int instead of ints. It is better to use an identifier instead of an explicit type in the sizeof operand to avoid making mistakes here. Also, you need to check the return value of malloc() for allocation errors:

int **compatible = malloc(sizeof(*compatible) * num_terms);
if (compatible == NULL) {
    fprintf(stderr, "Row allocation error\n");
    exit(EXIT_FAILURE);
}

for (int i = 0; i < num_terms; i++) {
    compatible[i] = malloc(sizeof(**compatible) * num_terms);
    if (compatible[i] == NULL) {
        fprintf(stderr, "Column allocation error\n");
        exit(EXIT_FAILURE);
    }

    // initialize every cell to 0
    for (int j = 0; j < num_terms; j++) {
        printf("writing 0 to (%d, %d)\n", i, j);
        compatible[i][j] = 0;
    }
}

A better approach is to use VLA's in the allocation, allocating space for num_terms arrays of num_terms ints, and assigning the result to a pointer to an array of ints. A virtue of this method is that the allocated memory is contiguous, and malloc() will return a null pointer if the allocation fails. You should also use the size_t type for array indices, as this type is guaranteed to be able to hold any array index.

int (*compatible)[num_terms] = malloc(sizeof(*compatible) * num_terms);
if (compatible == NULL) {
    fprintf(stderr, "Allocation error\n");
    exit(EXIT_FAILURE);
}
// initialize every cell to 0
for (size_t i = 0; i < num_terms; i++) {
    for (size_t j = 0; j < num_terms; j++) {
        printf("writing 0 to (%zu, %zu)\n", i, j);
        compatible[i][j] = 0;
    }
}

If your array is not too large (this is system-dependent), you could simply use a VLA. Note that allocation errors for VLAs are not detectable.

int compatible[num_terms][num_terms];

// initialize every cell to 0
for (size_t i = 0; i < num_terms; i++) {
    for (size_t j = 0; j < num_terms; j++) {
        printf("writing 0 to (%zu, %zu)\n", i, j);
        compatible[i][j] = 0;
    }
}

Answer 2

Change this:

int **compatible = malloc(sizeof(int) * num_terms);

to this:

int **compatible = malloc(sizeof(int *) * num_terms);

because the first dimension is an array of pointers.

And don't forget to release the memory at the end:

 for (int i = 0; i < num_terms; i++)
    free(compatible[i]);
 free(compatible);

Answer 3

This is wrong:

int **compatible = malloc(sizeof(int) * num_terms);

You need to reserve space for n pointers to int (not for n ints)

Change to

int **compatible = malloc(sizeof(int *) * num_terms);

or better yet

int **compatible = malloc(sizeof(*compatible) * num_terms);