Please complete the code in C

Complete only the sections marked TODO, instructions are in the header comments.

You're given a test to check. This program mem mimics the free() and malloc() operations in C.

mem.h (completed, do not change)

#ifndef __mem_h__ #define __mem_h__

int Mem_Init(int sizeOfRegion); void* Mem_Alloc(int size); int Mem_Free(void *ptr); int coalesce(); void Mem_Dump(); void* malloc(size_t size) { return NULL; }

#endif // __mem_h__

mem.c (complete the TODO sections to implement a C memory allocator)

#include #include #include #include #include #include #include #include "mem.h"

/* * This structure serves as the header for each allocated and free block * It also serves as the footer for each free block * The blocks are ordered in the increasing order of addresses */ typedef struct block_tag {

int size_status;

/* * Size of the block is always a multiple of 8. * Size is stored in all block headers and in free block footers. * * Status is stored only in headers using the two least significant bits. * Bit0 => least significant bit, last bit * Bit0 == 0 => free block * Bit0 == 1 => allocated block * * Bit1 => second last bit * Bit1 == 0 => previous block is free * Bit1 == 1 => previous block is allocated * * End Mark: * The end of the available memory is indicated using a size_status of 1. * * Examples: * * 1. Allocated block of size 24 bytes: * Allocated Block Header: * If the previous block is free p-bit=0 size_status would be 25 * If the previous block is allocated p-bit=1 size_status would be 27 * * 2. Free block of size 24 bytes: * Free Block Header: * If the previous block is free p-bit=0 size_status would be 24 * If the previous block is allocated p-bit=1 size_status would be 26 * Free Block Footer: * size_status should be 24 */ } block_tag;

/* Global variable - DO NOT CHANGE. It should always point to the first block, * i.e., the block at the lowest address. */ block_tag *first_block = NULL;

/* Size of heap allocation padded to round to nearest page size. */ int allocsize;

