double linked list - memory corruption

Question

I am trying to implement a double linked list in 2 parts: the first is the actual functions for creating the list; the second is a simulator - containing a few threads, readers and writers (each popping and pushing into the double linked list in a while loop), and a garbage collector thread that cleans the list if it gets too large (according to argv). The list uses a mutex and a conditional variable in order to make it thread safe. However - whenever I run it, I get a double free/memory corruption (fasttop) error and I don't know why. I'd appreciate some help.

#include <pthread.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <errno.h>

#define USAGE_ERR "Usage: ./hw3 <WNUM> <RNUM> <MAX> <TIME>\n"

/* Argc parameter indexing consts */
#define INPUT_WNUM_IDX 1
#define INPUT_RNUM_IDX 2
#define OUTPUT_MAX_IDX 3
#define OUTPUT_TIME_IDX 4

typedef struct node {
    int value;

    struct node * previous;
    struct node * next;
}
node;

typedef struct {
    int length;
    node * head;
    node * tail;
    pthread_mutex_t mutex;
}
list;

list * global_list;
int stop_threads = 0;
int MAX_LIST_SIZE;
pthread_cond_t      gc_cond  = PTHREAD_COND_INITIALIZER;
pthread_mutex_t     gc_mutex = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t      read_cond  = PTHREAD_COND_INITIALIZER;
pthread_mutex_t     read_mutex = PTHREAD_MUTEX_INITIALIZER;

list * initlist_create();
void initlist_destroy(list * target_list);
list * initlist_push_head(list * target_list, int value);
int initlist_pop_tail(list * target_list);
void initlist_remove_last_k(list * target_list, int k);
int initlist_size(list * target_list);
pthread_mutex_t initlist_get_mutex(list * target_list);
void writer_thread();
void reader_thread();
void garbage_collect_thread();


list * initlist_create() {
    size_t list_size = sizeof(list);
    list * new_list = (list * ) malloc(list_size);
    new_list->head = NULL;
    new_list->tail = NULL;
    new_list->length = 0;
    if (0 != pthread_mutex_init( & (new_list->mutex), NULL)) {
        exit(errno);
    }
    return new_list;
}

void initlist_destroy(list * target_list) {
    node * current_node;
    node * temp_node;

    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }

    if (0 != target_list->length) {
        current_node = target_list->head;
        while (current_node != NULL) {
            temp_node = current_node->next;
            free(current_node);
            current_node = temp_node;
        }
    }

    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }

    if (0 != pthread_mutex_destroy( & (target_list->mutex))) {
        exit(errno);
    }

    free(target_list);
}

list * initlist_push_head(list * target_list, int value) {
    node * new_node;
    size_t node_size = sizeof(node);


    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }

    new_node = (node * ) malloc(node_size);
    if(NULL == new_node)
    {
        printf("Malloc failed\n" );
        exit(errno);
    }
    new_node->value = value;


    if (NULL != target_list->head) {
        new_node->next = target_list->head;
        new_node->previous = target_list->tail;
        target_list->head->previous = new_node;
        target_list->tail->previous = new_node;
    }
    else{
        target_list->tail = new_node;
    }

    target_list->head = new_node;
    target_list->length++;
    if(0 < target_list->length){
        pthread_cond_signal(&read_cond); 
    }
    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }
    return target_list;
}

int initlist_pop_tail(list * target_list) {
    int deleted_node_value;

    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }
    while(0 == target_list->length){
        pthread_cond_wait(&read_cond, &target_list->mutex);
    }
    node * last_node = target_list->tail;


    if (1 == target_list->length) {
        last_node = target_list->head;
        target_list->head =  NULL;
        target_list->tail = NULL;
    } else {
        target_list->tail = last_node->previous;
        target_list->tail->next = target_list->head;
    }
    deleted_node_value = last_node->value;


    // IMPORTANT
    // If i uncomment this, segfault and memory corruption,no idea why
    //free(last_node);

    target_list->length--;
    if (0 != pthread_mutex_unlock( & ( target_list->mutex) )) {
        exit(errno);
    }
    // if (0 != pthread_mutex_unlock( & (read_mutex))) {
    //  exit(errno);
    // }

    return deleted_node_value;
}

void initlist_remove_last_k(list * target_list, int k) {
    int remove_size = k;
    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }
    if (k > target_list->length)
    {
        remove_size = target_list->length;
    }
    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }
    for (int i = 0; i < remove_size; ++i) {
        initlist_pop_tail(target_list);
    }
}

