C Hash表实现中的SEG故障

Question

我一直在研究这个动态的内存分配问题集，我们必须在其中实现malloc和free，而我在实施免费方面遇到了很多努力。除了释放适当的内存之外，还有一个统计结构，我们必须使用Malloc/free的每个调用来更新，该呼叫符合活动分配的大小，即Active_size。为了准确更新Active_size问题集，我们应该实现HASH表。我制作了Hash表以容纳Malloc Pointer及其分配的大小，并提供了一个Lookup_size功能，然后将其用于免费功能中以更新Active_Size。但是，看来Lookup_size函数有缺陷，并在此行会导致SEG故障：

return tmp->payload;

如果有人遇到其他错误，我也将在整个代码下方留下，但是如果某人可以找出原因，那将是一个巨大的帮助这个SEG故障。谢谢。

#define M61_DISABLE 1
#include "m61.hh"
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cinttypes>
#include <cassert>

// Hash table size
#define TABLE_SIZE 10

/// m61_malloc(sz, file, line)
///    Return a pointer to `sz` bytes of newly-allocated dynamic memory.
///    The memory is not initialized. If `sz == 0`, then m61_malloc must
///    return a unique, newly-allocated pointer value. The allocation
///    request was at location `file`:`line`.
static m61_statistics stat_count = {0, 0, 0, 0, 0, 0, 0, 4294967295};

// Hash table item defintion
typedef struct ht_item {
    void* address;
    unsigned long long payload;
    struct ht_item* next;
} ht_item;

// Initialize hash table
ht_item* hash_table[TABLE_SIZE];

// Mod hash function
int hash_func(void* address) {
    uintptr_t hash_value = (uintptr_t) address % TABLE_SIZE;
    return hash_value;
}

// Empty hash table
void init_hash_table() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hash_table[i] = NULL;
    }
}

// Hash table item insertion function
bool insert_item(ht_item* item) {
    // Check if there actually is an item
    if (item == NULL) {
        return false;
    }

    // Insert item to front of the l_list (assign current val to next and new value to hash table)
    int index = hash_func(item->address);
    item->next = hash_table[index];
    hash_table[index] = item;
    return true;
}

// Hash table functiont that finds allocated sizes by mallocc
unsigned long long lookup_size(void* p) {
    if (p == NULL) {
        return 0;
    }

    int index = hash_func(p); 
    ht_item* tmp = hash_table[index];
    while (tmp != NULL && tmp->address != p) {
        tmp = tmp->next;
    }
    return tmp->payload;
}

void* m61_malloc(size_t sz, const char* file, long line) {
    (void) file, (void) line;   // avoid uninitialized variable warnings
    // Your code here.
    if (!base_malloc(sz)){
        ++stat_count.nfail;
        stat_count.fail_size += sz;
    }

    else {
        ++stat_count.nactive;
        ++stat_count.ntotal;
        stat_count.active_size += sz;
        stat_count.total_size += sz;

        init_hash_table();
        void* p = base_malloc(sz);
        ht_item* malloc_data = (ht_item*) malloc(sizeof(ht_item));
        malloc_data->address = p;
        malloc_data->payload = sz;
        malloc_data->next = NULL;
        insert_item(malloc_data);
    }
    return base_malloc(sz);
}


/// m61_free(ptr, file, line)
///    Free the memory space pointed to by `ptr`, which must have been
///    returned by a previous call to m61_malloc. If `ptr == NULL`,
///    does nothing. The free was called at location `file`:`line`.

void m61_free(void* ptr, const char* file, long line) {
    (void) file, (void) line;   // avoid uninitialized variable warnings
    // Your code here.
    if (ptr){
        --stat_count.nactive;
        stat_count.active_size -= lookup_size(ptr);
    }
    base_free(ptr);
}

Answer 1

在进行答案之前，我要这么说：

除了从编译器输出中对代码进行反向工程，直到其工作不好，将一块内存管理代码放在没有办法的人身上。

请在提出另一个问题之前对此链接进行仔细研究。 https://stackoverflow.com/help/help/minimal-reproducible-example-a>

---

因此

while (tmp != NULL && tmp->address != p) {
    tmp = tmp->next;
}
return tmp->payload;

查看循环条件：

while (tmp != NULL && tmp->address != p) { ... }

假设 tmp-＆gt; address 永远不会等于 p ，只要 tmp 不是 null，它就会继续迭代。换句话说，当 tmp 是 null 时，它会停止。

然后，在下一行，您尝试访问 tmp 。但是 TMP 当时已经是 null ！因此，您几乎要这样做：

return NULL->payload;

这就是导致细分故障的原因。

如果此循环在有效的指针上呼叫时始终要成功，那么在某些情况下，您可能不会可靠地调用 insert_item （在 m61_malloc 中）？

或者，如果 insert_item 不应在每次呼叫 m61_malloc 上调用，那么您不会期望在每个调用 lookup_size ，因此，您应该检查 tmp 在循环后不是 null 。 （无论如何，您都应该这样做，因为有人可能会用无效的指针调用 m61_free ）。

---

至于此错误的原因， m61_malloc 似乎很可变...

if (!base_malloc(sz)) {
    ...
} else {
    ...
    void* p = base_malloc(sz);
    ...
}
return base_malloc(sz);

当第一个调用 base_malloc 不返回 null base_malloc 时，您希望这会做什么/代码>？就目前而言，它进入了“ else”分支，第二次调用 base_malloc （再次分配或返回未处理的 null ），然后调用<代码> base_malloc 在返回语句中第三次（再次，可能返回 null ）。

在这种情况下，存储在哈希表中的指针是第二个调用返回到 base_malloc 的指针，但是返回的指针（并且可以传递到 m61_free） 稍后）是第三个调用返回到 base_malloc （未存储在哈希表中）的一个。

也许这是造成错误的真正原因？

编辑：更改 m61_malloc 如下所示，尽管仍然错了，但修复了此特定的segfault。

if (!base_malloc(sz)) {
    ...
    return NULL;
} else {
    ...
    void* p = base_malloc(sz);
    ...
    return p;
}