使用 mmap 实现简单的堆分配器

Question

我正在使用 mmap 为我自己的 C 代码库实现我自己的堆分配器。基本上，我通过从 mmap 中分配一些缓冲区来实现哈希，其大小为描述符大小 + 请求的大小。然后我将内存的描述符保存在缓冲区的开头，并返回指向缓冲区的指针+描述符大小。我还认为，如果我为描述符添加一些哈希值，这样我就可以在释放时验证缓冲区，这会更安全一些。

#include "core.h"
#include <sys/mman.h>

#define HEAP_MEMORY_MAGIC_NUMBER 0xDEADBEEF

typedef struct HeapMemoryDescriptor {
    size_t size;
    void *start;
    uint32_t hash;
} HeapMemoryDescriptor;

#define HEAP_MEMORY_DESCRIPTOR_SIZE (sizeof(HeapMemoryDescriptor))

void *heap_alloc(size_t n_bytes)
{
    HeapMemoryDescriptor *result = (HeapMemoryDescriptor *)mmap(
                NULL,
                HEAP_MEMORY_DESCRIPTOR_SIZE + n_bytes,
                PROT_READ | PROT_WRITE,
                MAP_ANONYMOUS | MAP_PRIVATE,
                -1, 0
            );
    result->size = n_bytes;
    result->start = (void*)(result + 1);
    result->hash = HEAP_MEMORY_MAGIC_NUMBER;
    result->hash = hash_crc32((uint8_t *)result, HEAP_MEMORY_DESCRIPTOR_SIZE);
    return result->start;
}

void heap_dealloc(void *ptr)
{
    HeapMemoryDescriptor *descriptor = (HeapMemoryDescriptor *)((size_t)ptr - HEAP_MEMORY_DESCRIPTOR_SIZE);
    uint32_t expected_hash = descriptor->hash;
    descriptor->hash = HEAP_MEMORY_MAGIC_NUMBER;
    uint32_t calculated_hash = hash_crc32((uint8_t *)descriptor, HEAP_MEMORY_DESCRIPTOR_SIZE);

    if(descriptor->start == ptr && calculated_hash == expected_hash) {
        munmap(descriptor, HEAP_MEMORY_DESCRIPTOR_SIZE + descriptor->size);
    }
}

// https://web.archive.org/web/20190108202303/http://www.hackersdelight.org/hdcodetxt/crc.c.txt
uint32_t hash_crc32(const uint8_t *bytes, size_t bytes_size)
{
    size_t i, j;
    uint32_t byte, crc, mask;
    i = 0;
    crc = 0xFFFFFFFF;
    for(i = 0; i < bytes_size; ++i) {
        byte = bytes[i];
        crc = crc ^ byte;
        for(j = 8; j > 0; j--) {
            mask = -(crc & 1);
            crc = (crc >> 1) ^ (0xEDB88320 & mask);
        }
    }
    return ~crc;
}

我是否可以认为这足够安全，也许与 stdlib 中的 malloc 一样安全？

Answer 1

一些想法...

1. 任何

   malloc

   函数都必须返回一个与最大 intrinsic 类型（即

   double

   ）对齐的指针。
2. 因此，[为了简单起见]堆描述符大小应该是

   sizeof(double)

   的倍数（即 8）。为了更好地测量，请对齐 16。
3. 您的描述符不是 8 字节对齐（由于

   hash

   ）

4. start

   是无关的。返回的指针将always是

   (descriptor + 1)

5. 堆描述符通常具有前向/后向链接，以便可以通过（例如）heap_check_all函数遍历活动描述符的

   列表

   。链接可以是

   size_t

   或

   HeapMemoryDescriptor *

6. 我使用的一个技巧是“幻数”可以是描述符地址的散列。您可以散列整个描述符，但是，我发现如果幻数失败，通常就足够了。
7. 可以对

   prev

   和

   next

   指针进行额外的交叉检查（例如下面的

   heapcheck

   和

   heap_check_all

   ）。