int initlist_size(list * target_list) {
    int list_size;

    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }

    list_size = target_list->length;

    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }

    return list_size;
}

pthread_mutex_t initlist_get_mutex(list * target_list) {
    pthread_mutex_t list_mutex;

    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }

    list_mutex = target_list->mutex;

    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }

    return list_mutex;

}

void writer_thread()
{
    while (1)
    {
        if(stop_threads){
            return;
        }   
        if (MAX_LIST_SIZE < initlist_size(global_list))
        {
            pthread_cond_signal(&gc_cond);
        }
        initlist_push_head(global_list, rand());

    }
}


void reader_thread()
{
    while (1)
    {
        if(stop_threads){
            return;
        }   
        if (MAX_LIST_SIZE < initlist_size(global_list))
        {
            pthread_cond_signal(&gc_cond);
        }
        initlist_pop_tail(global_list);

    }
}

void garbage_collect_thread()
{
    while(1){
        if(stop_threads){
            return;
        }
        pthread_cond_wait(&gc_cond, &gc_mutex);
        int remove_count = (initlist_size(global_list) / 2);
        initlist_remove_last_k(global_list, remove_count);
        printf("GC – %d items removed from the list\r\n", remove_count);
        if (0 != pthread_mutex_unlock( & (gc_mutex))) {
            exit(errno);
        }
    }
}




int main(int argc, char * * argv) {
    /* Validate arguments */
    if (5 != argc) {
        printf(USAGE_ERR);
        exit(errno);
    }

    int writers_count        = atoi(argv[INPUT_WNUM_IDX]);
    int readers_count        = atoi(argv[INPUT_RNUM_IDX]);
    int max_run_time         = atoi(argv[OUTPUT_TIME_IDX]);
    MAX_LIST_SIZE            = atoi(argv[OUTPUT_MAX_IDX]);
    global_list = initlist_create();


    pthread_t garbage_collector_thread;

    pthread_t writer_threads[writers_count];
    pthread_t reader_threads[readers_count];

    if (0 != pthread_create(&garbage_collector_thread, NULL, garbage_collect_thread, NULL))

        {       exit(errno);
        }

        for (int i = 0; i < writers_count; ++i)
        {
            if (0 != pthread_create(&writer_threads[i], NULL, writer_thread, NULL))
            {
                exit(errno);
            }
        }


        for (int x = 0; x < readers_count; ++x)
        {
            if (0 != pthread_create(&reader_threads[x], NULL, reader_thread, NULL))
            {
                exit(errno);
            }
        }

        sleep(max_run_time);
        //IMPORTANT
        //threads should die after this is set,but all threads wait for the mutex to free
        //in gcc - see "info threads" command in gdb

        stop_threads = 1;
        int list_size = initlist_size(global_list); 
        printf("List size: %d", list_size);

        for (int i = 0; i < list_size; ++i)
        {
            continue;
            printf("num is %d", initlist_pop_tail(global_list));
        }

        //this gets stuck also when waiting for mutex obviously...
        initlist_destroy(global_list);


    }

Answer 1

#include <pthread.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <errno.h>

#define USAGE_ERR "Usage: ./hw3 <WNUM> <RNUM> <MAX> <TIME>\n"

/* Argc parameter indexing consts */
#define INPUT_WNUM_IDX 1
#define INPUT_RNUM_IDX 2
#define OUTPUT_MAX_IDX 3
#define OUTPUT_TIME_IDX 4

typedef struct node {
    int value;

    struct node * previous;
    struct node * next;
}
node;

typedef struct {
    int length;
    node * head;
    node * tail;
    pthread_mutex_t mutex;
}
list;

list * global_list;
int stop_threads = 0;
int MAX_LIST_SIZE;
pthread_cond_t      gc_cond  = PTHREAD_COND_INITIALIZER;
pthread_mutex_t     gc_mutex = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t      read_cond  = PTHREAD_COND_INITIALIZER;
pthread_mutex_t     read_mutex = PTHREAD_MUTEX_INITIALIZER;

list * initlist_create();
void initlist_destroy(list * target_list);
list * initlist_push_head(list * target_list, int value);
int initlist_pop_tail(list * target_list);
void initlist_remove_last_k(list * target_list, int k);
int initlist_size(list * target_list);
pthread_mutex_t initlist_get_mutex(list * target_list);
void writer_thread();
void reader_thread();
void garbage_collect_thread();


