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.
Simply grow the heap using the sbrk system call whenever the user requests memory at run-time.
Unfortunately, this initial version of a heap manager has some serious problems:
It doesn't actually free anything, so it is quite possible (and likely) that we would eventually run out of memory.
It doesn't keep track of blocks that have been allocated but are no longer in-use (ie. free), so it will never re-use a previous allocation. This is both wasteful (as there is memory that we could use, but don't), and it is slow because we are then forced to call sbrk, which is a system call and thus incurs the overhead of context switching.
The malloc1.c shown in class has the following features:
It maintains a free list of all the free blocks (previously allocated blocks that are no longer in use).
While this second version is better than the first heap manager, it is still lacking important features. For this project, you are to extend the functionality of the malloc1.c allocator to incorporate the following:
Ensure that all memory allocations are aligned to the nearest word size.
Implement multiple search algorithms (First Fit, Best Fit, and Worst Fit).
Implement shrinking the heap when a block is released.
Implement splitting a block when it is re-used.
Implement merging a block when it is inserted into the free list.
Add counters to keep track of number of operations performed by the allocator and the amount of internal fragmentation and external fragmentation. When the process exits, the library should output the following type of information (based on the counters):
blocks: 0 free blocks: 0 mallocs: 10 frees: 10 callocs: 0 reallocs: 0 reuses: 0 grows: 10 shrinks: 10 splits: 0 merges: 0 requested: 10240 heap size: 0 internal: 0.00 external: 0.00
Once you have a working malloc implementation (as verified by the provided functional and unit tests), you are to create benchmarks to analyze the metrics above for the different heap management strategies.
Note: We will not consider thread-safety or support multiple threads at all for this project.
Working in groups of one, two, or three people, you are to create a library that implements malloc and free by midnight on Friday, November 2, 2018. Additionally, you are benchmark and analyze your library by Friday, November 9, 2018.
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 initially used as the basis for this project.
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:
|Monday, October 22||Project description and repository are available.|
|Friday, November 2||Library is due (pushed to GitLab
|Friday, November 9||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 test scripts \_ include \_ malloc # This contains the malloc library header files \_ lib # This contains the malloc library when built \_ src # This contains the malloc library source code \_ tests # This contains the functional and unit test code
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 with all the
$ make # Build libraries and test applications Building lib/libmalloc-ff.so Building lib/libmalloc-bf.so Building lib/libmalloc-wf.so Building bin/test_01 Building bin/unit_block Building bin/test_02 Building bin/test_00 Building bin/test_04 Building bin/unit_freelist Building bin/test_03 $ make clean # Removes all targets Removing libraries Removing tests
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.
Once you have the library, you can use it to override the existing malloc
functions from the standard library 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
Note: there are three versions of our custom malloc implementation, where each version corresponds to a different search algorithm (first fit (ff), best fit (bf), and worst fit (wf)).
[x] include/malloc/block.h # Block structure header (implemented) [x] include/malloc/counters.h # Counters header (implemented) [x] include/malloc/freelist.h # Free List header (implemented) [~] src/malloc_block.c # Block structure definitions (partially implemented) [~] src/malloc_counters.c # Counters definitions (partially implemented) [ ] src/malloc_freelist.c # Free List definitions (not implemented) [~] src/malloc.c # POSIX definitions (partially implemented)
Basically, the malloc1.c code demonstrated in Lecture 15 was taken and split into separate files to form the skeleton provided to you. Additionally, we have implemented most of the desired counting functionality for you, so you can concentrate on just the block manipulation and free list management operations. Each of the functions in the incomplete files above have comments that describe what needs to be done.
You will need to examine these source files and complete the implementation
of a malloc library that uses a circular doubly-linked free list to
track free blocks. To do so, you should start with the basic
functions, then move to the free list functions. Once those pass the
provided unit tests, you should then utilize those components to complete
the malloc, free, calloc, and realloc functions:
src/malloc_block.c: This file contains the functions for the
structure, which contains the unaligned
size of the requested
allocation (not including the embedded
Block structure), and pointers to
the previous and next
Block structures. If the
Block is detached, then
it should just point to itself.
You will need to think carefully about how to manipulate the
structure in the context of circular doubly-linked list with a sentinel
src/malloc_counters.c: This file contains the functions for keeping
track of the various counters utilized in the library. Whenever malloc
is called, it will call the
init_counters function which will register
dump_counters function to run when the program properly terminates.
src/malloc_freelist.c: This file contains the functions for the free
You will need to think carefully about what needs to happen during searching and insertion.
You will need to think carefully about which of the previous functions you want to utilize.
Note: There are also some
TODOs to help identify which parts you need
to implement, along with how you will want to modify the counters.
For better performance, all memory allocations should be aligned by the
word size of the current machine. For instance, if the user requests
14 bytes and our word size is
8 bytes, then we will actually allocate
16 bytes as this is the nearest multiple of the word size (that has
ALIGN macro is provided to you that will perform this rounding
automatically for you. Whenever you are comparing or determining
sizes, you need to think carefully if you want to use the original size
as requested by the user and stored in the
Block structure (e.g.
if you really want the aligned size provided by
Failure to properly utilize this
ALIGN macro will most likely lead to
subtle and frustrating errors.
As you develop your library, you should utilize the provided functional and unit tests that ensure your heap management library works correctly:
$ make test # Build and runs test programs Running unit_block 0 Running unit_block 1 Running unit_block 2 Running unit_block 3 Running unit_block 4 Running unit_freelist 0 Running unit_freelist 1 Running unit_freelist 2 Running unit_freelist 3 Running unit_freelist 4 Running run_test_00.sh Testing libmalloc-ff.so ... success Testing libmalloc-bf.so ... success Testing libmalloc-wf.so ... success Running run_test_01.sh Testing libmalloc-ff.so ... success Testing libmalloc-bf.so ... success Testing libmalloc-wf.so ... success Running run_test_02.sh Testing libmalloc-ff.so ... success Testing libmalloc-bf.so ... success Testing libmalloc-wf.so ... success Running run_test_03.sh Testing libmalloc-ff.so ... success Testing libmalloc-bf.so ... success Testing libmalloc-wf.so ... success Running run_test_04.sh Timing libmalloc-ff.so ... 0m1.721s Timing libmalloc-bf.so ... 0m2.776s Timing libmalloc-wf.so ... 0m2.781s Running run_test_05.sh Testing libmalloc-ff.so (cat tests/test_00.c tests/test_01.c tests/test_02.c tests/test_03.c tests/test_04.c tests/unit_block.c tests/unit_freelist.c)... success Testing libmalloc-bf.so (cat tests/test_00.c tests/test_01.c tests/test_02.c tests/test_03.c tests/test_04.c tests/unit_block.c tests/unit_freelist.c)... success Testing libmalloc-wf.so (cat tests/test_00.c tests/test_01.c tests/test_02.c tests/test_03.c tests/test_04.c tests/unit_block.c tests/unit_freelist.c)... success Testing libmalloc-ff.so (md5sum bin/run_test_00.sh bin/run_test_01.sh bin/run_test_02.sh bin/run_test_03.sh bin/run_test_04.sh bin/run_test_05.sh)... success Testing libmalloc-bf.so (md5sum bin/run_test_00.sh bin/run_test_01.sh bin/run_test_02.sh bin/run_test_03.sh bin/run_test_04.sh bin/run_test_05.sh)... success Testing libmalloc-wf.so (md5sum bin/run_test_00.sh bin/run_test_01.sh bin/run_test_02.sh bin/run_test_03.sh bin/run_test_04.sh bin/run_test_05.sh)... success Testing libmalloc-ff.so (sort src/malloc_block.c src/malloc.c src/malloc_counters.c src/malloc_freelist.c)... success Testing libmalloc-bf.so (sort src/malloc_block.c src/malloc.c src/malloc_counters.c src/malloc_freelist.c)... success Testing libmalloc-wf.so (sort src/malloc_block.c src/malloc.c src/malloc_counters.c src/malloc_freelist.c)... success Testing libmalloc-ff.so (dd if=/dev/urandom of=/dev/null bs=1024 count=1024)... success Testing libmalloc-bf.so (dd if=/dev/urandom of=/dev/null bs=1024 count=1024)... success Testing libmalloc-wf.so (dd if=/dev/urandom of=/dev/null bs=1024 count=1024)... success Testing libmalloc-ff.so (du /lib/)... success Testing libmalloc-bf.so (du /lib/)... success Testing libmalloc-wf.so (du /lib/)... success Testing libmalloc-ff.so (find /lib/)... success Testing libmalloc-bf.so (find /lib/)... success Testing libmalloc-wf.so (find /lib/)... success
Note, you can run tests individually:
$ ./bin/run_test_00.sh Testing libmalloc-ff.so ... success Testing libmalloc-bf.so ... success Testing libmalloc-wf.so ... success
Once you have a working implementations of your custom malloc library, you should benchmark your library to answer the following questions:
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 or the most merging/coalescing?
Which heap management strategy was the fastest? slowest?
Which heap management strategy exhibited the least fragmentation?
You must create scripts or additional programs that perform these benchmarks and collect the data.
As part of your grade, you will need to present your library to a TA where you will demonstrate the correctness of your malloc library along with an analysis of the heap management strategies.
As part of your demonstration, you must provide a presentation (between
10 slides) with the following content:
Design: An overview of your library implementation.
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 question: Overally, 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.
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.
To arrange your demonstration time, please complete the form below:
As noted above, the Project 04 repository includes a
with the following sections:
Members: This should be a list of the project members.
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.
Once you have completed your project, you may extend the implementation of the malloc library by performing either (or both) of the following modifications:
Each modification is worth 2.0 points each.
Your project will be graded on the following metrics: