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:

  1. It doesn't actually free anything, so it is quite possible (and likely) that we would eventually run out of memory.

  2. 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:

  1. It maintains a free list of all the free blocks (previously allocated blocks that are no longer in use).

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

  3. 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:

  1. Ensure that all memory allocations are aligned to the nearest word size.

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

  3. Implement shrinking the heap when a block is released.

  4. Implement splitting a block when it is re-used.

  5. Implement merging a block when it is inserted into the free list.

  6. Implement the complimentary calloc and realloc functions.

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

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

Timeline

Here is a timeline of events related to this project:

Date Event
Monday, October 22 Project description and repository are available.
Friday, November 2 Library is due (pushed to GitLab master branch).
Friday, November 9 Demonstrations of library must be completed.

Repository

To start this project, one group member must fork the Project 04 repository on GitLab:

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

Once this repository has been forked, follow the instructions from Reading 00 to:

  1. Make the repository private.

  2. Configure access to the repository.

    Make sure you add all the members of the team in addition to the instructional staff.

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_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

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:

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:

  1. src/malloc_block.c: This file contains the functions for the Block 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 Block structure in the context of circular doubly-linked list with a sentinel node.

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

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

  4. 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 the aligned size provided by ALIGN(block->size) (e.g. 16).

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

Benchmarks

Once you have a working implementations of your custom malloc library, you should benchmark your library to answer the following questions:

  1. Which heap management strategy requires the least amount of heap space? Which one is the worst?

  2. Which heap management strategy allows for the most splits or the most merging/coalescing?

  3. Which heap management strategy was the fastest? slowest?

  4. Which heap management strategy exhibited the least fragmentation?

Consider using the following applications to help you answer the questions above: cat, md5sum, sort, dd, du, and find.

You must create scripts or additional programs that perform these benchmarks and collect the data.

Demonstration

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.

Presentation

As part of your demonstration, you must provide a presentation (between 5 - 10 slides) with the following content:

  1. Design: An overview of your library implementation.

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

  3. Analysis:: A discussion of the following question: Overally, which heap management strategy is the best?

    You should provide evidence for your choices.

  4. 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:

Documentation

As noted above, the Project 04 repository includes a README.md file with the following sections:

  1. Members: This should be a list of the project members.

  2. Demonstration: This is where you should provide a Google Drive link to your demonstration slides.

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

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:

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

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

Grading

Your project will be graded on the following metrics:

Metric Points
Source Code
  1. General
    • Builds and cleans without warnings or errors
    • Uses system calls appropriately
    • Is consistent, readable, and organized
    • On-time code submission

  2. Block
    • Implements block_release properly
    • Implements block_detach properly
    • Implements block_merge properly
    • Implements block_split properly

  3. Counters
    • Implements internal_fragmentation properly
    • Implements external_fragmentation properly

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

  5. POSIX
    • Implements malloc properly
    • Implements free properly
    • Implements calloc properly
    • Implements realloc properly

  6. Benchmarks
    • Provides scripts that automate data generation
    • Provides scripts that automate data collection
 19.0
  1. 3.0
    • 0.5
    • 0.5
    • 1.0
    • 1.0

  2. 4.5
    • 1.0
    • 0.5
    • 1.5
    • 1.5

  3. 2.0
    • 1.0
    • 1.0

  4. 5.5
    • 1.0
    • 1.0
    • 1.0
    • 2.0
    • 0.5

  5. 3.0
    • 1.0
    • 1.0
    • 0.5
    • 0.5

  6. 1.0
    • 0.5
    • 0.5
Demonstration
  1. Slides
  2. Benchmarks
  3. Analysis
 4.0
  1. 1.0
  2. 2.0
  3. 1.0
Documentation
  1. Design
 1.0
  1. 1.0