In this MP, you will implement four functions to match their documented behavior: calloc, malloc, realloc, and free.

1 Overview

The functions have two parts: a wrapper around the system call sbrk to manage the size of the heap and internal data stored to track and allow re-use of freed memory.

A minimal implementation that does not allow re-use of freed memory would be the following:

void *malloc(size_t size) { return sbrk(size); }
void free(void *ptr) {}

As you can see, when we request size bytes of memory, we call sbrk(size) to increase the heap by size bytes. Then, we return a pointer to this memory, and we’re done. This is a working implementation of malloc, but it cannot reuse freed memory. It also doesn’t check for errors when we call sbrk, and it doesn’t implement realloc or calloc. Your job is to make a better version that does not have these limitations.

In this MP:

You will implement the full suite of allocation functions malloc, calloc, free, and realloc using only the sbrk system call.
You will understand foundational ideas on how heap memory is managed.
You will gain an enormous amount of experience with pointers.
You will have completed one of the longest-running MPs in the history of the University of Illinois! :)

2 Can’t use MacOS

MacOS doesn’t let user code override the built-in malloc. If you run MacOS, you’ll either have to use your course virtual machine or run your code in Docker. If you run Linux, either natively or in the WSL, you don’t need to use a virtual machine or Docker but still may do so if you wish.

2.1 Course virtual machine

Visit our VM page for how to set up VSCode to connect to your course virutal machine.

You’ll probably need to install some build tools on the VM; one way to do this is to run the followiing in the VM terminal:

 sudo apt-get install build-essential gdb valgrind git

You can then git clone your GitHub repository on the VM and proceed to code as usual, including using the VSCode debugger.

2.2 Course Docker

From inside your mp3 directory, set up Docker (once) by running

docker build -t cs340  .

Once Docker is set up, you can use it to make and test your code be entering Docker as

docker run --rm -it -v "`pwd`:/mp3" cs340

From inside Docker you can run command-line code; for example

cd mp3
make clean
make
make test
./test

However, you cannot use the VSCode debugger from inside Docker. If you wish to debug, using the Course Virtual Machine is a better option.

3 Initial Files

In your CS 340 directory, merge the initial starting files with the following commands:

git fetch release
git merge release/mp3 --allow-unrelated-histories -m "Merging initial files"

4 Machine Problem

Implement the malloc, free, calloc and realloc functions to match their official manual pages. Implement them in a file named alloc.c by using the sbrk system call.

You implementation must make some re-use of free’d memory by using block splitting, free memory coalescing, and free lists (all described below).

You have multiple weeks to fully complete this MP, but you must complete the initial work in the first week.

Week 1 implements an efficient memory allocator.

Week 2 passes various more advanced tests.

5 Modifiable Files

In your solution, you must only modify the following file. Modifications of other files may break things:

alloc.c

6 Week 1: Implementing Basic Memory Allocator

Not sure how to get started or test this program? We’ve made a Building Malloc guide to help you get started!

We require that your implementation be efficient in both space and time. Part of space efficiency requires that the memory used by an allocated block be no larger than 24 bytes + the size of the block.

6.1 Running Your Program

In your terminal, type make to compile your alloc.c code.
Run your program with a simple allocator using ./mreplace tests/samples_exe/00-simple
You can inspect what this code is doing by taking a look at tests/samples/00-simple.c to help you debug.

6.2 Testing Your Program

In your terminal, type make test to compile the test suite.
Run ./test "[part=1]" to run the tests that have been tagged with "[part=1]".
To evaluate your malloc implementation on a specific sample1 file, run ./mstats tests/samples_exe/sample1

Here is what some of the error codes you may encounter mean:

11: (SIGSEGV) Segmentation fault
15: (SIGTERM) Timed out
65, 66: Dynamic linking error
67: Failed to collect memory info
68: Exceeded memory limit
91: Data allocated outside of heap
92: Data allocated exceeds heap limit

6.3 Adding Print Statements

