The fourth project is to build your own implementation of malloc and free. That is, you will need to implement a library that interacts with the operating system to perform heap management on behalf of a user process as demonstrated in class. Using the Lecture 15: Example Code as a starting point, you will need to add the following features:
Implement splitting and coalescing of free blocks.
Implement additional heap management strategies: Next Fit, Best Fit, and Worst Fit (First Fit has already been implemented for you).
Add counters for tracking of the following events:
Maximum size of the heap
This information should be reported whenever the program exits (hint: atexit) and should look like this:
mallocs: 6 frees: 6 reuses: 2 grows: 4 splits: 1 coalesces: 1 blocks: 4 requested: 6144 max heap: 4096
Create tests to check the correctness of your implementations.
Create benchmarks to analyze the metrics above for the different strategies.
Note: We will not consider thread-safety or support multiple threads at all for this project.
Working in groups of one or two people, you are to create a library that implements malloc and free by midnight on Thursday, November 9, 2017. Additionally, you are benchmark and analyze your library by Tuesday, November 14, 2017.
More details about this project and your deliverables are described below.
Implementing your own heap management library is more common than you think. For instance, Firefox uses jemalloc, while GNU uses dlmalloc, and Google provides tcmalloc. As hardware and operating systems evolve, the optimal heap management strategies change as well, and so developers continue to advance the state of the art. For this project, we will focus on understanding the basics and getting something that works (good enough).
For a reference on how to create a simple heap management library, I recommend: A quick tutorial on implementing and debugging malloc, free, calloc, and realloc. This is what I used as the basis for the Lecture 15: Example Code.
As noted above, you are to work in groups of one or two (three is permitted, but discouraged) to implement your heap management library. You must use C (not C++) as the implementation language. Any test scripts or auxillary tools can be written in any reasonable scripting language.
Here is a timeline of events related to this project:
|Sunday, October 29||Project description and repository are available.|
|Thursday, November 2||Test scripts are available from the TA (once you check off your design).|
|Thursday, November 9||Library is due (pushed to GitLab).|
|Tuesday, November 14||Demonstrations of library must be completed.|
Once this repository has been forked, follow the instructions from Reading 00 to:
Make the repository private
Configure access to the repository
Make sure you add all the members of the team in addition to the instructional staff.
As you can see, the base Project 04 repository contains a
file and the following folder hierarchy:
project04 \_ Makefile # This is the project Makefile \_ bin # This contains the binary executables and scripts \_ lib # This contains the malloc library when built \_ src # This contains the malloc source code \_ malloc.c # This contains the malloc implementation from Lecture 15
You must maintain this folder structure for your project and place files in their appropriate place.
To help you get started, we have provided a
Makefile that will build the
First Fit library for you:
# Build First First version of malloc library $ make lib/libmalloc-ff.so gcc -shared -fPIC -g -gdwarf-2 -std=gnu99 -Wall -DFIT=0 -o lib/libmalloc-ff.so src/malloc.c
Once you have the library, you can use it to override the existing malloc
by using the
# Use our implementation of library $ env LD_PRELOAD=lib/libmalloc-ff.so cat README.md
This will load our library first and thus link any calls to malloc and
cat to our library rather than the standard C library. To
make this more convenient, you should consider creating a
script that sets the environment variable for you and then runs the
In addition to the
Makefile, we have also provided the initial
implementation of malloc and free from the Lecture 15: Example Code.
TODOs to mark where you should consider modifying the
library. Of course, you are free to do as you wish, as long as you
implement the malloc and free API.
While the exact organization of the project code is up to you, keep in mind that you will be graded in part on coding style, cleaniness, and organization. This means your code should be consistently formatted, not contain any dead code, have reasonable comments, and appropriate naming among other things:
Break long functions into smaller functions.
Make sure each function does one thing and does it well.
Abstract, but don't over do it.
Please refer to these Coding Style slides for some tips and guidelines on coding style expectations.
As you develop your library, you should create functional or unit tests that ensure your heap management library works correctly. These tests could take any of the following forms:
Functional: This could be a script that runs an existing command such as cat with your library and ensures it runs properly.
Unit: This could be a test program you write that tests individual
functions such as
grow_heap or any other functions you
You must have both functional and unit tests for full credit.
Once you have working implementations of the four heap management stratgies and you have added the ability to track and report the information described above, you should benchmark your library to answer the following questions:
Which heap management strategy does the best job of reusing free blocks? Which one is the worst?
Which heap management strategy requires the least amount of heap space? Which one is the worst?
Which heap management strategy allows for the most splits? most coalescing? least?
Which heap management strategy was the fastest? slowest?
You must create scripts or additional programs that perform these benchmarks and collect the data.
As part of your demonstration, you must provide a presentation (between
10 slides) with the following content:
Design: An overview of your library implementation.
Testing: A discussion on how you tested your library.
Benchmarks: A discussion on how you benchmarked your library and what the results were. You should address each of the questions above and have data and diagrams to backup your presentation.
Analysis:: A discussion of the following questions:
Which heap management strategy suffers the most from fragmentation (what type)?
Which heap management strategy is the best?
You should provide evidence for your choices.
Summary: A summary of what you learned about memory management.
Note, you must incorporate images, graphs, diagrams and other visual elements as part of your presentation where reasonable.
Please upload these slides to Google Drive and place a link in your
Be prepared to be asked about different aspects of your project, as the TA may ask you questions to probe your understanding of the material and your work.
As noted above, the Project 04 repository includes a
with the following sections:
Members: This should be a list of the project members.
Design: This is a list of design questions that you should answer before you do any coding as they will guide you towards the resources you need.
Demonstration: This is where you should provide a Google Drive link to your demonstration slides.
Errata: This is a section where you can describe any deficiencies or known problems with your implementation.
You must complete this document report as part of your project.
You should look at the design questions in the
README.md file of the
Project 04 repository. The questions there will help you design and plan
your process queue implementation.
Feel free to ask the TAs or the instructor for some guidance on these questions before attempting to implement this project.
Improve your coalescing mechanism so that it combines surrounding blocks rather than just the next block (when possible).
Add the ability to shrink the heap when possible.
Each modification is worth 0.5 points each.
Your project will be graded on the following metrics: