Edge cases for simulated malloc function

I'm trying to simulate the malloc function in C by using mmap and having 2 linked lists to act as memory blocks. The program works by reserving a region of memory and then keeps track of the free and allocated memory address with size in the linked lists. I have tested the program with normal cases like

• free memory > needed to be allocate

• free memory

• free memory == needed to be allocate

… but couldn't think of special cases. Are there cases where the program fails?

```
#include
#include
#include
#include
#include

struct block {
void addr; /start address of memory for this block */
int size;
struct block *next;
};

void *mem;
struct block *freelist;
struct block *allocated_list;

void *smalloc(unsigned int nbytes) {
struct block *cur = freelist;

while(cur!=NULL){

if (cur ->size >= nbytes){
struct block *tempBlock;
tempBlock= malloc(sizeof(struct block));
tempBlock->addr = cur ->addr;
tempBlock->size = nbytes;
tempBlock->next = NULL;

cur->addr = cur->addr + nbytes;
cur ->size = cur ->size - nbytes;

if(allocated_list == NULL){
allocated_list = tempBlock;
}
else{
cur = allocated_list;
while(cur->next!=NULL){
cur =cur->next;
}
cur->next=tempBlock;
}

return (tempBlock->addr);

}
cur = cur->next;

}

return NULL;
}

int sfree(void *addr) {
struct block *cur = allocated_list;
struct block *tempBlock;
while(cur!=NULL){
if (cur ->next->addr == addr){
tempBlock=cur->next; //disjoint the matched block from the allocated_list
cur->next = cur->next->next;
tempBlock->next = NULL; // set the matched block pointing to null

cur = freelist;
while(cur->next!=NULL){

-
Not sure if it's just a result from copy-and-pasting the code here but the code formatting needs improvement.

• Inconsistent indentation

• Inconsistent use of spaces

• Random empty lines

Clearly formatted code is a lot easier to read, maintain and is less prone to contain bugs.

-
Naming is inconsistent as well, e.g. allocated_list vs freelist vs tempBlock.

-
There is no need to place braces around the return value like this: return(0);. It should simply be return 0;. return is not a function call.

-
In order to append blocks to the end of each of the lists you currently iterate to find the end. It would pay off to keep a tail pointer pointing to the last element of each of the lists which avoids that.

-
I think there is a bug when calling sfree on the last block allocated. Example:

• First call to smalloc allocates a new struct block and assigns it to allocated_list

• This means allocated_list->next == NULL.

• Call to sfree

• cur points to allocated_list

• cur != NULL

• But cur->next->addr is invalid because cur->next == NULL

-
I think the cleaning up is technically broken. When initializing the structure you perform a single call to mmap to obtain a set of mapped memory pages. However on clean up you munmap every single block allocated by the user of smalloc. As per munmap man page:


The implementation will require that addr be a multiple of the page size {PAGESIZE}.

This can't be guaranteed because the passed in addr is not aligned at all as it is purely dependent on what was allocated by the user.

However I suspect it "simply works" because the first call to munmap unmaps the entire space mapped in originally with mmap because that's what the first addr of freelist is. Nevertheless the implementation is incorrect and works by pure coincidence.

-
You should check the return values of malloc and munmap as well.

-
Multiple calls to mem_init will leak memory. While it would certainly count as user error detecting this and notifying the user is good defensive programming.

StackExchange Code Review Q#82666, answer score: 6