C语言线性探测哈希表resize函数内存泄漏问题求助

问题概述 #

实现了一个线性探测哈希表，仅在hash_map_add触发resize_hash_map时出现内存泄漏，通过macOS的leaks命令检测到2处共32字节的泄漏。

环境 #

• 架构：Apple Silicon（macOS aarch64）
• 编译器：gcc
• 编译参数：-std=c17 -Wall -g

实现代码 #

hash_map.h #

#ifndef TERRACRAFT_HASH_MAP_H
#define TERRACRAFT_HASH_MAP_H

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>

#ifndef NDEL
#define NDEL ((void*) 1)  // void pointer del tag
#endif

typedef struct HashMap HashMap;

struct HashMap {
    void** items; // pointer to array of pointers to items
    char** keys; // pointer to array of strings
    unsigned long size;
    unsigned long non_null;
    unsigned long capacity;
};

HashMap* create_hash_map(unsigned long capacity);
void destroy_hash_map(HashMap* map);
void resize_hash_map(HashMap* map);
void* hash_map_get(HashMap* map, char* key);
bool hash_map_add(HashMap* map, char* key, void* item);

// TODO remove function

#endif //TERRACRAFT_HASH_MAP_H

hash_map.c #

#include "collections/hash_map.h"

// based on public domain implementation from: http://www.cse.yorku.ca/~oz/hash.html
// note: static here limits this function to this file only
static unsigned long sdbm_hashcode(const char* str) {
    unsigned long hash = 0;
    int c;

    while ((c = *str++)) hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}

HashMap* create_hash_map(unsigned long capacity) {
    size_t val_bytes = sizeof(void*) * capacity;
    size_t key_bytes = sizeof(char*) * capacity;
    // create and zero arrays
    void** items = malloc(val_bytes);
    memset(items, NULL, val_bytes);

    char** keys = malloc(key_bytes);
    memset(keys, NULL, key_bytes);

    HashMap* map = malloc(sizeof(HashMap));
    map->items = items;
    map->keys = keys;
    map->size = 0;
    map->non_null = 0;
    map->capacity = capacity;

    return map;
}

void destroy_hash_map(HashMap* map) {
    for (int i = 0; i < map->size; i++) {
        if (map->items[i] != NULL) {
            free(map->items[i]);
        }

        if (map->keys[i] != NULL) {
            free(map->keys[i]);
        }
    }

    free(map->items);
    free(map->keys);
    free(map);

    map = NULL;
}

void resize_hash_map(HashMap* map) {
    printf("resizing hash map\n");
    // TODO: this may be leaking memory

    // smallest non-negative integer d, where 2^d ≥ 3n
    // we maintain this invariant to support hash functions that only work on table sizes that are a power of 2
    unsigned long d = 1;

    // bit shift d to go through the base 2 powers: 2^d until we find a value where 2^d >= 3n
    // the bit shift is an efficient way to do base 2 powers.
    while ((1<<d) < 3*map->capacity) d++;

    unsigned long new_len = (1<<d);

    // create and zero new arrays
    size_t item_bytes = sizeof(void*) * new_len;
    size_t key_bytes = sizeof(char*) * new_len;
    void** new_item_arr = malloc(item_bytes);
    memset(new_item_arr, NULL, item_bytes);

    char** new_key_arr = malloc(key_bytes);
    memset(new_key_arr, NULL, key_bytes);

    map->size = map->capacity;
    map->non_null = map->size;

    // copy old arrays to new array
    for (int i = 0; i < map->size; i++) {
        if (map->keys[i] == NULL || map->keys[i] == NDEL) continue;

        unsigned long k = sdbm_hashcode(map->keys[i]) % new_len;

        // linearly prob from position k
        while (new_key_arr[k] != NULL) k = (k == new_len-1) ? 0 : k + 1; // increment with wrap around

        new_key_arr[k] = map->keys[i];
        new_item_arr[k] = map->items[i];
    }

    // free pointers to old arrays but not their contents since the contents were moved to the new array
    free(map->keys);
    free(map->items);

    // set new arrays
    map->keys = new_key_arr;
    map->items = new_item_arr;

    // set new capacity
    map->capacity = new_len;
}

void* hash_map_get(HashMap* map, char* key) {
    unsigned long hash = sdbm_hashcode(key) % map->capacity;

    // linear probe to check for key
    while(map->keys[hash] != NULL) {
        // check if the key was found
        if (map->keys[hash] != NDEL && strcmp(map->keys[hash], key) == 0) {
            return map->items[hash];
        }
        hash = (hash == map->capacity-1) ? 0 : hash + 1;
    }

    // key not in table, return nothing
    return NULL;
}

bool hash_map_add(HashMap* map, char* key, void* item) {
    void* existing_item = hash_map_get(map, key);
    if (existing_item != NULL && existing_item != NDEL) return false;
    if (2*(map->non_null+1) > map->capacity) resize_hash_map(map); // allow for a maximum of 50% occupancy
    unsigned long hash = sdbm_hashcode(key) % map->capacity;

    // linear probe to insert
    while (map->keys[hash] != NULL && map->keys[hash] != NDEL) hash = (hash == map->capacity-1) ? 0 : hash + 1;

    if (map->keys[hash] == NULL) map->non_null++;
    map->size++;

    // create memory for string and copy key to that block of memory
    size_t key_len = strlen(key);
    map->keys[hash] = malloc(key_len * sizeof(char));
    strncpy(map->keys[hash], key, key_len+1);
    map->keys[hash][key_len] = '\0';  // strncpy does not copy terminator,  manually add it

    // set the item
    map->items[hash] = item;

    return true;
}