Debuggers have trouble when malloc is broken, so you’ll probably want print statements to help you understand what’s going on. A print_heap function that reads and displays information contained in your heap entry metadata can be a very useful addition.

Note that printin can slow down your coe a lot, so you might want to comment out the body of that print_heap function when running larger test cases.

Our Building Malloc has code to print your heap as part of malloc and you just need to make it into a function.

7 Memory Allocator Design Ideas

There are many ways to make a good memory allocator, and creativity is encouraged. Your design should reuse free memory whenever it can. You should include implementations that include block splitting, memory coalescing, and free lists.

7.1 Basic Malloc

We have a separate page that walks you through one possible design of a basic malloc and free implementation. It’s a great place to start!

Run ./test "[part=1]" to run the tests related to basic malloc.

7.2 Block Splitting

When memory is re-used, it is very easy to simply mark the entire block as used again even if the block is not a perfect fit. Block splitting instead splits a block if there’s enough space left over to leave some free space for a future allocation.

With successful block splitting, you should see the r1 allocation in the sample1 program split one of the large free blocks into a block of size 10 for r1 and a large remaining free block for future allocations.

Run ./test "[part=2]" to run the tests related to block splitting.

7.3 Memory Coalescing

When memory is freed, two blocks of free memory may appear next to one-another. In our example, this happened with a and b. Memory Coalescing combines the blocks together to create one larger block.

With successful memory coalescing, you should see the free block of a and b in the sample1 program join together for a free block of over 500 bytes.

Run ./test "[part=3]" to run the tests related to memory coalescing.

7.4 Free Lists

Simple versions of malloc scan all blocks in the heap looking for free ones that are large enough for the current allocation. Free lists instead use a linked list or other data structure to traverse only the free blocks.

With successful free lists, your list of memory should skip over all blocks that are in use and list only the free blocks.

Run ./test "[part=4]" to run the tests related to free lists.

8 Week 2: Advanced Testers

8.1 Running Your Program

Run ./test "[part=5]" to run the tests related to advanced testers. The source files for these advanced testers and their purposes are as follows:
- mp0-gif - MP0, but with your malloc! :)
- tester1.c - repeatedly malloc()s, assigns, and free()s a single int
- tester2.c - several ints malloc()d and assigned in succession, all free()d at the end
- tester3.c - several malloc()s, memsets(), and free()s of a megabyte of data at a time
- tester4.c - malloc() a large amount of memory, recursively realloc() into smaller chunks, coalesce back together
- tester5.c - repeatedly calloc()s, assigns, and free()s a single int

8.2 Passing Advanced Tests

The tests/testers directory contains many advanced tests that do really stretch your memory allocator in terms of the number of requests, the sizes of the requests, and more.

The mp0-gif test

The mp0-gif test checks if your malloc works given a real workload. Because it is running a real workload, not a small hand-built test case, it has several properties that other tests lack:

It allocates and frees various size blocks of memory in a non-trivial order, resulting in more memory fragmentation than other tests.
It depends on the specific contents of allocated memory to function correctly, resulting in a more accurate test that only allocated but not freed memory is accessed and that each free returns the correct part of memory to be allocated in the future.

9 Submission and Grading

9.1 Submission

Once you have locally passed all the tests, you will need to submit and grade your code. First commit using the standard git commands:

git add -A
git commit -m "MP submission"
git push

9.2 Grading

The initial grading is done via a manual GitHub Action. You MUST complete this step before the deadline to earn any points for the MP:

Navigate to your repository on https://github.com/cs340-illinois.
Click on the Action Tab
Choose mp3 autograding
Click the green Run Workflow button (located on the blue bar)
Press Run Workflow
You will trigger a GitHub Action that will complete the grading run!

9.3 Points

This MP is worth as much as 2 MPs: week 1 is worth one, and week 2 worth another.

Week 1’s points are divided evenly between a basic allocator, block splitting, memory coalescing, and free lists.

Week 2’s points are half a repetition of Week 1’s; if those pass (and only if they do), the other half is new, more advanced tests.