So for my C assignment, I need to implement a dynamic memory allocator with a similar interface to the standard library like malloc, free, realloc. I'm implementing the allocator as a library of functions that can be called by other programs. Virtual heap will be managed by a simple buddy allocation algorithm.
My functions given are:
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.
This is my current problem: How do you initialise the heap and implement malloc without anything in the first place? Like I can't use malloc or any of the pre existing allocator functions. So far I've tried to use a linked list with nodes containing the memory as a value. Eg if initial size is 3 and min size is 1, I'd have 5 nodes with the root containing 8 bytes, two more containing 4 bytes each , and lastly 2 more contining 2 bytes each. But I'm still confused on how to use sbrk or how the heap is structured in the first place. I've browsed online resources but still confused on how to construct the heap memory.
Following is my code so far:
#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 null\n", comment);
}
else{
printf("%s: memory:%d address:%p nextInLine:%p\n",
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 empty\n");
}
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 NULL\n");
}
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 0\n");
}
if(initial_size < min_size){
printf("initial_size is smaller than min_size\n");
}
//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) {
}
It would be great if someone could help explain how I would go about doing this, as in the structure I need to follow, if that makes sense.