/* * Function for allocating 'size' bytes of heap memory. * Argument size: requested size for the payload * Returns address of allocated block (payload) on success. * Returns NULL on failure. * * This function must: * - Check size - Return NULL if not positive or if larger than heap space. * - Determine block size rounding up to a multiple of 8 * and possibly adding padding as a result. * * - Use BEST-FIT PLACEMENT POLICY to chose a free block * * - If the BEST-FIT block that is found is exact size match * - 1. Update all heap blocks as needed for any affected blocks * - 2. Return the address of the allocated block payload * * - If the BEST-FIT block that is found is large enough to split * - 1. SPLIT the free block into two valid heap blocks: * 1. an allocated block * 2. a free block * NOTE: both blocks must meet heap block requirements * - Update all heap block header(s) and footer(s) * as needed for any affected blocks. * - 2. Return the address of the allocated block payload * * - If a BEST-FIT block found is NOT found, return NULL * Return NULL unable to find and allocate block for desired size * * Note: payload address that is returned is NOT the address of the * block header. It is the address of the start of the * available memory for the requesterr. * * Tips: Be careful with pointer arithmetic and scale factors. */ void* Mem_Alloc(int size) { //TODO }

/* * Function for freeing up a previously allocated block * Argument - ptr: Address of the payload of the allocated block to be freed up * Returns 0 on success * Returns -1 on failure * Here is what this function should accomplish * - Return -1 if ptr is NULL. * - Return -1 if ptr is not a multiple of 8. * - Return -1 if ptr is outside of the heap space. * - Return -1 if ptr block is already freed. * - Update header(s) and footer as needed. */ int Mem_Free(void *ptr) { //TODO }

/* * Function for traversing heap block list and coalescing all adjacent * free blocks. * * This function is used for delayed coalescing. * Updated header size_status and footer size_status as needed. */ int coalesce() { //TODO }

/* * Function used to initialize the memory allocator * Not intended to be called more than once by a program * Argument - sizeOfRegion: Specifies the size of the chunk which needs to be allocated * Returns 0 on success and -1 on failure */ int Mem_Init(int sizeOfRegion) { int pagesize; int padsize; int fd; int alloc_size; void *space_ptr; static int allocated_once = 0;

if (0 != allocated_once) { fprintf(stderr, "Error:mem.c: Mem_Init has allocated space during a previous call "); return -1; } if (sizeOfRegion <= 0) { fprintf(stderr, "Error:mem.c: Requested block size is not positive "); return -1; }

// Get the pagesize pagesize = getpagesize();

// Calculate padsize as the padding required to round up sizeOfRegion to a multiple of pagesize padsize = sizeOfRegion % pagesize; padsize = (pagesize - padsize) % pagesize;

alloc_size = sizeOfRegion + padsize;

// Using mmap to allocate memory fd = open("/dev/zero", O_RDWR); if (-1 == fd) { fprintf(stderr, "Error:mem.c: Cannot open /dev/zero "); return -1; } space_ptr = mmap(NULL, alloc_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0); if (MAP_FAILED == space_ptr) { fprintf(stderr, "Error:mem.c: mmap cannot allocate space "); allocated_once = 0; return -1; }

allocated_once = 1;

// Intialising total available memory size allocsize = alloc_size;

// To begin with there is only one big free block first_block = (block_tag*) space_ptr;

// Setting up the header first_block->size_status = alloc_size; // Marking the previous block as busy first_block->size_status += 2;

// Setting up the footer block_tag *footer = (block_tag*) ((char*) first_block + alloc_size - 4); footer->size_status = alloc_size;

return 0; }

/* * Function to be used for debugging * Prints out a list of all the blocks along with the following information for each block * No. : serial number of the block * Status : free/busy * Prev : status of previous block free/busy * t_Begin : address of the first byte in the block (this is where the header starts) * t_End : address of the last byte in the block * t_Size : size of the block (as stored in the block header)(including the header/footer) */ void Mem_Dump() { int counter; char status[5]; char p_status[5]; char *t_begin = NULL; char *t_end = NULL; int t_size;

block_tag *current = first_block; counter = 1;

int busy_size = 0; int free_size = 0; int is_busy = -1;

fprintf(stdout, "************************************Block list*********************************** "); fprintf(stdout, "No.\tStatus\tPrev\tt_Begin\t\tt_End\t\tt_Size "); fprintf(stdout, "--------------------------------------------------------------------------------- ");

while (current < (block_tag*) ((char*) first_block + allocsize)) {

t_begin = (char*) current;

t_size = current->size_status;

if (t_size & 1) { // LSB = 1 => busy block strcpy(status, "Busy"); is_busy = 1; t_size = t_size - 1; } else { strcpy(status, "Free"); is_busy = 0; }

if (t_size & 2) { strcpy(p_status, "Busy"); t_size = t_size - 2; } else strcpy(p_status, "Free");

if (is_busy) busy_size += t_size; else free_size += t_size;

t_end = t_begin + t_size - 1;

fprintf(stdout, "%d\t%s\t%s\t0x%08lx\t0x%08lx\t%d ", counter, status, p_status, (unsigned long int) t_begin, (unsigned long int) t_end, t_size);

current = (block_tag*) ((char*) current + t_size); counter = counter + 1; } fprintf(stdout, "--------------------------------------------------------------------------------- "); fprintf(stdout, "********************************************************************************* ");

fprintf(stdout, "Total busy size = %d ", busy_size); fprintf(stdout, "Total free size = %d ", free_size); fprintf(stdout, "Total size = %d ", busy_size + free_size); fprintf(stdout, "********************************************************************************* "); fflush(stdout); return; }

test.c

#include #include #include "mem.h"

int main() { assert(Mem_Init(4096) == 0); void *ptr[4];

ptr[0] = Mem_Alloc(800); assert(ptr[0] != NULL);

ptr[1] = Mem_Alloc(800); assert(ptr[1] != NULL);

ptr[2] = Mem_Alloc(800); assert(ptr[2] != NULL);

ptr[3] = Mem_Alloc(800); assert(ptr[3] != NULL);

while (Mem_Alloc(800) != NULL) ;

assert(Mem_Free(ptr[1]) == 0); assert(Mem_Free(ptr[2]) == 0);

ptr[2] = Mem_Alloc(1200); assert(ptr[2] == NULL);

coalesce();

ptr[2] = Mem_Alloc(1200); assert(ptr[2] != NULL);

exit(0); }