Overview

Your third MP in CS 340 is writing your own memory allocator! You will write your implementations of calloc, malloc, realloc, and free in alloc.c.

Memory allocation seems like a mystery, but in actuality, we are making a wrapper around the system call sbrk. Here’s a really simple implementation of malloc:

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

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

Here is our implementation of free:

void free(void *ptr) {
}

This is a “correct” way to implement free. However, the obvious drawback with our implementation is that we can’t reuse memory after we are done with it. Also, we have not checked for errors when we call sbrk, and we have not implemented realloc or calloc.

Despite all of this, this is still a “working” implementation of malloc. So, the job of malloc is not really to allocate memory, but to keep track of the memory we’ve allocated so that we can reuse it.

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! :)

MP Overview Session

An MP Overview Session will be held by Anna on Thursday, Sep. 15 at 5:00pm.

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"

Machine Problem

Implement the malloc, free, calloc and realloc functions described in the Linux documentation manual https://man7.org/linux/man-pages/man3/free.3.html in 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 two weeks to fully complete this MP, but you must complete the initial work in the first week:

• Week #1 Deadline (Sep. 20 by 11:59pm): You must complete Parts 1-4 before Sep. 20. This implements an efficient memory allocator.
• Week #2 Deadline (Sep. 27 by 11:59pm): You must complete the advanced tests (Part 5) by Sep. 27.

Modifiable Files

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

• alloc.c

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

Running Your Program

• In your terminal, type make to compile your alloc.c code.
• 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

# Build the Docker container:
docker build -t cs340  .

# Run make clean, make, run the test suite, and run ./mstats:
docker run --rm -it -v `pwd`:/mp3 cs340 "make clean"
docker run --rm -it -v `pwd`:/mp3 cs340 "make"
docker run --rm -it -v `pwd`:/mp3 cs340 "./test [part=1]"
docker run --rm -it -v `pdf`:/mp3 cs340 "./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

Adding Print Statements

I highly encourage you to add a print_heap function to your code, if you have not done so already. Our “Building Malloc” has code to print your heap as part of malloc and you just need to make it into a function.

When you want to run your program without the print output, you can simple comment out the contents of your print_heap function. You will find for all non-trivial tests the print statements will slow down your code far, far too much.

Memory Allocator Design Ideas

At this point, there are a lot of ways to be creative to make a good memory allocator. As a minimum, we need to make sure to reuse the free memory when available. Additionally, we need to optimize our use of heap memory in a few ways. Here’s a few ideas:

1. [Block Splitting]: When memory is re-used, it is very easy to simply mark the block isUsed to be 1 again even if the block is not a perfect fit. Could you split 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.

2. [Memory Coalescing]: Currently, when memory is freed, two blocks of free memory may appear next to one-another. In our example, this happened with a and b. Could you combine 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.

3. [Free Lists]: Right now, we have to traverse both used and free blocks when walking through our memory. Could we create a linked list or other data structure to allow us 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.

Part 2: Block Splitting

Implement block splitting in your memory allocator.

Running Your Program

• Run ./test "[part=2]" to run the tests related to Block Splitting.

Running Samples

Several sample programs are provided on which your malloc implementation is evaluated. In each of these descriptions, the below values are the MAX values expected when running ./mstats (ex: ./mstats tests/samples_exe/sample1).

• tests/samples_exe/sample1 is the sample from the “Building Malloc” guide. and is a great sample to test block splitting.

  • Without block splitting, sample1 should MAX around 1,600 bytes of memory.
  • With block splitting, sample1 should MAX around 1,100 bytes of memory.
    
    

Note: You have to implement Part 3 to pass the test for Part 2.

Part 3: Memory Coalescing

Implement free memory coalescing in your memory allocator.

Running Your Program

• Run ./test "[part=3]" to run the tests related to Memory Coalescing.
• Note: The output that you are printing is really useful for debugging, but will make the allocator very slow due to printing the messages on the screen. You should remove lines related to the output when running more complex programs.

Running Samples

• tests/samples_exe/sample2 is a great sample to debug memory coalescing.

  • Without memory coalescing, sample2 should MAX around 9,000 bytes of memory.
  • With memory coalescing, sample2 should MAX around 6,500 bytes of memory.
    
    

• tests/samples_exe/sample3 tests memory coalescing in reverse order (this one is trickier).

  • Without memory coalescing, sample3 should MAX around 9,000 bytes of memory.
  • With memory coalescing, sample3 should MAX around 6,500 bytes of memory.
    
    

• tests/samples_exe/sample4 tests memory coalescing with extra free blocks around that cannot be coalesced.

  • Without memory coalescing, sample4 should MAX around 11,000 bytes of memory.
  • With memory coalescing, sample4 should MAX around 9,000 bytes of memory.
    
    

Part 4: Free Lists

Implement free lists in your memory allocator.

Running Your Program

• Run ./test "[part=4]" to run the tests related to Free Lists.

Running Samples

• tests/samples_exe/sample5 tests a “free list” by having allocated blocks before/after the freed element. This is a simple version of sample6.

• tests/samples_exe/sample6 tests your “free list” by having LOTS of allocated blocks before/after your free block.

  • If you are NOT reusing blocks, sample6 will run quickly but will use over 3,000,000 bytes of memory.
  • If you are re-using blocks, sample6 should run quickly when a linked list of free nodes are maintained (ex: TIME less than about 0.1s).
  • If you are re-using blocks but are NOT maintaining a linked list of free nodes, sample6 will run slower (TIME greater than 1s).
  • (The speed of your system will impact the speed, but there will be a significant speed difference.)
    
    

Real Programs

Both mstats and mreplace can be used to launch “real” programs (not just the testers). For example:

# ignore the warning about an invalid terminal, if you get it
./mreplace /usr/bin/less alloc.c

or

./mstats /bin/ls

You can even run your version of MP2 using your malloc! For example:

./mstats ../mp2/png-extractGIF PATH_TO_PNG

Part 5: Advanced Testers

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

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. Earn credit for each of tester{1-5} that successfully run using ./mstats within 6 seconds.

Grading

The MP is worth a total of 80 points, and the points are split in the following way:

Week 1 Tasks:

• Implement a basic memory allocator, 20%
• Implement block splitting, 30% (see sample1)
• Implement memory coalescing, 30% (see sample{2,3,4})
• Implement free lists, 20% (see sample{5,6})

Week 2 Tasks:

• Pass tester{1-5}, 20% each

Submit

When you have completed your program, double-check all your functions run without errors and gets the result your expect. When you are ready, submit the code via the following git commands:

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

You can verify your code was successfully submitted by viewing your git repo on github.com