Instructions
Objective
Write a program to write replacement for malloc and free function in C language.
Requirements and Specifications
Screenshots of output
Source Code
// Note: Necessary header files are included
// Do not add extra header files
#define _GNU_SOURCE
#include
#include
#include
#include
// Data structure of meta_data
struct
__attribute__((__packed__)) // compiler directive, avoid "gcc" padding bytes to struct
meta_data {
size_t size; // 8 bytes (in 64-bit OS)
char free; // 1 byte ('f' or 'o')
struct meta_data *next; // 8 bytes (in 64-bit OS)
struct meta_data *prev; // 8 bytes (in 64-bit OS)
};
// calculate the meta data size and store as a constant (exactly 25 bytes)
const size_t meta_data_size = sizeof(struct meta_data);
// Global variables
void *start_heap = NULL; // pointing to the start of the heap, initialize in main()
struct meta_data dummy_head_node; // dummy head node of a doubly linked list, initialize in main()
struct meta_data *head = &dummy_head_node;
// The implementation of the following functions are given:
void list_add(struct meta_data *new, struct meta_data *prev, struct meta_data *next);
void list_add_tail(struct meta_data *new, struct meta_data *head);
void init_list(struct meta_data *list);
// Helper function: print the memory table
void mm_print();
// TODO: Students are required to implement these functions below
void *mm_malloc(size_t size);
void mm_free(void *p);
int main() {
start_heap = sbrk(0);
init_list(head);
// Assume there are at most 26 different malloc/free
// Here is the mapping rule
// a=>0, b=>1, ..., z=>25
void *pointers[26] = {NULL};
// Note: The input parsing part is already done
FILE *fp = stdin;
char command[10];
char block_name ; // a-z
unsigned int block_size; // a non-negative integer
while ( fscanf(fp, "%s", command) != EOF ) {
if ( strcmp(command, "malloc") == 0 ) {
fscanf(fp, " %c %u", &block_name, &block_size);
pointers[block_name-'a'] = mm_malloc(block_size);
printf("=== %s %c %d ===\n", command, block_name, block_size);
mm_print();
} else if ( strcmp(command, "free") == 0 ) {
fscanf(fp, " %c", &block_name);
mm_free(pointers[block_name-'a']);
printf("=== %s %c ===\n", command, block_name);
mm_print();
}
}
fclose(fp);
return 0;
}
void *mm_malloc(size_t size) {
// TODO: Complete mm_malloc here
struct meta_data *cur = head->next, *fblock = NULL;
char *new_ptr;
struct meta_data *new_node;
// search for free node with enough space
while ( cur != head && fblock == NULL) {
if (cur->free == 'f' && cur->size >= size)
fblock = cur;
cur = cur->next;
}
if (fblock != NULL) // if free node found
{
if (fblock->size >= size + meta_data_size) // if it can be split
{
new_ptr = (char *) fblock;
new_ptr += meta_data_size + size; // point to new block
new_node = (struct meta_data*) new_ptr;
new_node->free = 'f'; // set remaining as free
new_node->size = fblock->size - (size + meta_data_size); // set size as remainder
fblock->free = 'o'; // set initial node as allocated
fblock->size = size; // adjust node size
list_add(new_node, fblock, fblock->next); // insert new after allocated block
return (void *) (fblock + 1); // return pointer to allocated area
}
else // if can't be split
{
fblock->free = 'o'; // set whole block as occupies
return (void *) (fblock + 1); // return pointer to allocated area
}
}
else // no space in list for block
{
new_ptr = (char *) sbrk(size + meta_data_size); // allocate space for meta + alloc
if ((void *) new_ptr == (void *) -1) // if no more space
return NULL;
new_node = (struct meta_data*) new_ptr;
new_node->free = 'o'; // set as occupied
new_node->size = size; // set required size
list_add_tail(new_node, head); // add new node at end of list
return (void *) (new_node + 1); // return pointer to allocated area
}
}
void mm_free(void *p) {
// TODO: Complete mm_free here
struct meta_data *cur = head->next, *fblock = NULL;
struct meta_data *free_node;
free_node = (struct meta_data *) p;
free_node--; // point to start of node
// search for corresponding node
while ( cur != head && fblock == NULL) {
if (cur->free == 'o' && cur == free_node)
fblock = cur;
cur = cur->next;
}
if (fblock != NULL) // if we found the block to free
fblock->free = 'f'; // set as free
}
// Helper: initialize the linked list
void init_list(struct meta_data *list) {
list->next = list;
list->prev = list;
}
// Helper: add a list item
void list_add(struct meta_data *new,
struct meta_data *prev,
struct meta_data *next) {
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
// Helper: append a list item to the end
void list_add_tail(struct meta_data *new,
struct meta_data *head) {
list_add(new, head->prev, head);
}
// Helper: Tranverse and print the list of alloc/free blocks
void mm_print() {
struct meta_data *cur = head->next;
int i = 1;
while ( cur != head ) {
printf("Block %02d: [%s] size = %lu bytes\n",
i, // block number - counting from bottom
(cur->free=='f') ? "FREE" : "OCCP", // free or occupied
cur->size ); // size, in term of bytes
i = i+1;
cur = cur->next;
}
}