---

这是一个重构版本。我没有编译或测试它。但是，它应该给你一些想法：

#include "core.h"
#include <sys/mman.h>

#define HEAP_MEMORY_MAGIC_NUMBER 0xDEADBEEF

// must be multiple of 8 bytes to ensure pointer returned by heap_alloc is
// [at least] 8 byte aligned (16 byte preferred)
typedef struct HeapMemoryDescriptor HeapMemoryDescriptor;
struct HeapMemoryDescriptor {
    size_t hash;
    size_t size;
    HeapMemoryDescriptor *prev;
    HeapMemoryDescriptor *next;
} HeapMemoryDescriptor;

// global list of active/free descriptors
typedef struct HeapList HeapList;
struct HeapList {
    HeapMemoryDescriptor *head;
    HeapMemoryDescriptor *tail;
};

HeapList heaplist;

#define HEAP_MEMORY_DESCRIPTOR_SIZE (sizeof(HeapMemoryDescriptor))

static size_t
hashof(void *ptr)
{
    size_t hash = (size_t) ptr;

    hash = (~hash * 1103515245) + 12345;

    return addr;
}

static int
hashcheck(HeapMemoryDescriptor *cur)
{
    size_t expected_hash = cur->hash;
    size_t calculated_hash = hashof(cur);

    int bad = (calculated_hash != expected_hash);

    if (bad)
        heapfault("hashcheck: corrupted heap -- ptr=%p cur=%p expected_hash=%16.16zX calculated_hash=%16.16zX\n",
            ptr,cur,expected_hash,calculated_hash);

    return bad;
}

void
heapcheck(HeapMemoryDescriptor *cur,HeapMemoryDescriptor *prev)
{

    if (hashcheck(cur))
        exit(9);

    if (cur->prev != prev)
        heapfault("heapcheck: cur=%p prev=%p cur->prev=%p\n",
            cur,prev,cur->prev);

    if (cur->next != NULL)
        heapcheck(cur->next);
}

void *
heap_alloc(size_t n_bytes)
{
    HeapMemoryDescriptor *result = (HeapMemoryDescriptor *) mmap(NULL,
        HEAP_MEMORY_DESCRIPTOR_SIZE + n_bytes,
        PROT_READ | PROT_WRITE,
        MAP_ANONYMOUS | MAP_PRIVATE,
        -1, 0);

    result->size = n_bytes;
    result->hash = hashof(result);

    result->prev = NULL;
    result->next = heaplist.head;

    heaplist.head = result;
    if (heaplist.tail == NULL)
        heaplist.tail = result;

    return result + 1;
}

void
heap_dealloc(void *ptr)
{
    HeapMemoryDescriptor *cur = ptr;
    --cur;

    heapcheck(cur);

    HeapMemoryDescriptor *prev = cur->prev;
    HeapMemoryDescriptor *next = cur->next;

    if (prev != NULL)
        prev->next = next;
    if (next != NULL)
        next->prev = prev;

    if (heaplist.head == cur)
        heaplist.head = next;
    if (heaplist.tail == cur)
        heaplist.tail = prev;

    munmap(cur, HEAP_MEMORY_DESCRIPTOR_SIZE + cur->size);
}

void
heap_check_all(void)
{
    HeapMemoryDescriptor *cur = heaplist.head;
    HeapMemoryDescriptor *prev = NULL;
    HeapMemoryDescriptor *next;

    for (;  cur != NULL;  cur = next) {
        hashcheck(cur,prev);

        if (cur->prev != prev)
            heapfault("heapcheck: bad prev pointer -- cur=%p prev=%p cur->prev=%p\n",
                cur,prev,cur->prev);

        do {
            next = cur->next;
            if (next == NULL)
                break;

            hashcheck(next);

            if (next->prev != cur)
                heapfault("heapcheck: bad next/prev pointer -- next=%p next->prev=%p cur=%p\n",
                    next,next->prev,cur);
        } while (0);

        prev = cur;
    }
}