list * initlist_create() {
    size_t list_size = sizeof(list);
    list * new_list = (list * ) malloc(list_size);
    new_list->head = NULL;
    new_list->tail = NULL;
    new_list->length = 0;
    if (0 != pthread_mutex_init( & (new_list->mutex), NULL)) {
        exit(errno);
    }
    return new_list;
}

void initlist_destroy(list * target_list) {
    node * current_node;
    node * temp_node;

    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }

    if (0 != target_list->length) {
        current_node = target_list->head;
        while (current_node != NULL) {
            temp_node = current_node->next;
            free(current_node);
            current_node = temp_node;
        }
    }

    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }

    if (0 != pthread_mutex_destroy( & (target_list->mutex))) {
        exit(errno);
    }

    free(target_list);
}

list * initlist_push_head(list * target_list, int value) {
    node * new_node;
    size_t node_size = sizeof(node);


    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }

    new_node = (node * ) malloc(node_size);
    if (NULL == new_node)
    {
        printf("Malloc failed\n" );
        exit(errno);
    }
    new_node->value = value;

    if (0 == target_list->length) {
        target_list->tail = new_node;
    }
    else {
        target_list->head->previous = new_node;
    }
    new_node->next = target_list->head;
    target_list->head = new_node;

    pthread_cond_signal(&read_cond);
    target_list->length++;
    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }
    return target_list;
}

int initlist_pop_tail(list * target_list) {
    int deleted_node_value;

    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }
    while(0 == target_list->length) {
        pthread_cond_wait(&read_cond, &target_list->mutex);
    }
    node * last_node = target_list->tail;
    deleted_node_value = last_node->value;
    target_list->tail = last_node->previous;
    if (last_node->previous != NULL) {
        last_node->previous->next = NULL;
        }
    else
    {
        target_list->head = NULL;

    }
    target_list->length--;
    if (0 != pthread_mutex_unlock( & ( target_list->mutex) )) {
        exit(errno);
    }
    last_node->next = NULL;
    last_node->previous = NULL;
    free(last_node);



    //  node *result = NULL;
    // lock(&list_ptr->mutex);
    // if (list_ptr->head != NULL) {
    //     result = list_ptr->tail;
    //     list_ptr->tail = result->prev;
    //     if (result->prev != NULL) {
    //         result->prev->next = NULL;
    //     }
    //     else {
    //         list_ptr->head = NULL;
    //     }
    //     list_ptr->length--;
    // }
    // unlock(&list_ptr->mutex);
    // if (result != NULL) {
    //     result->next = NULL;
    //     result->prev = NULL;
    // }
    // return result;

    return deleted_node_value;
}

void initlist_remove_last_k(list * target_list, int k) {
    int remove_size = k;
    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }
    if (k > target_list->length)
    {
        remove_size = target_list->length;
    }
    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }
    for (int i = 0; i < remove_size; ++i) {
        initlist_pop_tail(target_list);
    }
}

int initlist_size(list * target_list) {
    int list_size;

    if (0 != pthread_mutex_lock( & (target_list->mutex))) {
        exit(errno);
    }

    list_size = target_list->length;

    if (0 != pthread_mutex_unlock( & (target_list->mutex))) {
        exit(errno);
    }

    return list_size;
}

pthread_mutex_t initlist_get_mutex(list * target_list) {
    pthread_mutex_t list_mutex;

    list_mutex = target_list->mutex;

    return list_mutex;

}

void writer_thread()
{
    while (1)
    {
        if (stop_threads) {
            return;
        }
        if (MAX_LIST_SIZE < initlist_size(global_list))
        {

            pthread_cond_signal(&gc_cond);
        }
        initlist_push_head(global_list, rand());

    }
}


void reader_thread()
{
    while (1)
    {
        if (stop_threads) {
            return;
        }
        if (MAX_LIST_SIZE < initlist_size(global_list))
        {
            pthread_cond_signal(&gc_cond);
        }
        initlist_pop_tail(global_list);

    }
}

void garbage_collect_thread()
{
    while(1) {
        if (stop_threads) {
            return;
        }

        if (0 != pthread_mutex_lock( & (gc_mutex))) {
            exit(errno);
        }
        pthread_cond_wait(&gc_cond, &(gc_mutex));
        int remove_count = (initlist_size(global_list) / 2);
        if (0 == remove_count){
            continue;
        }
        initlist_remove_last_k(global_list, remove_count);
        printf("GC – %d items removed from the list\r\n", remove_count);
        if (0 != pthread_mutex_unlock( & (gc_mutex))) {
            exit(errno);
        }
    }
}

