segfault in a C garbage collector

Question

I'm building a simple garbage collector in C, with a void pointer linked list that collects the malloced pointers and frees them all at the end.

#include "linked_list.h"

#define MAKE_GC(NAME) \
MAKE_LIST(NAME); \
static void _throw_away_##NAME() { \
    ITERATOR(NAME) = &NAME; \
    do { \
        free(ITERATOR(NAME)->elem); \
    } while ((ITERATOR(NAME) = ITERATOR(NAME)->next) != NULL); \
    DESTROY_LIST(NAME); \
}

#define GC_ALLOC(TYPE, TARGET, LEN, GC_NAME) \
do { \
    TARGET = (TYPE *)malloc(LEN * sizeof(TYPE)); \
    PUSH(TYPE *, TARGET, GC_NAME); \
} while (0)

#define GC_FREE(NAME) _throw_away_##NAME()

The above is the garbage collector, and below is linked_list.h

struct linked_list {
    void *elem;
    struct linked_list *next;
};

#define ITERATOR(LIST_NAME) _iter_##LIST_NAME

#define MAKE_LIST(NAME) \
struct linked_list NAME = { NULL, NULL }; \
struct linked_list *ITERATOR(NAME) = &NAME

#define PUSH(TYPE, X, LIST) \
do { \
    ITERATOR(LIST) = ITERATOR(LIST)->next = (struct linked_list *)malloc(sizeof(struct linked_list)); \
    *(TYPE *)ITERATOR(LIST)->elem = X; \
    ITERATOR(LIST)->next = NULL; \
} while (0)

#define DESTROY_LIST(LIST) \
do { \
    struct linked_list *l; \
    ITERATOR(LIST) = &LIST; \
    do { \
        l = ITERATOR(LIST)->next; \
        free(ITERATOR(LIST)); \
    } while ((ITERATOR(LIST) = l) != NULL); \
} while (0)

When I test this code with the following,

#include <stdio.h>
#include "garbage_collector.h"

MAKE_GC(char_gc);

int main() {
    char *str;
    int i;

    GC_ALLOC(char, str, 11, char_gc);
    for (i = 0; i < 10; i++) {
        putchar(str[i] = i + '0');
    }
    str[i] = '\0';
    putchar('\n');
    puts(str);

    GC_FREE(char_gc);
    return 0;
}

It runs as expected, although the debuggers (gdb and Visual Studio debugger) keep on throwing segfaults in GC_ALLOC. It's a really short piece of code, and I'm quite annoyed that I still have no clue where it goes wrong.

I want to be sure where my program is broken and fix it before implementing elsewhere. Thanks in advance for any help.

Answer 1

In your PUSH macro, I don't think this line is correct:

*(TYPE *)ITERATOR(LIST)->elem = X; \

I think you want something like this:

ITERATOR(LIST)->elem = (void *)X; \

In your code, I get a seg fault here:

GC_ALLOC(char, str, 11, char_gc);

and it's due to the fact that GC_ALLOC does a PUSH, passing str as X. Once str has been properly allocated by the previous line, you want to assign the pointer to elem, but your code attempts to dereference elem, and then assign the pointer to that dereferenced item. dereferencing elem is illegal at that point, and seg faults, because it has not been allocated (and should not be at that point).

After that, you have a problem at the final GC_FREE in your code, because it eventually tries to free an unallocated pointer. When GC_FREE attempts to DESTROY_LIST(gc_Char), it starts with the first item in the list. But this item was not allocated via malloc (take a look at MAKE_LIST), so it cannot be free'd using free. So we have to skip past this first item in the list when we want to DESTROY_LIST. The following code has these items fixed and seems to work correctly for your test case:

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

struct linked_list {
    void *elem;
    struct linked_list *next;
};

#define ITERATOR(LIST_NAME) _iter_##LIST_NAME

#define MAKE_LIST(NAME) \
struct linked_list NAME = { NULL, NULL }; \
struct linked_list *ITERATOR(NAME) = &NAME

#define PUSH(TYPE, X, LIST) \
do { \
    ITERATOR(LIST) = ITERATOR(LIST)->next = (struct linked_list *)malloc(sizeof(struct linked_list)); \
    ITERATOR(LIST)->elem = (void *)X; \
    ITERATOR(LIST)->next = NULL; \
} while (0)

#define DESTROY_LIST(LIST) \
do { \
    struct linked_list *l; \
    ITERATOR(LIST) = &LIST; \
    l = ITERATOR(LIST)->next; \
    while ((ITERATOR(LIST) = l) != NULL) { \
        l = ITERATOR(LIST)->next; \
        free(ITERATOR(LIST)); \
    }  \
} while (0)

#define MAKE_GC(TYPE, NAME) \
MAKE_LIST(NAME); \
static void _throw_away_##NAME() { \
    ITERATOR(NAME) = &NAME; \
    do { \
        free(ITERATOR(NAME)->elem); \
    } while ((ITERATOR(NAME) = ITERATOR(NAME)->next) != NULL); \
    DESTROY_LIST(NAME); \
}

#define GC_ALLOC(TYPE, TARGET, LEN, GC_NAME) \
do { \
    TARGET = (TYPE *)malloc(LEN * sizeof(TYPE)); \
    PUSH(TYPE *, TARGET, GC_NAME); \
} while (0)

#define GC_FREE(NAME) _throw_away_##NAME()

MAKE_GC(char, char_gc);

int main() {
    char *str;
    int i;
    GC_ALLOC(char, str, 11, char_gc);
    for (i = 0; i < 10; i++) {
        putchar(str[i] = i + '0');
    }
    str[i] = '\0';
    putchar('\n');
    puts(str);
    GC_FREE(char_gc);
    return 0;
}