I'm really curious to know someone else's opinion on this implementation. Specifically, I would be interested to know the way you would have implemented it. Here the list of issues I've found with in this primitive implementation:
- It's slow. You have to traverse the entire list in order to find a free block of memory.
- Overuse of
sbrk()
. - Very high possibility of internal fragmentation.
mem.h
#ifndef __MEM__
#define __MEM__
#include<stdio.h>
#include<stdlib.h>
typedef enum { false, true } bool;
typedef struct page
{
size_t size;
bool free;
struct page* next;
struct page* prev;
} page_t;
extern void* memalloc(size_t size);
extern void memfree(void* pointer);
#endif
mem.c
#include "include/mem.h"
#include <assert.h>
#include <sys/types.h>
#include <unistd.h>
#define SBRK_ERROR (void*)(-1)
#define UNDEFINED 0
page_t* global;
page_t* last;
page_t* allocate(size_t size)
{
page_t* node = sbrk(0);
void* pointer = sbrk(size + sizeof(page_t));
if(pointer == SBRK_ERROR)
return NULL;
if(last != NULL)
last-> next = node;
last = node;
last-> size = size;
last-> free = false;
last-> next = NULL;
return last;
}
void* search(size_t size)
{
page_t* node = global;
while(node != NULL){
if(node-> size >= size || node-> size == UNDEFINED){
if(node-> free)
return node;
}
node = node-> next;
}
return NULL;
}
void* memalloc(size_t size)
{
page_t* result = NULL;
if(size >= 0){
if(global != NULL){
result = search(size);
if(result == NULL)
result = allocate(size);
}else {
global = allocate(size);
result = global;
}
}
return result != NULL ? (result + 1) : NULL;
}
page_t* to_page(void* pointer){
return pointer - sizeof(page_t);
}
void memfree(void* pointer)
{
if(pointer != NULL) {
page_t* page = to_page(pointer);
page-> size = UNDEFINED;
page-> free = true;
}
}
int main(int argc, char** argv)
{
char* pointer = memalloc(5);
memfree(pointer);
return 1;
}
What are the most common techniques (implementations) to solve the issues above? Just rough ideas of it.
->
is unusual and makes it look like the>
operator at first glance, specially in theif
. I'd recommend against it. \$\endgroup\$