实施的malloc？ [英] malloc implementation?
问题描述
我想实施的malloc 和免费的C和我不知道如何再利用内存。我现在有一个结构，看起来像这样：
I'm trying to implement malloc and free for C, and I am not sure how to reuse memory. I currently have a struct that looks like this:
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 ，然后内存分配到该地址。我有点糊涂了如何实现这一点。
When I free memory, I would just mark the address as 0 (that would indicate that it is free). In my malloc, I would then use a for loop to look for any value in the array to equal 0 and then allocate memory to that address. I'm kind of confused how to implement this.
推荐答案
要做到这一点是保持空闲块的链接列表的最简单方法。在的malloc ，如果列表不为空，你搜索大到足以满足该请求并返回一个块。如果该列表是空的;如果没有这样的块，可以发现，你叫 SBRK 来从操作系统分配一些内存。在免费，只需将内存块添加到空闲块的列表。作为奖励，你可以尝试合并连续释放的块，你可以改变策略选择块返回（第配合，最适合，...）。也可以选择，如果它是比请求大分裂块
The easiest way to do it is to keep a linked list of free block. In malloc, if the list is not empty, you search for a block large enough to satisfy the request and return it. If the list is empty or if no such block can be found, you call sbrk to allocate some memory from the operating system. in free, you simply add the memory chunk to the list of free block. As bonus, you can try to merge contiguous freed block, and you can change the policy for choosing the block to return (first fit, best fit, ...). You can also choose to split the block if it is larger than the request.
一些示例实现（它没有经过测试，这显然不是线程安全的，需要您自担风险使用）：
Some sample implementation (it is not tested, and is obviously not thread-safe, use at your own risk):
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 是两个功率取决于数字的二进制重新presentation工作。
Note: (n + align_to - 1) & ~ (align_to - 1) is a trick to round n to the nearest multiple of align_to that is larger than n. This only works when align_to is a power of two and depends on the binary representation of numbers.
在 align_to 是二的幂，它只有一个位设置，从而 align_to - 1 有所有的最低位集（即 align_to 的形式为000 ... 010 ... 0和 align_to - 1 的形式为 000 ... 001 ... 1 ）。这意味着〜（align_to - 1）。有所有的高比特集，而低比特未设置（即它的形式是 111。 ..110 ... 0 ）。因此， X'放大器; 〜（align_to - 1）将设置为零 X 所有的低位和圆形下来到就近多个 align_to 。
When align_to is a power of two, it only has one bit set, and thus align_to - 1 has all the lowest bit sets (ie. align_to is of the form 000...010...0, and align_to - 1 is of the form 000...001...1). This means that ~ (align_to - 1) has all the high bit set, and the low bit unset (ie. it is of the form 111...110...0). So x & ~ (align_to - 1) will set to zero all the low bits of x and round it down to the nearest multiple of align_to.
最后，加入 align_to - 1 到尺寸确保我们搜捕到的最接近的倍数 align_to （除非尺寸已经是一个多 align_to 在这种情况下，我们想要得到尺寸）。
Finally, adding align_to - 1 to size ensure that we round-up to the nearest multiple of align_to (unless size is already a multiple of align_to in which case we want to get size).
这篇关于实施的malloc？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
