1

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);


    }
lippy1234
  • 11
  • 4
  • Note: Interesting Unicode character in comment `... spots larger than 1ר` Suggest removing distraction - assuming it is not part of the problem. – chux - Reinstate Monica Jan 04 '17 at 19:57
  • removed - however comments are strippe during the compilation... – lippy1234 Jan 04 '17 at 19:59
  • Perhaps `void reader_thread()` --> `void *reader_thread(void *x_void_ptr)`. Found by enabling all warnings - it saves debug time, try it. [Ref](http://timmurphy.org/2010/05/04/pthreads-in-c-a-minimal-working-example/) – chux - Reinstate Monica Jan 04 '17 at 20:02
  • tried,did not effect the output.the 2 issues are with synchronization as well as with this memory corruption,can't seem to find the issue. – lippy1234 Jan 04 '17 at 20:06
  • It's more about readability. Have you tried valgrind? Are you sure that `pthread_cond_wait(&read_cond, &read_mutex);` inside `initlist_pop_tail` is called with a locked mutex? – 1000ml Jan 04 '17 at 20:07
  • Did you enable all warnings to find the other functions that have this problem too? Was code corrected in those functions to return a valid value? – chux - Reinstate Monica Jan 04 '17 at 20:07
  • 1000ml - pthread_cond_wait called inside pop_tail locks the mutex as soon as the condition is set,and once it is available according to the docs. chux-i did - most are simply conventional - not related to memory leaks. – lippy1234 Jan 04 '17 at 20:10
  • `They shall be called with mutex locked by the calling thread or undefined behavior results.`: https://linux.die.net/man/3/pthread_cond_wait – 1000ml Jan 04 '17 at 20:11
  • 1000ml - does that mean i need to lock the mutex before i block on the cond_wait?if so - that is problematic - because the condition is triggered by a writer thread - that has to lock the same mutex(in this scenario - the reader thread will block the general mutex, and wait for a condition to be set by a writer thread.This writer thread will wait for the mutex to free - a deadlock).look at the answer to this question:http://stackoverflow.com/questions/16522858/understanding-of-pthread-cond-wait-and-pthread-cond-signal – lippy1234 Jan 04 '17 at 20:14
  • Yes, but `cond_wait` will release the lock immediately and put the thread to sleep until a signal is received. – 1000ml Jan 04 '17 at 20:18
  • Good point.i edited that(see the original question) - locked the mutex before waiting for the condition,but the problem remains.Also,does it make sense to wait for a writer to signal and only then read value? – lippy1234 Jan 04 '17 at 20:27
  • Isn't that what you're already doing? Yes that makes sense, otherwise you would have to continuously poll for new elements. But you might want to call `pop_tail` in a loop and handle all elements that are already queued, and only then fall back to sleep. You can't predict how the threads are scheduled so it's possible that `push_head` is called 3 times in a row before `pop_tail` is called once. – 1000ml Jan 04 '17 at 20:39
  • I assume you're on linux since you're using gdb, so give valgrind a try. It can tell you where a double-delete occurs. – 1000ml Jan 04 '17 at 20:42
  • instead of waiting in initlist_pop_tail until i get signaled - i only wait for the signal if the length of the list is 0.however - now i get a segmentation fault.Can you spot the issue?i edited the original answer to include the revised pop_tail and push_Head code – lippy1234 Jan 04 '17 at 20:47
  • `if(0 == target_list->length) { cond_wait(); }` you should make that a `while(...)` because of spurious wakeups. – 1000ml Jan 04 '17 at 20:54
  • edit:okay - replaced the if with a while and the segfault is gone- however the memory problem remains.What can be done except for valgrind? – lippy1234 Jan 04 '17 at 20:57
  • i gave up and used valgrind - enclosed the output in the answer.any idea what is the issue? – lippy1234 Jan 04 '17 at 21:26
  • @lippy1234: What exists to prevent the list length from going negative here: `target_list->length--;`? –  Jan 04 '17 at 21:48
  • @DavidCullen - this piece of code only runs if the length of the list is greater than 1(that is why i use the conditional variable and the pthread_cond_wait) – lippy1234 Jan 04 '17 at 21:51
  • @lippy1234: Why is `initlist_remove_last_k` accessing `target_list` without acquiring its mutex? –  Jan 04 '17 at 21:51
  • @DavidCullen - you are correct - i added a lock in the first lines that check the size of the list.however - it did not affect the result. – lippy1234 Jan 04 '17 at 21:56

2 Answers2

0
#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);


}
lippy1234
  • 11
  • 4
0

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.

  • I tried going over the initlist_destroy function,but i cant figure out why the error occurs.any idea? – lippy1234 Jan 06 '17 at 12:41
  • Yes, you are doing something wrong when you add elements to your list or when you remove elements from your list. The `next` pointer of the last element of your list should be `NULL`. Instead, it points to the last element of the list. You should be able to see the problem by stepping through the list handling code in a debugger. –  Jan 06 '17 at 14:16
  • i changed it in the code,it is in the answer down.but now,when i run the code with 10 writers,10 readers,10 meax size and 100 seconds,it gets stuck on the cond_wait in the initlist_pop_tail function,and i cant seem to figure why? – lippy1234 Jan 06 '17 at 14:22
  • I ran the program below and it crashes in `initlist_destroy` because it tries to free a pointer that was not allocated. Have you tried debugging your list handling code in a single-threaded program? –  Jan 06 '17 at 15:38
  • I have.i do not undersand where the issue is.i am freeing the memory once in initlist_pop_tail(only once i've removed all reffferences to it).Any ideas? – lippy1234 Jan 06 '17 at 15:59
  • I modified your code in your answer to run single-threaded. I called `initlist_push_head` three times. I added my `list_print` function and ran it after each call to `initlist_pop_tail`. After each call to `initlist_pop_tail`, `list_print` still shows one more element in the list than the list length. Your `initlist_pop_tail` appears to be defective. –  Jan 06 '17 at 16:26
  • That is strange - what the function does is remove any refference to the last node,and free it.It is only 6 lines,i cant seemt ofigrue why that would happend – lippy1234 Jan 06 '17 at 16:38
  • I replaced the code in your `initlist_pop_tail` with a version of the code in my `list_remove` and `list_print` displayed the correct values and the program ran to completion. You need to look more closely at the code in `initlist_pop_tail`. –  Jan 06 '17 at 20:16
  • i looked into your list_remove code - and replicated it,however,every seoncd or third time i run my code it gets stuck while printing the list,and i do not know why.Try running my code and you will see that the second time it runs(running with 10 10 10 100 as the arguments) - it wil lget stuck – lippy1234 Jan 06 '17 at 20:42
  • You need to initialize `next` and `previous` to `NULL` in `initlist_push_head`. Also, I had to remove the `while` loop and the read signal code from `initlist_pop_tail`. But now I have a version of your program that runs to completion. You will have to add an explanation of how the signals are supposed to work in your original question. I do not understand the purpose of the read signal, and it appears to cause a deadlock. –  Jan 06 '17 at 21:06
  • The read signal is a requirment in the project - the reader should wait until the list contains more than 1 value using a condition variable.It does cause a deadlock - i cant seem to figure out why and when – lippy1234 Jan 07 '17 at 07:17