Malloc Implementation
In this assignment, you will develop a C program to implement the “malloc”, “free”, “calloc” and “realloc” functionalities.
Instructions:
Check out the malloc tutorial from Dan Luu on how these functions can be implemented.
Write a driver function (i.e., main function) to demonstrate the usage and efficiency of these functions. The main() should have at least 10 calls each to malloc, calloc and realloc and at least 5 calls to free. Set up the function to print out the heap start/end addresses and also print out the memory leaks in your code.
3. Your main task is to implement the exercises mentioned in the tutorial. These are also shown below:
(a) Convert the single linked list implementation of the tutorial into a doubly linked list
version; make changes to all the functions accordingly to work with the doubly linked list.
(b) malloc is supposed to return a pointer “which is suitably aligned for any built-in type”.
(c) The implemented malloc is really wasteful if we try to re-use an existing block and we
don’t need all of the space. Implement a function that will split up blocks so that they use the
minimum amount of space necessary.
(d) After doing (c), if we call malloc and free lots of times with random sizes, we’ll end up
with a bunch of small blocks that can only be re-used when we ask for small amounts of
space. Implement a mechanism to merge adjacent free blocks together so that any consecutive
free blocks will get merged into a single block.
(e) The current implementation implements a first fit algorithm for finding free blocks. Implement a best fit algorithm instead.
4. Repeat Step (2) with this implementation to demonstrate usage of the functions and memory leakage.
5. Your code must use the set-up mentioned in this tutorial.
To turn in:
1. You will need 4 files: (a) a header file with all the function prototypes, (b) a .c file with all the function definitions, (c) a .c file with the driver main() function and (d) a Makefile to compile your code.
2. Create a tarball file with all these files.
Solution
driver.c
#include “malloc.h”
int main()
{
void *m1 = malloc(10);
void *m2 = malloc(20);
void *m3 = malloc(30);
void *m4 = malloc(40);
void *m5 = malloc(50);
void *m6 = malloc(60);
void *m7 = malloc(70);
void *m8 = malloc(80);
void *m9 = malloc(90);
void *m10 = malloc(100);
free(m1);
free(m2);
free(m3);
free(m4);
free(m5);
free(m6);
free(m7);
free(m8);
free(m9);
free(m10);
void *n1 = malloc(100);
void *n2 = malloc(200);
void *n3 = malloc(300);
void *n4 = malloc(400);
void *n5 = malloc(500);
void *n6 = malloc(600);
void *n7 = malloc(700);
void *n8 = malloc(800);
void *n9 = malloc(900);
void *n10 = malloc(1000);
void *r1 = realloc(NULL, 10);
void *r2 = realloc(n2, 200);
void *r3 = realloc(n3, 200);
void *r4 = realloc(n4, 200);
void *r5 = realloc(n5, 200);
void *r6 = realloc(n6, 200);
void *r7 = realloc(n7, 200);
void *r8 = realloc(n8, 200);
void *r9 = realloc(n9, 200);
void *r10 = realloc(n10, 200);
print_leaks();
return 0;
}
Malloc.c
#include
#include
#include
#include
#include
#include “malloc.h”
// Don’t include stdlb since the names will conflict?
// TODO: align
// sbrk some extra space every time we need it.
// This does no bookkeeping and therefore has no ability to free, realloc, etc.
void *nofree_malloc(size_t size) {
void *p = sbrk(0);
void *request = sbrk(size);
if (request == (void*) -1) {
return NULL; // sbrk failed
} else {
assert(p == request); // Not thread safe.
return p;
}
}
structblock_meta {
size_t size;
structblock_meta *next;
structblock_meta *prev; // to use doubly linked list
int free;
int magic; // For debugging only. TODO: remove this in non-debug mode.
};
#define META_SIZE sizeof(structblock_meta)
void *global_base = NULL;
// function to print memory leaks
voidprint_leaks()
{
structblock_meta *current = (structblock_meta *)global_base;
if(current == NULL)
printf(“no linked list\n”);
while(current)
{
if(current->free == 0)
{
printf(“Lost %d bytes starting from address %p \n”,current->size,current);
}
current = current->next;
}
}
// function to split block
voidsplit_block(structblock_meta **current, size_t size)
{
size_tprev_sz = (*current)->size;
(*current)->size = (*current)->size – size;
void *addr = (*current) + sizeof(structblock_meta) + (*current)->size;
structblock_meta *block = (structblock_meta *)addr;
block->size = prev_sz – (*current)->size – sizeof(structblock_meta);
block->free = 1;
block->prev = *current;
block->next = (*current)->next = block;
(*current)->next = block;
}
// function to merge to neighbor blocks
voidmerge_neigbor(structblock_meta **current)
{
size_t sz1 = (*current)->size;
size_t sz2 = (*current)->next->size;
(*current)->size = sz1 + sz2 + sizeof(structblock_meta);
(*current)->next = (*current)->next->next;
}
// function to merge free blocks
int merge(structblock_meta *current)
{
structblock_meta *next = current->next;
if(next != NULL)
{
if(current->free && next->free)
{
merge_neigbor(¤t);
return 1;
}
else
return 0;
}
return 0;
}
// Iterate through blocks until we find one that’s large enough.
// TODO: split block up if it’s larger than necessary
structblock_meta *find_free_block(structblock_meta **last, size_t size) {
structblock_meta *current = (structblock_meta *)global_base;
size_tbest_size = 100000;
// use best fit algorithm
structblock_meta *best_block = NULL;
//while (current && !(current->free && current->size >= size)) {
while (current) {
if(current->size >= size && current->size
{
best_block = current;
best_size = current->size;
}
current = current->next;
}
returnbest_block;
}
structblock_meta *request_space(structblock_meta* last, size_t size) {
structblock_meta *block;
block = (structblock_meta *)sbrk(0);
void *request = sbrk(size + META_SIZE);
assert((void*)block == request); // Not thread safe.
if (request == (void*) -1) {
return NULL; // sbrk failed.
}
if (last) { // NULL on first request.
last->next = block;
}
block->size = size;
block->prev = last;
block->next = NULL;
block->free = 0;
block->magic = 0x12345678;
return block;
}
// If it’s the first ever call, i.e., global_base == NULL, request_space and set global_base.
// Otherwise, if we can find a free block, use it.
// If not, request_space.
void *malloc(size_t size) {
structblock_meta *block;
// DONE: align size?
// align size to 8 byte boundary
if (size <= 0) {
return NULL;
}
if(size % 8 != 0)
{
size_t rem = size%8;
size += (8 – rem);
}
if (!global_base) { // First call.
block = request_space(NULL, size);
if (!block) {
return NULL;
}
global_base = block;
} else {
structblock_meta *last = (structblock_meta *)global_base;
block = find_free_block(&last, size);
if (!block) { // Failed to find free block.
block = request_space(last, size);
if (!block) {
return NULL;
}
} else { // Found free block
// DONE: consider splitting block here.
block->free = 0;
if(block->size > size + sizeof(structblock_meta))
split_block(&block, size);
block->magic = 0x77777777;
}
}
return(block+1);
}
void *calloc(size_tnelem, size_telsize) {
size_t size = nelem * elsize;
void *ptr = malloc(size);
memset(ptr, 0, size);
returnptr;
}
// DONE: maybe do some validation here.
structblock_meta *get_block_ptr(void *ptr) {
if(ptr == NULL) return NULL;
return (structblock_meta*)ptr – 1;
}
void free(void *ptr) {
if (!ptr) {
return;
}
// DONE: consider merging blocks once splitting blocks is implemented.
structblock_meta* block_ptr = get_block_ptr(ptr);
assert(block_ptr->free == 0);
assert(block_ptr->magic == 0x77777777 || block_ptr->magic == 0x12345678);
block_ptr->free = 1;
block_ptr->magic = 0x55555555;
merge(block_ptr);
}
void *realloc(void *ptr, size_t size) {
if (!ptr) {
// NULL ptr. realloc should act like malloc.
returnmalloc(size);
}
structblock_meta* block_ptr = get_block_ptr(ptr);
if (block_ptr->size >= size) {
// We have enough space. Could free some once we implement split.
returnptr;
}
// Need to really realloc. Malloc new space and free old space.
// Then copy old data to new space.
void *new_ptr;
new_ptr = malloc(size);
if (!new_ptr) {
errno = ENOMEM;
return NULL; // DONE: set errno on failure.
}
memcpy(new_ptr, ptr, block_ptr->size);
free(ptr);
returnnew_ptr;
}
Malloc.h
#include
void *nofree_malloc(size_t size);
void *malloc(size_t size);
void *calloc(size_tnelem, size_telsize);
void free(void *ptr);
void *realloc(void *ptr, size_t size);
voidprint_leaks();