Overview

Your third MP in CS 240 is writing your own memory allocator! You should 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.

Initial Files

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

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

Note for Mac OS X Users

For this MP only and for OS X users only, you will need to program on a Linux system due to the differences in how Linux and OS X handles process/memory injection and the sbrk() library call. The linux.ews.illinois.edu server is available for you to remotely connect to to work on a Linux environment to run the MP. (These machine are already set up and ready to go!)

• If you are comfortable with the terminal, you can use ssh to access linux.ews.illinois.edu.
• If you want a graphical desktop, EngrIT has details on going FastX to connect on their FastX guide here

Machine Problem

Writing malloc

Using sbrk, write your malloc implementation! Your malloc should allocate a block of size bytes of memory, returning a pointer to the beginning of the block. The contents of the newly allocated block of memory are not initialized.

Writing free

Write your implementation of free! This function will take a pointer to a block of previously allocated memory and make it available again for future allocations.

Writing calloc

Write your implementation of calloc! This function will take in two parameters, num and size. It will allocate a block of memory for an array of num elements, each of them being size bytes long, and initialize all of its bits to zero.

Writing realloc

Write your implementation of realloc! This function will take in two parameters: a pointer to a previously allocated block of memory, and the desired size of the returned memory. You must return a pointer to a block of allocated memory of at least size, with this block of memory containing the same contents as the passed in pointer.

Getting Started Guide

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

Testing Your Code

In order to run your solution on the testers, run ./mstats with the tester you want. You must do this, or your code will be run with the glibc implementation!

Example:

./mstats testers_exe/tester-1
Memory failed to allocate!
[mstats]: STATUS: FAILED=(256)
[mstats]: MAX: 0
[mstats]: AVG: 0.000000
[mstats]: TIME: 0.000000

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

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

We have also provided you with a tester python file called dice_roll.py. You can run it with your implementation of malloc with these commands:

./mstats python ./testers_exe/dice_roll.py

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

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

Grading

We have included mstats-libc that tracks the memory usage of the system-included libc library – lots of people have worked on this library, so it’s quite efficient and something that would be a challenge to do better than in all three metrics.

Before Week 2 of this MP, we will release “performance thresholds” relative to mstats-libc. If you implement a few heap management strategies, you will earn all 50 points; you can earn extra credit for making a particularly efficient or speedy alloc! More details soon! :)

Submit

When you have completed your program, double-check all four 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 origin master

You can verify your code was successfully submitted by viewing your git repo via the web interface here: https://github-dev.cs.illinois.edu/cs240-fa20