int main(int argc, char * * argv) {
    /* Validate arguments */
    if (5 != argc) {
        printf(USAGE_ERR);
        exit(errno);
    }

    int writers_count        = atoi(argv[INPUT_WNUM_IDX]);
    int readers_count        = atoi(argv[INPUT_RNUM_IDX]);
    int max_run_time         = atoi(argv[OUTPUT_TIME_IDX]);
    MAX_LIST_SIZE            = atoi(argv[OUTPUT_MAX_IDX]);
    global_list = initlist_create();


    pthread_t garbage_collector_thread;

    pthread_t writer_threads[writers_count];
    pthread_t reader_threads[readers_count];

    if (0 != pthread_create(&garbage_collector_thread, NULL, garbage_collect_thread, NULL))

    {   exit(errno);
    }

    for (int i = 0; i < writers_count; ++i)
    {
        if (0 != pthread_create(&writer_threads[i], NULL, writer_thread, NULL))
        {
            exit(errno);
        }
    }


    for (int x = 0; x < readers_count; ++x)
    {
        if (0 != pthread_create(&reader_threads[x], NULL, reader_thread, NULL))
        {
            exit(errno);
        }
    }


    sleep(max_run_time);
    stop_threads = 1;
    int list_size = initlist_size(global_list);
    printf("List size: %d\r\n", list_size);

    for (int i = 0; i < readers_count; ++i)
    {
        pthread_cancel(&reader_threads[i]);
    }
     for (int i = 0; i < writers_count; ++i)
    {
        pthread_cancel(&writer_threads[i]);
    }

    for (int i = 0; i < list_size; ++i)
    {
        printf("num is %d\r\n", initlist_pop_tail(global_list));
    }

    initlist_destroy(global_list);


}

Answer 2

I ran your code in a debugger and there is an attempt to free the same pointer twice in this code from initlist_destroy:

if (0 != target_list->length) {
    current_node = target_list->head;
    while (current_node != NULL) {
        temp_node = current_node->next;
        // Added the following line to view pointer values
        printf("Freeing %p...\n", current_node);
        free(current_node);
        current_node = temp_node;
    }
}

When I print out the pointer values, I get output like this:

GC – 5 items removed from the list
List size: 4
Freeing 0x7fc1a1602d20...
Freeing 0x7fc1a15045e0...
Freeing 0x7fc1a3569c40...
Freeing 0x7fc1a3569c40...

As you can see, you attempt to free the same pointer twice. You have a defect in your list handling code. This is not surprising. Linked list code is hard to write.

My recommendation is to write a single-threaded program that

1. Creates a linked list
2. Adds a small number of items to the list (e.g. 3)
3. Removes each item from the list
4. Verifies the list is empty

I would write a function that prints the list pointers in an easy to read way (e.g. a table of hex values). Call that function after each modification to the list. It should be easy to see what you are doing wrong.

Update

I wrote a program that implements the suggestions above:

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <pthread.h>
#include <inttypes.h>

#define PTR_FMT "0x%016" PRIXPTR

void perror_location(const char *file, int line_number) {
    char location[80];
    snprintf(location, sizeof(location), "%s:%d", file, line_number);
    perror(location);
    exit(errno);
}

#define PERROR() perror_location(__FILE__, __LINE__)

void *malloc_safe(size_t size) {
    void *result = malloc(size);
    if (NULL == result) {
        PERROR();
    }
    return result;
}

#define MALLOC(type) \
    (type *) malloc_safe(sizeof(type))

void lock(pthread_mutex_t *mutex) {
    if (0 != pthread_mutex_lock(mutex)) {
        PERROR();
    }
}

void unlock(pthread_mutex_t *mutex) {
    if (0 != pthread_mutex_unlock(mutex)) {
        PERROR();
    }
}

typedef struct _node {
    int value;
    struct _node *next;
    struct _node *prev;
} node;

typedef struct _list {
    node *head;
    node *tail;
    size_t length;
    pthread_mutex_t mutex;
} list;

list *list_init(void) {
    list *result = MALLOC(list);
    result->head = NULL;
    result->tail = NULL;
    result->length = 0;
    if (0 != pthread_mutex_init(&result->mutex, NULL)) {
        PERROR();
    }
    return result;
}

