malloc实现？
我正在尝试为C实现malloc和free ，我不知道如何重用内存。 我目前有一个如下所示的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; }