Invalid free() when trying to reorder a linked list

Question

I am attempting to reorder a linked list by swapping the pointers around. It works until I try to free the memory and then it gives me an error.

I have gotten it to work, by swapping the data and not the pointers, but I am curious as to why this causes an issue with my memory. Here is my code

typedef struct myArray {
    void *data;
    struct myArray *next;
} myArray_t;

int main(int argc, char **argv) {
    myArray *ma = paramsToList(argc, argv);
    revArray(&ma);
    printArray(ma);
    free(ma);
    return 0;
}

myArray_t *paramsToList(int ac, char *const *av) {
    myArray *ma = (myArray*)malloc((ac) * sizeof(myArray));
    int i = 0;
    while (i < ac) {
        ma[i].data = av[i];
        if (i < ac - 1) {
            ma[i].next = &ma[i + 1];
        } else {
            ma[i].next = NULL;
        }
        i++;
    }
    return ma;
}

void revArray(myArray_t **begin) {
    myArray *cur = begin[0];
    myArray *prev = NULL;
    myArray *next = cur->next;
    while (cur != NULL) {
        cur->next = prev;
        prev = cur;
        cur = next;
        if (cur != NULL) {
            next = cur->next;
        }
    }
    begin[0] = prev;
}

When I run the code I get this error

valgrind ./a.out one two three

three
two
one
./a.out
==3662== Invalid free() / delete / delete[] / realloc()
==3662==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3662==    by 0x400604: main (example.c:20)
==3662==  Address 0x51fc070 is 48 bytes inside a block of size 64 alloc'd
==3662==    at 0x4C2AB80: malloc (in /usr/lib/valgrind    /vgpreload_memcheck-amd64-linux.so)
==3662==    by 0x40062B: paramsToList(int, char* const*) (example.c:26)
==3662==    by 0x4005DC: main (example.c:17)
==3662== 
==3662== 
==3662== HEAP SUMMARY:
==3662==     in use at exit: 64 bytes in 1 blocks
==3662==   total heap usage: 1 allocs, 1 frees, 64 bytes allocated
==3662== 
==3662== LEAK SUMMARY:
==3662==    definitely lost: 64 bytes in 1 blocks
==3662==    indirectly lost: 0 bytes in 0 blocks
==3662==      possibly lost: 0 bytes in 0 blocks
==3662==    still reachable: 0 bytes in 0 blocks
==3662==         suppressed: 0 bytes in 0 blocks
==3662== Rerun with --leak-check=full to see details of leaked memory
==3662== 
==3662== For counts of detected and suppressed errors, rerun with: -v
==3662== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

PSA: [Don't cast the result of `malloc`](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — tadman, Sep 03 '19 at 22:33

Iharob Al Asimi · Answer 1 · 2019-09-03T21:15:43.083

4

You can only pass to free() a pointer that was returned by malloc()/realloc()/calloc() and you are passing a node that is a pointer to a ma plus some offset, precisely &ma[ac - 1].

You could just change the content of the nodes instead of the nodes themeselves, or just write a normal linked list where every node is just allocated with malloc().

edited Sep 03 '19 at 21:15

answered Sep 03 '19 at 21:09

Iharob Al Asimi

52,653
6
59
97

1

The problem is in `begin[0] = prev;`. Since `begin` is `&ma`, changing `begin[0]` changes `ma`. So when you `free(ma)`, you aren't freeing the same address you got from `malloc`. – David Schwartz Sep 03 '19 at 21:37

score 2 · Answer 2 · answered Sep 04 '19 at 13:08

You must pass the original pointer returned by malloc() to free().

Since revarray modifies the pointer received by address, you must save the original pointer to later pass to free().

Also note that revArray can be simplified by removing the test to set next.

Here is a modified version:

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

typedef struct myArray {
    void *data;
    struct myArray *next;
} myArray_t;

myArray_t *paramsToList(int ac, char *const *av) {
    myArray *ma = (myArray *)malloc(ac * sizeof(myArray));
    if (ma == NULL)
        return NULL;
    for (int i = 0; i < ac; i++) {
        ma[i].data = av[i];
        if (i < ac - 1) {
            ma[i].next = &ma[i + 1];
        } else {
            ma[i].next = NULL;
        }
    }
    return ma;
}

void revArray(myArray_t **begin) {
    myArray *cur = *begin;
    myArray *prev = NULL;
    myArray *next = cur->next;
    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    *begin = prev;
}

int main(int argc, char **argv) {
    myArray *ma = paramsToList(argc, argv);
    myArray *orig_ma = ma;
    revArray(&ma);
    printArray(ma);
    free(orig_ma);
    return 0;
}

Invalid free() when trying to reorder a linked list

2 Answers2