c - 双链表 - 内存损坏

Question

我试图分两部分实现双链表:第一个是创建列表的实际功能；第二个是模拟器 - 包含一些线程、读取器和写入器(每个线程都在 while 循环中弹出和插入双链表)，以及一个垃圾收集器线程，如果列表太大(根据 argv)则清理列表。该列表使用互斥锁和条件变量以使其线程安全。但是 - 每当我运行它时，我都会收到双重空闲/内存损坏(fasttop)错误，我不知道为什么。我会很感激一些帮助。

#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

我在调试器中运行了您的代码，并且试图在这段代码中从 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;
    }
}

当我打印出指针值时，我得到这样的输出:

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

如您所见，您尝试释放同一个指针两次。您的列表处理代码存在缺陷。这并不奇怪。链表代码难写。

我的建议是编写一个单线程程序

1. 创建一个链表
2. 向列表中添加少量项目(例如 3)
3. 从列表中删除每一项
4. 验证列表是否为空

我会编写一个函数，以易于阅读的方式打印列表指针(例如，十六进制值表)。在每次修改列表后调用该函数。应该很容易看出您做错了什么。

更新

我编写了一个实现上述建议的程序:

#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;
}

输出

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

我使用调试器来修复我自己的列表处理。我建议使用一个来修复你的问题。