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

Instructions

Objective

Write a program to write replacement for malloc function in C language.

Requirements and Specifications

Most OS code is written in C. Having a good understanding and practice in C will help you better understand code in our readings. To complete C homework you are to write your own static library for dynamic allocation using freelists (Reference for Memory API: https://pages.cs.wisc.edu/~remzi/OSTEP/vm-api.pdf.

Reference for FreeList: https://pages.cs.wisc.edu/~remzi/OSTEP/vm-freespace.pdf).

You should write this library in standard C99 on a Linux/Unix system using mmap. The library should allocate (i.e., malloc) and deallocate (i.e., free). It does not have support growing the “heap” if out of memory (make the default mmap large enough to do a few mallocs). The first Fit strategy for selection is fine to use. Freeing memory should only combine segments if they are right next to each other. No need to recursively combine segments as this is just a toy library.

This is a reference on using ar to build a static library that can be linked against (https://tldp.org/HOWTO/Program-Library-HOWTO/static-libraries.html)

Screenshots of output

Source Code

Main.c

#include #include #include #include "mymalloc.h" int main() { void *ptr[20]; int i, j, k, tmp; int size; int pos[20]; /* seed the random generator using current time */ srand(time(NULL)); /* initialize the library */ mymalloc_init(); /* print initial list */ mymalloc_print_list(); for (i = 0; i < 3; i++) { printf("Allocating 100 bytes in pointer %d...\n", i + 1); ptr[i] = mymalloc(100); /* allocate 100 bytes */ if (ptr[i] == NULL) { printf("Error allocating memory\n"); return 1; } mymalloc_print_list(); } for (i = 0; i < 3; i++) { printf("Freeing pointer %d...\n", i + 1); myfree(ptr[i]); mymalloc_print_list(); } printf("Allocating 20 blocks of random size..\n"); for (i = 0; i < 20; i++) { size = (rand() % 91) + 10; // size between 10 and 100 printf("Allocating block %d of %d bytes\n", i, size); ptr[i] = mymalloc(size); if (ptr[i] == NULL) { printf("Error allocating memory\n"); return 1; } } mymalloc_print_list(); printf("Freeing all allocated blocks at random...\n"); /*make array with pointer numbers*/ for (i = 0; i < 20; i++) pos[i] = i; /* shuffle positions at random */ for (i = 0; i < 20; i++) { j = rand() % 20; k = rand() % 20; tmp = pos[j]; pos[j] = pos[k]; pos[k] = tmp; } /* do random frees */ for (i = 0; i < 20; i++) { printf("Freeing block %d\n", pos[i]); myfree(ptr[pos[i]]); } mymalloc_print_list(); return 0; }

Makefile

CC=gcc CFLAGS=-g -Wall -Werror -pedantic all: lib main lib: mymalloc.o ar rcs mymalloc.a mymalloc.o main: main.o mymalloc.a $(CC) main.o mymalloc.a -o main main.o: main.c $(CC) $(CFLAGS) -c main.c -o main.o mymalloc.o: mymalloc.h mymalloc.c $(CC) $(CFLAGS) -c mymalloc.c -o mymalloc.o clean: rm -f *.o main

Mymalloc.c

#include "mymalloc.h" /* Pointer to start of free list */ node_t *head = NULL; /* Initialize our memory manager */ void mymalloc_init() { /* allocate 4K for the heap in our library */ head = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0); head->size = 4096 - sizeof(node_t); head->next = NULL; } /* Allocate size bytes of memory in the heap, returns pointer to allocated space or NULL if there was not enough memory */ void *mymalloc(size_t size) { node_t *prev, *tmp, *new_blk; header_t *hdr; size_t req_size; /* avoid creating zero size blocks */ if (size == 0) return NULL; /* required size for block */ req_size = sizeof(header_t) + size; tmp = head; /* point to start of list */ prev = NULL; /* point to previous block */ /* look for a free block with enough space for the alloc (first fit) */ while (tmp != NULL && tmp->size < req_size) { prev = tmp; /* set current as previous */ tmp = tmp->next; /* advance to next block */ } /* if not enough free space */ if (tmp == NULL) { return NULL; } /* split block */ new_blk = (node_t *) (((char *) tmp) + req_size); /* create new block */ new_blk->next = tmp->next; /* next of new block is next on list */ new_blk->size = tmp->size - req_size; /* size is reduced by newly allocated space */ /* if we are allocating the first block in the list */ if (prev == NULL) { head = new_blk; /* advance head to new block */ } else /* else, we are inside the list */ { prev->next = new_blk; /* link previous to new block */ } /* put header info at start of allocated block */ hdr = (header_t *) tmp; hdr->size = size; hdr->magic = MAGIC; return (void *) (hdr + 1); /* return pointer to space after header */ } /* Free the space allocated previously by mymalloc */ void myfree(void *ptr) { node_t *new_blk, *prev, *tmp; header_t *hptr; size_t size; /* avoid null pointers */ if (ptr == NULL) return; hptr = (header_t *) ptr - 1; /* ensure we are pointing to a block allocated by us */ assert(hptr->magic == MAGIC); size = hptr->size; /* get block size */ new_blk = (node_t *) hptr; /* point to start of new free block */ new_blk->size = size + sizeof(header_t) - sizeof(node_t); /* get size of free space */ tmp = head; /* point to start of list */ prev = NULL; /* point to previous block */ /* look for place to insert new block */ while (tmp != NULL && tmp < new_blk) { prev = tmp; /* set current as previous */ tmp = tmp->next; /* advance to next block */ } assert(tmp != NULL); /* check for bad pointer */ new_blk->next = tmp; /* point to next on list */ if (prev == NULL) /* if new block is behind the head */ { head = new_blk; } else /* if we are inside the list */ { prev->next = new_blk; /* set previous pointer to new block */ /* try to coalesce previous with new block */ if ((node_t *) ((char *)(prev + 1) + prev->size) == new_blk) { prev->next = new_blk->next; prev->size += new_blk->size + sizeof(node_t); new_blk = prev; /* use coalesced block as new block */ } } if (new_blk->next != NULL) { tmp = new_blk->next; /* try to coalesce new block with next */ if ((node_t *) ((char *)(new_blk + 1) + new_blk->size) == tmp) { new_blk->next = tmp->next; new_blk->size += tmp->size + sizeof(node_t); } } } /* Prints the current free list on the standard output */ void mymalloc_print_list() { node_t *tmp; printf("Free list:\n"); tmp = head; /* start at head */ while (tmp != NULL) { printf(" %p: [%d, %p]\n", (void *) tmp, tmp->size, (void *) tmp->next); tmp = tmp->next; } printf("\n"); }

Mymalloc.h

#ifndef MYMALLOC_H #define MYMALLOC_H #include #include #include #include #define MAGIC 0x1234567 /* magic number for the block header */ /* Definition of the block header */ typedef struct { int size; int magic; } header_t; /* Definition of a free node */ typedef struct __node_t { int size; struct __node_t *next; } node_t; void mymalloc_init(); void *mymalloc(size_t size); void myfree(void *ptr); void mymalloc_print_list(); #endif /* MYMALLOC_H */