malloc实现?

我正在尝试为C实现mallocfree ,我不知道如何重用内存。 我目前有一个如下所示的struct

 typedef struct _mem_dictionary { void *addr; size_t size; int freed; } mem_dictionary; 

我的malloc看起来像这样:

 void *malloc(size_t size) { void *return_ptr = sbrk(size); if (dictionary == NULL) dictionary = sbrk(1024 * sizeof(mem_dictionary)); dictionary[dictionary_ct].addr = return_ptr; dictionary[dictionary_ct].size = size; dictionary[dictionary_ct].freed = 1; dictionary_ct++; return return_ptr; } 

当我释放内存时,我只会将地址标记为0 (这表示它是免费的)。 在我的malloc ,我会使用for循环来查找数组中的任何值等于0 ,然后将内存分配给该地址。 我有点困惑如何实现这一点。

最简单的方法是保留一个空闲块的链表。 在malloc ,如果列表不为空,则搜索足够大的块以满足请求并返回它。 如果列表为空或者找不到这样的块,则调用sbrk从操作系统分配一些内存。 在free ,您只需将内存块添加到空闲块列表中。 作为奖励,您可以尝试合并连续释放的块,并且您可以更改选择要返回的块的策略(首先适合,最适合,…)。 如果块大于请求,您也可以选择拆分块。

一些示例实现(未经过测试,显然不是线程安全的,使用风险自负):

 typedef struct free_block { size_t size; struct free_block* next; } free_block; static free_block free_block_list_head = { 0, 0 }; static const size_t overhead = sizeof(size_t); static const size_t align_to = 16; void* malloc(size_t size) { size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1); free_block* block = free_block_list_head.next; free_block** head = &(free_block_list_head.next); while (block != 0) { if (block->size >= size) { *head = block->next; return ((char*)block) + sizeof(size_t); } head = &(block->next); block = block->next; } block = (free_block*)sbrk(size); block->size = size; return ((char*)block) + sizeof(size_t); } void free(void* ptr) { free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t)); block->next = free_block_list_head.next; free_block_list_head.next = block; } 

注意: (n + align_to - 1) & ~ (align_to - 1)是将n舍入到最大的align_to倍数的align_to ,该倍数大于n 。 这只适用于align_to是2的幂并且取决于数字的二进制表示。

align_to是2的幂时,它只有一个比特集,因此align_to - 1具有所有最低比特集(即align_to的forms为000 … 010 … 0,并且align_to - 1是表格000...001...1 )。 这意味着~ (align_to - 1)具有所有高位设置,而低位未设置(即,其forms为111...110...0 )。 因此x & ~ (align_to - 1)x所有低位设置为零,并将其向下舍入到最接近的align_to

最后,将align_to - 1添加到size确保我们向上舍入到最接近的align_to (除非size已经是align_to的倍数,在这种情况下我们想要获得size )。

您不希望将字典条目的size字段设置为零 – 您将需要该信息以供重用。 相反,仅在释放块时才设置freed=1

你不能合并相邻的块,因为可能有对sbrk()干预调用,这样可以更容易。 你只需要一个for循环来搜索一个足够大的释放块:

 typedef struct _mem_dictionary { void *addr; size_t size; int freed; } mem_dictionary; void *malloc(size_t size) { void *return_ptr = NULL; int i; if (dictionary == NULL) { dictionary = sbrk(1024 * sizeof(mem_dictionary)); memset(dictionary, 0, 1024 * sizeof(mem_dictionary)); } for (i = 0; i < dictionary_ct; i++) if (dictionary[i].size >= size && dictionary[i].freed) { dictionary[i].freed = 0; return dictionary[i].addr; } return_ptr = sbrk(size); dictionary[dictionary_ct].addr = return_ptr; dictionary[dictionary_ct].size = size; dictionary[dictionary_ct].freed = 0; dictionary_ct++; return return_ptr; } void free(void *ptr) { int i; if (!dictionary) return; for (i = 0; i < dictionary_ct; i++ ) { if (dictionary[i].addr == ptr) { dictionary[i].freed = 1; return; } } } 

这不是一个很棒的malloc()实现。 实际上,大多数malloc / free实现都会为malloc返回的每个块分配一个小头。 例如,标题可能从比返回指针八(8)个字节的地址开始。 在这些字节中,您可以存储指向拥有该块的mem_dictionary条目的指针。 这样可以free避免O(N)操作。 您可以通过实现释放块的优先级队列来避免malloc()的O(N)。 考虑使用二进制 ,块大小作为索引。

我从Sylvain的回复中借用代码。 他似乎错过了计算free_block * ini计算开销的大小。

总体而言,代码通过将此free_block作为标头添加到分配的内存来工作。 1.当用户调用malloc时,malloc会在此标头之后返回有效负载的地址。 2.当调用free时,计算块头的起始地址(通过从块地址中减去头大小)并将其添加到空闲块池中。

 typedef struct free_block { size_t size; struct free_block* next; } free_block; static free_block free_block_list_head = { 0, 0 }; // static const size_t overhead = sizeof(size_t); static const size_t align_to = 16; void* malloc(size_t size) { size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1); free_block* block = free_block_list_head.next; free_block** head = &(free_block_list_head.next); while (block != 0) { if (block->size >= size) { *head = block->next; return ((char*)block) + sizeof(free_block); } head = &(block->next); block = block->next; } block = (free_block*)sbrk(size); block->size = size; return ((char*)block) + sizeof(free_block); } void free(void* ptr) { free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block )); block->next = free_block_list_head.next; free_block_list_head.next = block; }