#include

#include

#include

#include

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;

}

}

struct block_meta {

size_t size;

struct block_meta *next;

int free;

int magic;

};

#define META_SIZE sizeof(struct block_meta)

void *global_base = NULL;

// Iterate through blocks until we find one that's large enough.

// TODO: split block up if it's larger than necessary

struct block_meta *find_free_block(struct block_meta **last, size_t size) {

struct block_meta *current = global_base;

while (current && !(current->free && current->size >= size)) {

*last = current;

current = current->next;

}

return current;

}

struct block_meta *request_space(struct block_meta* last, size_t size) {

struct block_meta *block;

block = 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->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) {

struct block_meta *block;

// TODO: align size?

if (size <= 0) {

return NULL;

}

if (!global_base) { // First call.

block = request_space(NULL, size);

if (!block) {

return NULL;

}

global_base = block;

} else {

struct block_meta *last = 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

// TODO: consider splitting block here.

block->free = 0;

block->magic = 0x77777777;

}

}

return(block+1);

}

void *calloc(size_t nelem, size_t elsize) {

size_t size = nelem * elsize;

void *ptr = malloc(size);

memset(ptr, 0, size);

return ptr;

}

// TODO: maybe do some validation here.

struct block_meta *get_block_ptr(void *ptr) {

return (struct block_meta*)ptr - 1;

}

void free(void *ptr) {

if (!ptr) {

return;

}

// TODO: consider merging blocks once splitting blocks is implemented.

struct block_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;

}

void *realloc(void *ptr, size_t size) {

if (!ptr) {

// NULL ptr. realloc should act like malloc.

return malloc(size);

}

struct block_meta* block_ptr = get_block_ptr(ptr);

if (block_ptr->size >= size) {

// We have enough space. Could free some once we implement split.

return ptr;

}

// 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) {

return NULL; // TODO: set errno on failure.

}

memcpy(new_ptr, ptr, block_ptr->size);

free(ptr);

return new_ptr;

}

Use This Code

To Write 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.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 code. These are also shown below: (a) Convert the single linked list implementation of the code 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. Does our malloc do that? If so, why? If not, fix the alignment. Note that any built-in type is basically up to 8 bytes for C. (c) The implemented malloc is really wasteful if we try to re-use an existing block and we dont 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, well 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.