node *list_add(list *list_ptr, int value) {
    node *result = MALLOC(node);
    result->value = value;
    result->next = NULL;
    result->prev = NULL;
    lock(&list_ptr->mutex);
    if (list_ptr->head == NULL) {
        list_ptr->head = result;
        list_ptr->tail = result;
    }
    else {
        result->prev = list_ptr->tail;
        list_ptr->tail->next = result;
        list_ptr->tail = result;
    }
    list_ptr->length++;
    unlock(&list_ptr->mutex);
    return result;
}

node *list_remove(list *list_ptr) {
    node *result = NULL;
    lock(&list_ptr->mutex);
    if (list_ptr->head != NULL) {
        result = list_ptr->tail;
        list_ptr->tail = result->prev;
        if (result->prev != NULL) {
            result->prev->next = NULL;
        }
        else {
            list_ptr->head = NULL;
        }
        list_ptr->length--;
    }
    unlock(&list_ptr->mutex);
    if (result != NULL) {
        result->next = NULL;
        result->prev = NULL;
    }
    return result;
}

void list_print(list *list_ptr) {
    lock(&list_ptr->mutex);
    printf("----------\n");
    printf("length = %ld\n", list_ptr->length);
    printf("%-18s %-18s %-18s\n", "list", "list->head", "list->tail");
    printf(PTR_FMT " " PTR_FMT " " PTR_FMT "\n",
           (uintptr_t) list_ptr,
           (uintptr_t) list_ptr->head,
           (uintptr_t) list_ptr->tail);
    if (list_ptr->head != NULL) {
        printf("%-18s %-18s %-18s\n", "node", "node->next", "node->prev");
        node *current = list_ptr->head;
        do {
            printf(PTR_FMT " " PTR_FMT " " PTR_FMT "\n",
                   (uintptr_t) current,
                   (uintptr_t) current->next,
                   (uintptr_t) current->prev);
            current = current->next;
        } while (current != NULL);
    }
    unlock(&list_ptr->mutex);
}

int main(void) {
    list *linked_list = list_init();

    printf("Add items...\n");
    for (int value = 1; value <= 3; value++) {
        list_add(linked_list, value);
        list_print(linked_list);
    }

    printf("Remove items...\n");
    while (1) {
        node *result = list_remove(linked_list);
        if (NULL == result) {
            break;
        }
        free(result);
        list_print(linked_list);
    }

    if ((linked_list->head != NULL) || (linked_list->tail != NULL)) {
        printf("ERROR: List is not empty\n");
        return EFAULT;
    }

    free(linked_list);

    return 0;
}

Output

Add items...
----------
length = 1
list               list->head         list->tail        
0x00007F8180C031B0 0x00007F8180C03210 0x00007F8180C03210
node               node->next         node->prev        
0x00007F8180C03210 0x0000000000000000 0x0000000000000000
----------
length = 2
list               list->head         list->tail        
0x00007F8180C031B0 0x00007F8180C03210 0x00007F8180C03230
node               node->next         node->prev        
0x00007F8180C03210 0x00007F8180C03230 0x0000000000000000
0x00007F8180C03230 0x0000000000000000 0x00007F8180C03210
----------
length = 3
list               list->head         list->tail        
0x00007F8180C031B0 0x00007F8180C03210 0x00007F8180C03250
node               node->next         node->prev        
0x00007F8180C03210 0x00007F8180C03230 0x0000000000000000
0x00007F8180C03230 0x00007F8180C03250 0x00007F8180C03210
0x00007F8180C03250 0x0000000000000000 0x00007F8180C03230
Remove items...
----------
length = 2
list               list->head         list->tail        
0x00007F8180C031B0 0x00007F8180C03210 0x00007F8180C03230
node               node->next         node->prev        
0x00007F8180C03210 0x00007F8180C03230 0x0000000000000000
0x00007F8180C03230 0x0000000000000000 0x00007F8180C03210
----------
length = 1
list               list->head         list->tail        
0x00007F8180C031B0 0x00007F8180C03210 0x00007F8180C03210
node               node->next         node->prev        
0x00007F8180C03210 0x0000000000000000 0x0000000000000000
----------
length = 0
list               list->head         list->tail        
0x00007F8180C031B0 0x0000000000000000 0x0000000000000000

I used a debugger to fix my own list handling. I recommend using one to fix yours.