为什么 Valgrind 在此哈希 table 测试用例中发现错误？

Question

我自己在 C 中开发了一个并发通用哈希 table。

hash_table.h的相关内容：

typedef struct list_node {
    void * data;
    struct list_node * next;
} list_node_t;


typedef struct hash_table {
    int max_size;
    int count;
    list_node_t * * elements;
    pthread_rwlock_t * locks;
    pthread_rwlock_t global_table_lock;
    hash_table_compare_function compare;
    hash_table_hash_function hash;
} hash_table_t;

hash_table.c的相关内容：

#define LOCK_RD(lock)   pthread_rwlock_rdlock(&lock);
#define LOCK_WR(lock)   pthread_rwlock_wrlock(&lock);
#define UNLOCK(lock)    pthread_rwlock_unlock(&lock);

bool
hash_table_remove(hash_table_t * table, void * element)
{
    int hash_value = table->hash(element);
    list_node_t * node, * prev;

    LOCK_WR(table->locks[hash_value]);

    node = table->elements[hash_value];
    prev = NULL;

    while (node) {
        if (!table->compare(node->data, element)) {
            // value is first item in the list
            if (node == table->elements[hash_value]) {
                table->elements[hash_value] = node->next;
                free(node);
                UNLOCK(table->locks[hash_value]);
                LOCK_WR(table->global_table_lock);
                table->count--;
                UNLOCK(table->global_table_lock);
                return true;
            } else {
                // link previous node with one after current
                prev->next = node->next;
                free(node);
                UNLOCK(table->locks[hash_value]);
                LOCK_WR(table->global_table_lock);
                table->count--;
                UNLOCK(table->global_table_lock);
                return true;
            }
        }
        prev = node;
        node = node->next;
    }

    UNLOCK(table->locks[hash_value]);

    return false;
}

我写了一个使用字符串的测试用例，相关代码如下：

#include "hashtable.h"

#define NUM_THREADS 2
#define NUM_STRINGS 154560
#define NUM_LOOKUPS 10000


void *
do_work(void * data)
{
    int thread_id = *(int*)data;

    // write "threadX.txt" to filename, where X is the given thread id
    char filename[64];
    strcpy(filename, "thread");
    char thread_id_str[4];
    sprintf(thread_id_str, "%d", thread_id);
    strcat(filename, thread_id_str);
    strcat(filename, ".txt");

    FILE * file = fopen(filename, "r");
    char buffer[128];
    int i, num_str_per_thread = NUM_STRINGS / NUM_THREADS;
    char * str_array[num_str_per_thread];

    for (i = 0; i < num_str_per_thread; i++) {
        fgets(buffer, 128, file);

        str_array[i] = calloc((strlen(buffer) + 1), sizeof(char));
        strcpy(str_array[i], buffer);
    }

    fclose(file);

    for (i = 0; i < num_str_per_thread; i++)
        hash_table_insert(table, str_array[i]);

    for (i = 0; i < NUM_LOOKUPS; i++)
        hash_table_contains(table, str_array[rand() % num_str_per_thread]);

    for (i = 0; i < num_str_per_thread / 2; i++)
        hash_table_remove(table, str_array[rand() % num_str_per_thread]);

    //sleep(2); NOTE: no read errors reported if I leave this sleep() here.

    for (i = 0; i < num_str_per_thread; i++)
        if (str_array[i])
            free(str_array[i]);

    return NULL;
}


void
create_workers()
{
    pthread_t threads[NUM_THREADS];
    int ids[NUM_THREADS];
    int i;

    for (i = 0; i < NUM_THREADS; i++)
        ids[i] = i + 1;

    for (i = 0; i < NUM_THREADS; i++)
        pthread_create(&threads[i], NULL, do_work, (void*)&ids[i]);

    for (i = 0; i < NUM_THREADS; i++)
        pthread_join(threads[i], NULL);
}

测试用例应该按如下方式工作：有两个文件，thread1.txt 和 thread2.txt，每个文件都包含我预先生成的 unique 字符串.我创建了两个线程，每个线程将从一个文件中读取并将每个字符串存储在一个名为 str_array 的字符串数组中。然后，他们会将所有这些字符串插入哈希 table 并执行随机搜索 (hash_table_contains) 和删除 (hash_table_remove)。然后，每个人都将释放他们各自的字符串数组。但是，当我运行这个测试用例时，Valgrind 报告如下：

请注意没有内存泄漏。我从这些错误中得到的是，线程在调用 hash_table_remove 时试图释放已被 free(str_array[i]) 释放的内存。然而，这没有意义，因为 hash_table_remove 在 free(str_array[i] 之前被调用。我不知道是什么给我这些无效读取。

提前致谢！

Answer 1

在这里，您的线程最多删除它插入的字符串的一半：

for (i = 0; i < num_str_per_thread / 2; i++)
    hash_table_remove(table, str_array[rand() % num_str_per_thread]);

（实际上，它最有可能删除它插入的字符串的大约39%）。

然后，它继续释放所有它插入的字符串：

for (i = 0; i < num_str_per_thread; i++)
    if (str_array[i])
        free(str_array[i]);

然而，这些字符串中至少有一半（很可能是 ~61%）仍在散列中 table，其他线程将在扫描链式散列桶条目时尝试比较它们.那是你的 use-after-free 错误。

您可以在删除它们时释放它们，而不是释放所有字符串：

for (i = 0; i < num_str_per_thread / 2; i++)
{
    int str_index = rand() % num_str_per_thread;

    if (str_array[str_index])
    {
        hash_table_remove(table, str_array[str_index]);
        free(str_array[str_index]);
        str_array[str_index] = NULL;
    }
}

此时，str_array[] 中的 non-NULL 条目是仍然存在于散列 table 中的字符串。在将它们从散列 table 中删除（或散列 table 不再使用）之前，您无法释放它们。

您的测试用例出现此错误的事实很好地表明您的界面的人体工程学设计不如应有的好。您可能应该考虑一种设计，其中插入的字符串的所有权转移到散列 table，以便 hash_table_remove() 本身负责释放字符串。

为什么 Valgrind 在此哈希 table 测试用例中发现错误？

Why is Valgrind finding errors in this hash table test case?

c

memory

valgrind

pthreads