Project 04: Heap Management

Overview

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.

As demonstrated in malloc0.c from Lecture 15, writing a functional heap management system is relatively straightforward:

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.

To remedy this, we wrote malloc1.c, which utilizes a circular doubly-linked free list to keep track of only the free blocks as shown below:

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).
malloc will search this free list for a free block it can re-use. If no such block exists, it will simply fall-back to growing the heap with sbrk.
free will insert released blocks to the free list to make them available for future re-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).

To support different strategies in the same source file, we will use C's #if directive to select different blocks of code at compile time.
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.
Implement the complementary calloc and realloc functions.
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 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 individually, you are to create a library that implements malloc and free by 11:59PM on Monday, November 11, 2019. More details about this project and your deliverables are described below.

Heap Management

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.

Deliverables

As noted above, you are to work individually 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.

Timeline

Here is a timeline of events related to this project:

Date	Event
Monday, October 21	Project description and repository are available.
Saturday, November 2	Brainstorming should be completed.
Monday, November 11	Library is due (pushed to GitLab `malloc` branch).

Final Submission

For the final submission, please open a Merge Request on your repository (for your malloc branch to the master branch) and assign it to your grader from the Reading 08 TA List.

Repository

To start this project, you must fork the Project 04 repository on GitLab:

https://gitlab.com/nd-cse-30341-fa19/cse-30341-fa19-project04

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.

Note: Do your work in a separate git branch that can be later merged into the master branch (ie. make a malloc branch, DO NOT COMMIT OR MERGE TO MASTER).

Documentation

The Project 04 repository includes a README.md file with the following sections:

Student: This should be your name and email address.
Brainstorming: This should contain your responses to the provided brainstorming questions (optional for this project).
Reflection: This should contain your responses to the provided reflection questions.
Errata: This should contain a description of any known errors or deficiencies in your implementation.
Extra Credit: This should contain a description of any extra credit you attempted or completed.

You must complete this document report as part of your project.

Less is More

While it is tempting to write a long response to the brainstorming and reflection questions, please limit yourself to a few sentences at the most for each response.

This will facilitate more efficient grading and it will help you practice distilling ideas into their absolute essentials (which is useful for real world communication and for answering questions on exams).

Source Code

As you can see, the base Project 04 repository contains a README.md 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.

Compiling

To help you get started, we have provided a Makefile with all the necessary targets:

$ 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_03
Building bin/test_02
Building bin/test_00
Building bin/test_04
Building bin/unit_freelist
Building bin/test_05

$ make clean            # Removes all targets
Removing libraries
Removing tests

K.I.S.S.

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.

Running

Once you have the library, you can use it to override the existing malloc functions from the standard library by using the LD_PRELOAD trick:

# 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 free in cat to our library rather than the standard C library. To make this more convenient, you should consider creating a bin/run.sh script that sets the environment variable for you and then runs the specified command.

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)).

Implementation

All of the C header files are in the include/malloc folder, while the C source code for the malloc library is in the src folder. To help you get started, parts of the project are already implemented:

[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 Block 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 Block structure, which contains the aligned capacity of the requested allocation and the unaligned size of the requested allocation (neither of which includes space for 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 Block structure in the context of circular doubly-linked list with a sentinel node.
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 the dump_counters function to run when the program properly terminates.

You will need to implement the functions for computing the internal fragmentation and external fragmentation of the heap.
src/malloc_freelist.c: This file contains the functions for the free list.

You will need to think carefully about what needs to happen during searching and insertion.
src/malloc.c: This file contains the POSIX functions: malloc, free, calloc, realloc.

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.

Alignment

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 sufficient capacity).

A 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. 14) or if you really want to use the capacity of the Block (e.g. block->capacity) which stores the original aligned allocation capacity.

Failure to properly utilize this ALIGN macro will most likely lead to subtle and frustrating errors.

Testing

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
Testing libmalloc-ff.so ... success
Testing libmalloc-bf.so ... success
Testing libmalloc-wf.so ... success

Running run_test_05.sh
Timing libmalloc-ff.so ... 0m1.721s
Timing libmalloc-bf.so ... 0m2.776s
Timing libmalloc-wf.so ... 0m2.781s

Running run_test_06.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 bin/run_test_06.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 bin/run_test_06.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 bin/run_test_06.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

Debugging

While running the tests, you may encounter some segfaults and other memory errors. Because we are side-loading our own malloc implementation, you will need to do the following to debug a test application using gdb.

$ gdb ./bin/test_01
...
(gdb) set exec-wrapper env LD_PRELOAD=./lib/libmalloc-ff.so
(gdb) run
...
(gdb) bt

Basically, you want to first load gdb with the test program that is crashing. Next, you need to tell gdb to utilize the appropriate malloc library by creating an exec-wrapper that loads it into memory. Next, simply run the program. Once it segfaults, you can print a stack trace by using the bt command. From there, you can explore the state of your program and see if you can determine what went wrong.

Extra credit

Once you have completed your project, you may extend the implementation of the malloc library by performing either (or both) of the following modifications:

Make your malloc library thread-safe and then demonstrate its safety by making a test application that uses multiple threads that repeatedly call malloc and free.
Rather than having a single free list, modify your free list to internally utilize segregated lists such that allocations come out different lists based on the size of the request.

Each modification is worth 2.0 points each.

Note: Do your work in a separate git branch that can be later merged into the master branch (ie. make a ec-thread or ec-segregated branch, DO NOT COMMIT OR MERGE TO MASTER).

Grading

Your project will be graded on the following metrics:

Metric	Points
Source Code General Builds and cleans without warnings or errors Uses system calls appropriately Is consistent, readable, and organized On-time code submission Block Implements `block_release` properly Implements `block_detach` properly Implements `block_merge` properly Implements `block_split` properly Counters Implements `internal_fragmentation` properly Implements `external_fragmentation` properly Free List Implements `free_list_search_ff` properly Implements `free_list_search_bf` properly Implements `free_list_search_wf` properly Implements `free_list_insert` properly Implements `free_list_length` properly POSIX Implements `malloc` properly Implements `free` properly Implements `calloc` properly Implements `realloc` properly	21.0 *3.0* 0.5 0.5 1.0 1.0 *5.5* 1.0 0.5 2.0 2.0 *2.0* 1.0 1.0 *6.0* 1.0 1.0 1.0 2.0 1.0 *4.5* 1.5 1.0 1.0 1.0
Documentation Reflection	3.0 3.0

Commit History

To encourage you to work on the project regularly (rather than leaving it until the last second) and to practice performing incremental development, part of your grade will be based on whether or not you have regular and reasonably sized commits in your git log.

That is, you will lose a point if you commit everything at once near the project deadline.