因此，对于我的C赋值，我需要实现一个动态内存分配器，该分配器具有与标准库类似的接口，如malloc、free、realloc。我将分配器实现为其他程序可以调用的函数库。虚拟堆将通过一个简单的伙伴分配算法进行管理。
我给出的函数是：
void * virtual_sbrk(int32_t increment);
pretty much the same as the real-world sbrk and brk syscalls. I don't need to implement this.
void init_allocator(void * heapstart, uint8_t initial_size, uint8_t min_size);
This function will be called once at the beginning and initialise the virtual heap.
void * virtual_malloc(void * heapstart, uint32_t size);
mallocs memory
int virtual_free(void * heapstart, void * ptr);
frees memory
void * virtual_realloc(void * heapstart, void * ptr, uint32_t size);
reallocates memory
void virtual_info(void * heapstart);
prints the current state of the buddy allocator to standard output.
这是我目前的问题：如何初始化堆并在没有任何东西的情况下实现malloc？就像我不能使用malloc或任何预先存在的分配器函数一样。到目前为止，我已经尝试使用一个链表，其中包含作为值的内存的节点。例如，如果初始大小为3，最小大小为1，那么我将有5个节点，根节点包含8个字节，另外两个节点各包含4个字节，最后两个节点分别包含2个字节。但我仍然对如何使用sbrk或堆的结构感到困惑。我浏览了在线资源，但仍然对如何构建堆内存感到困惑。
以下是我到目前为止的代码：
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
struct node{
size_t memory;
struct node *nextInLine;
};
void printNode(const struct node *nd, const char *comment){
if(nd == NULL){
printf("%s is nulln", comment);
}
else{
printf("%s: memory:%d address:%p nextInLine:%pn",
comment,
nd->memory,
nd,
nd->nextInLine);
}
}
void printList(const struct node *list){
printf("Printing List:n");
const struct node *t;
t = list;
if(t == NULL){
printf("current node is emptyn");
}
else{
while(t){
printNode(t, "node");
t = t->nextInLine;
}
}
}
void * virtual_sbrk(int32_t increment) {
void *p = malloc(increment);
return p;
}
uint8_t return_init_size(uint8_t size){
return size;
}
struct node *getNewNode(const uint8_t memory_size){
struct node *newNode = NULL;
double two = 2;
size_t m_size = memory_size;
double result = pow(two, m_size);
newNode = virtual_sbrk(result);
if(newNode != NULL){
newNode->memory = result;
newNode->nextInLine = NULL;
}
else{
printf("Allocation error: newNode is still NULLn");
}
return newNode;
}
void init_allocator(void * heapstart, uint8_t initial_size, uint8_t min_size) {
//error catchers
if(initial_size == 0){
printf("Initial size is 0n");
}
if(initial_size < min_size){
printf("initial_size is smaller than min_sizen");
}
//initialising the virtual heap using a linked array with nodes the memory size of 2^some_size
uint8_t i = initial_size;
struct node *first = heapstart;
heapstart = first;
struct node *tail = NULL;
while(i >= min_size){
if(first == NULL){
first = getNewNode(i);
if(first != NULL){
tail = first;
}
}
else{
tail->nextInLine = getNewNode(i);
if(tail->nextInLine != NULL){
tail = tail->nextInLine;
}
tail->nextInLine = getNewNode(i);
if(tail->nextInLine != NULL){
tail = tail->nextInLine;
}
}
i -= 1;
}
printList(first);
}
void * virtual_malloc(void * heapstart, uint32_t size) {
if(size == 0){
return NULL;
}
return NULL;
}
int virtual_free(void * heapstart, void * ptr) {
return 1;
}
void * virtual_realloc(void * heapstart, void * ptr, uint32_t size) {
return NULL;
}
void virtual_info(void * heapstart) {
}
如果有人能帮助解释我将如何做这件事，就像我需要遵循的结构一样，如果这有意义的话，那就太好了。
您可以像glibcmalloc那样同时使用sbrk和mmap。
glibcmalloc使用线程，使用一种叫做arenas的东西。
当malloc被初始化时，它调用sbrk来扩展映射的内存。
当发生大的分配或创建新线程时，malloc最终会调用mmap。
CCD_ 5在进程的地址空间中分配新的映射。sbrk扩展当前映射以使其更大。
sbrk:的简单示例
#define _GNU_SOURCE
#include <stdio.h>
#include <unistd.h>
#define HEAP_SZ 0x8000
int main(void) {
void *p = sbrk(0);
printf("current break addr = %pn", p);
sbrk(HEAP_SZ);
void *n = sbrk(0);
printf("new break addr = %pn", n);
return 0;
}
第一个调用(参数为0(返回当前程序中断。当指定的大小大于0时，程序中断将被扩展，因此在下一次使用参数0的调用中，将返回新的程序中断。
你可以这样做：
unsigned long heap_mem_sz = 0;
void *heap_start_addr = NULL;
void init_heap(void) {
void *p = sbrk(0);
#if DEBUG
printf("current break addr = %pn", p);
#endif
sbrk(HEAP_SZ);
heap_mem_sz = (unsigned long)HEAP_SZ;
void *n = sbrk(0);
#if DEBUG
printf("new break addr = %pn", n);
#endif
heap_start_addr = (void *)n;
return;
}
有了这些关于全局变量的信息，就可以继续开发分配器实现。
您可以在第一次请求分配时调用init_heap()。
现在，您可以返回该分配并创建一个"；顶部块"；。
它将是一个结构与其他块相同的块，但包含分配占用内存的所有内存，并且在分配时会收缩。
此外，一旦堆内存已满，您将需要执行一些操作，因此可以考虑再次调用类似mmap或sbrk的系统调用。
malloc上的链表用于bin。它们用于搜索可以满足新分配的释放块，以便重用不再使用的块。
对于这样的链接列表，您可以创建一个全局：
struct heap_chunk *freed_chain = NULL
当请求内存时，首先检查freed_chain是否为NULL，如果不是，则遍历链表，直到找到与用户请求兼容的块，或者下一个指针为NULL。
如果这些区块中的任何一个是有效的，您将需要从链表中取消该区块的链接，并使上一个区块指向下一个区块，这样就不会有更多的内存请求访问它，因为现在它已经分配而没有释放。
在释放内存时，您需要将一个新的区块链接到该链表。
显然，在malloc上，出于优化目的，这更为复杂，并且存在一些具有不同大小要求和不同属性的不同容器，以加快分配。