(project concept thanks to Dr. Misurda.)
In this project, you will be implementing a memory allocator. You’ll be making your own versions of the malloc and free functions! Yay! Fun!
You are given the following source files to begin with. Right click and download these files. Read the comments inside them thoroughly before getting started.
mymalloc.c is where you’ll be writing all your code for this project.
mydriver.c file contains a
main function for you to expand upon. By default it just allocates and frees a single block of memory. As you work on your allocator, you can add more testing code to this driver program to make sure it works.
Makefile is a makefile to make your driver, and eventually, other test file(s) that I give you.
bigdriver.c file is a driver I made to test your allocator more thoroughly. READ THE COMMENTS INSIDE IT THOROUGHLY TO HELP DEBUG ANY ISSUES THAT COME UP.
bigdriver.c does a lot of tests, it might not catch all bugs. Look at it closely and add tests if you think it’s not thorough enough. You can change it and submit it along with your
Building and running
To build everything, use the following command line:
Ignoring warnings in this project would be a very, very bad idea. The
-Wall -Werror. Do not remove these. Fix all the warnings. SERIOUSLY.
Then, you should be able to:
You can do the same with
make bigdriver ./bigdriver
You will write
my_free which implement a simple memory allocator using a linked list and a next-fit allocation scheme. The performance won’t be great, but hey, it’s a class project, not a AAA game engine.
my_malloc function will:
- Round up the size of the requested allocation to a certain size (I gave you this)
- Try to find a block to reuse, using next-fit allocation
- If it found a block, and that block can be split into two smaller blocks, do so
- If it couldn’t find a block, expand the heap by moving the break with
- Mark it as used
- Return the pointer to the data part (after the header)
my_free function will:
- Figure out the pointer to the header
- Mark the block free
- Coalesce it with any neighboring blocks on either side
- If it’s the last block on the heap, contract the heap by moving the break with
Requirements and Grading
-  Submitted properly
-  Compiles with the
-  Coding style (don’t make two enormous functions, y’all.)
-  Properly maintains a linked list of blocks
-  Successfully completes provided test cases
- We will test your code with another driver besides the one we’ve given you.
-  Uses next-fit to find the next available block
-  Splits blocks when big enough to be split
-  If no free block is big enough, expands the heap with sbrk
-  Always returns a valid pointer to a new or previously-unused block!
-  Freed blocks can be reused on subsequent allocations
-  Coalesces neighboring free blocks
-  Contracts the heap with brk or sbrk when freeing the last block on the heap
Extra Credit  - that’s 2% of your final grade
While next-fit works, it’s still worst-case linear time to find a block. You can do better by using a more advanced data structure to store the free blocks. It’s up to you to choose what data structure to use - just as long as it results in better than linear time for allocation.
Follow this checklist:
make cleanto remove any executables.
- Include the following files in your
README.txttext file which contains any notes that might be helpful to the grader
- such as: is anything not working? did you do any extra credit? etc.
- Did you make a copy of that directory just in case?
- Did you put your full name and username at the top of each file in comments?
Name your file
Now you can submit using the same directions as lab1.