Create A Program To Write Replacement For Malloc And Free Function In C Language Assignment Solution

Instructions

Objective

Write a C assignment program to write replacement for malloc and free function.

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; } }