main.c #

#include <stdio.h>
#include <stdlib.h>

#include "collections/hash_map.h"

typedef struct {
    int x, y;
} Point;

void print_point(Point* point) {
    printf("Point: (%d, %d)\n", point->x, point->y);
}

int main() {
    HashMap* map = create_hash_map(2);
    Point* one = malloc(sizeof(Point));
    one->x = 1;
    one->y = 2;

    Point* two = malloc(sizeof(Point));
    two->x = 3;
    two->y = 4;

    hash_map_add(map, "one", one);
  
    /*
     * Note:
     * When adding an item that will cause the hash map to resize, a memory leak is introduced.
     */
    hash_map_add(map, "two", two);

    Point* one_result = hash_map_get(map, "one");
    print_point(one_result);
    
    Point* two_result = hash_map_get(map, "two");
    print_point(two_result);

    destroy_hash_map(map);

    // wait for user input, gives me time to run the MacOS 'leaks' command on the executable
    // Is there a better way besides running valgrind on a linux vm? I'm on an Apple silicon mac.
    getchar();
    return 0;
}

leaks检测输出 #

Process 64507 is not debuggable. Due to security restrictions, leaks can only show or save contents of readonly memory of restricted processes.

Process:         terracraft [64507]
Path:            /Users/USER/*/terracraft
Load Address:    0x1027bc000
Identifier:      terracraft
Version:         ???
Code Type:       ARM64
Platform:        macOS
Parent Process:  clion [62506]

Date/Time:       2023-02-10 09:09:51.751 -0400
Launch Time:     2023-02-10 09:09:44.092 -0400
OS Version:      macOS 12.6.3 (21G419)
Report Version:  7
Analysis Tool:   /usr/bin/leaks

Physical footprint:         1617K
Physical footprint (peak):  1617K
----

leaks Report Version: 4.0
Process 64507: 1059 nodes malloced for 92 KB
Process 64507: 2 leaks for 32 total leaked bytes.

    2 (32 bytes) << TOTAL >>
      1 (16 bytes) ROOT LEAK: 0x600001120180 [16]
      1 (16 bytes) ROOT LEAK: 0x6000011201c0 [16]

泄漏原因分析 #

1. 销毁函数遍历范围错误：destroy_hash_map中循环条件为i < map->size，但哈希表的元素可能分布在整个数组（容量为map->capacity）的任意位置，而非仅前map->size个索引。resize后数组容量增大，元素可能被哈希到旧size之外的位置，这些位置的key和item无法被遍历到，导致内存泄漏。

2. resize时size和non_null值被错误覆盖：resize_hash_map中map->size = map->capacity;和map->non_null = map->size;这两行完全错误，将size设置为旧数组的容量，进一步加剧了销毁时的遍历范围错误，同时导致哈希表内部状态混乱。

修复方案 #

修复destroy_hash_map函数 #

将循环条件改为遍历整个数组容量，同时跳过NDEL标记避免无效释放：

void destroy_hash_map(HashMap* map) {
    // 遍历整个哈希表数组，而非仅前size个元素
    for (int i = 0; i < map->capacity; i++) {
        if (map->items[i] != NULL && map->items[i] != NDEL) {
            free(map->items[i]);
        }

        if (map->keys[i] != NULL && map->keys[i] != NDEL) {
            free(map->keys[i]);
        }
    }

    free(map->items);
    free(map->keys);
    free(map);
}

修复resize_hash_map函数 #

删除错误的size和non_null赋值，重新统计有效元素：

void resize_hash_map(HashMap* map) {
    printf("resizing hash map\n");

    unsigned long d = 1;
    while ((1<<d) < 3*map->capacity) d++;
    unsigned long new_len = (1<<d);

    size_t item_bytes = sizeof(void*) * new_len;
    size_t key_bytes = sizeof(char*) * new_len;
    void** new_item_arr = malloc(item_bytes);
    memset(new_item_arr, NULL, item_bytes);

    char** new_key_arr = malloc(key_bytes);
    memset(new_key_arr, NULL, key_bytes);

    // 保存原有有效元素数量，重置size和non_null
    map->size = 0;
    map->non_null = 0;

    // 复制旧数组有效元素到新数组，遍历旧数组的全部容量
    for (int i = 0; i < map->capacity; i++) {
        if (map->keys[i] == NULL || map->keys[i] == NDEL) continue;

        unsigned long k = sdbm_hashcode(map->keys[i]) % new_len;
        while (new_key_arr[k] != NULL) k = (k == new_len-1) ? 0 : k + 1;

        new_key_arr[k] = map->keys[i];
        new_item_arr[k] = map->items[i];
        // 更新size和non_null
        map->size++;
        map->non_null++;
    }

    free(map->keys);
    free(map->items);

    map->keys = new_key_arr;
    map->items = new_item_arr;
    map->capacity = new_len;
}

修改点：

• 遍历旧数组时使用map->capacity而非错误的map->size
• 重置size和non_null为0，复制元素时重新统计
• 删除错误的map->size = map->capacity;和map->non_null = map->size;

验证 #

修复后重新编译运行，使用leaks命令检测，内存泄漏问题将被解决。

内容的提问来源于stack exchange，提问作者Dylan Randall