This is an archived copy of a previous semester's site.
Please see the current semester's site.
In this MP, you will implement four functions to match their documented behavior: calloc, malloc, realloc, and free.
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:
malloc, calloc, free, and realloc using only the sbrk system call.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.
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 gitYou can then git clone your GitHub repository on the VM and proceed to code as usual, including using the VSCode debugger.
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" cs340From inside Docker you can run command-line code; for example
cd mp3
make clean
make
make test
./testHowever, you cannot use the VSCode debugger from inside Docker. If you wish to debug, using the Course Virtual Machine is a better option.
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"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.
In your solution, you must only modify the following file. Modifications of other files may break things:
alloc.cNot 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.
make to compile your alloc.c code../mreplace tests/samples_exe/00-simpletests/samples/00-simple.c to help you debug.make test to compile the test suite../test "[part=1]" to run the tests that have been tagged with "[part=1]".malloc implementation on a specific sample1 file, run ./mstats tests/samples_exe/sample1Here 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 limitDebuggers 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.
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.
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.
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.
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.
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.
./test "[part=5]" to run the tests related to advanced testers. The source files for these advanced testers and their purposes are as follows:
malloc()s, assigns, and free()s a single intmalloc()d and assigned in succession, all free()d at the endmalloc()s, memsets(), and free()s of a megabyte of data at a timemalloc() a large amount of memory, recursively realloc() into smaller chunks, coalesce back togethercalloc()s, assigns, and free()s a single intThe 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:
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 pushThe initial grading is done via a manual GitHub Action. You MUST complete this step before the deadline to earn any points for the MP:
ActionTab
mp3 autograding
Run Workflowbutton (located on the blue bar)
Run Workflow
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.