In this project, you will be implementing a memory allocator. You’ll be making your own versions of the malloc and free functions! Yay! Fun!

This project gives many people a lot of difficulty. Do not wait to start it.
Start early, and get help when you get stuck.

Grading Rubric

0. Starting off

  1. Make a new directory for this project in your VM.
  2. Here are the starting materials for you to wget and unzip.
  3. Do make testall to compile the program and run all the tests.

It should compile successfully; then it will try running the tests, and they will all segfault.

no compiling on a mac!

You can’t compile this project on your Mac.

There is no sbrk() or brk() on macOS.

Please do not ask questions about why you get linker errors or deprecation warnings.

This is because you’re trying to compile it on your Mac.

You can still write the code on your Mac, but you have to upload and test it in your VM.

Makefile targets

These are the targets available to use with make:

Using the driver program

The driver program just takes a number in the range 1 to 6, which is the number of the test to run. For example:

./driver 1

runs the first test (test_writing).

Since you will likely be running one test at a time, a useful command will be:

make && ./driver 1

The && in bash:

This way you can change your code, then run this line again, and it will compile and run the given test in one command.

The Break

When any process first starts running, its (virtual!) address space will look something like this:

A diagram of a process's address space showing the text and data segments at the low addresses, the "break" between them and the empty space, and the stack at the high addresses.

The “break” represents the “frontier” between the memory that your process does have access to, and the empty, unallocated space that it doesn’t have access to. (Accessing addresses in the large middle region would result in a segfault.)

We can ask the OS for more space dynamically by moving the break up. We can do this with the sbrk function.

When you call sbrk(n), it will move the break up by n bytes and return the old location of the break.

The code "void* p = sbrk(64);" The same diagram as before, but 64 bytes have been allocated, and the break has moved up. The allocated block is located where the break used to be.

Now, p points to a brand new block of 64 bytes. This new memory space is the heap! We can make the heap bigger by moving the break up, or make it smaller by moving the break down. However, we are entirely responsible for managing the memory within the heap. The OS won’t do it for us.

If you want to give heap memory back to the operating system, you do it by moving the break back down. We call this “contracting” the heap. There are two ways to contract the heap: either use the brk system call to set the break to a certain address, or use sbrk with a negative offset to move it backwards.

In this diagram, using brk(p) with the p pointer from the above diagram would set the break to where it started; and sbrk(-0x40) would do the exact same thing.

Either the code "brk(p);" or "sbrk(-64);" A diagram that looks just like the first one, with the break positioned at its original location.

Heap Blocks

Your heap will be divided into blocks. The blocks will be in a doubly-linked list. Each block can be either free (ready for reuse) or used (someone malloc‘ed it and is still using it).

A block has two parts: the header and the data. Each header contains the following information:

The Header struct in mymalloc.c represents the header of a block. However, the header struct does not contain the data part of a block. In memory, the header will be before the data part.

Your allocator does not care about the data part. That’s just for the user program to use!

The doubly-linked list

Note: these diagrams only show the tail, but you need to keep track of the head too.

When the program first starts and the heap is empty, your linked list will also be empty:

A diagram of an empty heap with the break at the beginning.

Here is a visual example of how the physical linked list might look with 6 blocks. Red blocks are allocated, and blue blocks are free. The arrows are the links between the blocks:

A diagram showing six blocks on the heap, linked together in a doubly-linked list in order.

Notice that the break is after the tail block. This will make it easy to know when to contract the heap: when you free a block, if it’s the tail (like this):

The same diagram as previous, except the last block (heap_tail) is now free.

Then you need to unlink it from the list (which will move heap_tail to the previous block), and then move the break down with either brk() or sbrk():

The previous diagram, but the break has moved down to where the last block used to begin, and heap_tail now points at what used to be the second-to-last block.

Block? Header? Data size? Block size? Nodes?

It’s important to keep terminology straight when working on this project, or you will very quickly get overwhelmed and confused by mixing up units.

First is a block, which is one piece of the heap. It has a header and some data.

It’s important to distinguish between the data size, which is what the user asks for when they call my_malloc, and the block size, which is that size plus the extra space needed for the header. As the allocator, it is your responsibility to make sure that you make enough space for the headers at the beginnings of blocks.

Each block is also a node in the doubly-linked list of the heap. That’s what the next and prev members of Header are for. “Node” is kind of an abstract term for “thing on a list.” It doesn’t really matter whether you think of the headers being the nodes, or the whole blocks being nodes. What matters is that the blocks are linked together.

Your Task

You will write my_malloc and my_free in mymalloc.c which implement a simple memory allocator using a linked list and a first-fit allocation scheme. The performance won’t be great, but hey, it’s a class project, not a AAA game engine.

Your my_malloc function will:

Your my_free function will:

1. First steps (./driver 1)

You are going to be building up my_malloc and my_free gradually. No one writes a program in a single try. Do NOT try to write the entire allocator without compiling, and then compile it and get a million errors and fix them and run it and it crashes and aaaaahhhh oh my godddddd

Look at the first test, test_writing, in driver.c. This test is extremely simple: it allocates two things, then frees them in the opposite order of allocating. Most of the tests use make_array to allocate memory, which allocates an array of ints using my_malloc and fills that array with values.

The tests also make generous use of my_dump(), a function I gave you in mymalloc.c which dumps the current state of the heap to stdout along with a message. This is your main way of telling if things are working.

If you completed lab 4 successfully, you will be able to reuse much of that code (with some modifications) for manipulating the doubly linked list pointed to by heap_head and heap_tail. If you weren’t able to complete lab 4, now is a great time to get help on it.

So here are the parts that you need to get working to get the first test to pass:

Done correctly, this is what test 1 should output:

-----------------------------------------------------------------------------
Running test_writing...

If this crashes, make sure my_malloc returns a pointer to
the data part of the block, NOT the header. my_free also 
has to handle that by moving the pointer backwards.
    should be empty:
        <empty>
    should have one used 40B block:
        [U 40]
    should have two used 40B blocks:
        [U 40][U 40]

Both arrays should contain the values 1 through 10:
a[0] = 1, b[0] = 1
a[1] = 2, b[1] = 2
a[2] = 3, b[2] = 3
a[3] = 4, b[3] = 4
a[4] = 5, b[4] = 5
a[5] = 6, b[5] = 6
a[6] = 7, b[6] = 7
a[7] = 8, b[7] = 8
a[8] = 9, b[8] = 9
a[9] = 10, b[9] = 10

    should have one used 40B block:
        [U 40]
    should be empty:
        <empty>

After test_writing, the break is back where it started!

2. Reusing blocks (./driver 2)

Right now, your allocator is pretty dumb. It doesn’t reuse free blocks. Instead, it moves the break up on every allocation. Let’s fix that.

Implement the part of my_malloc that tries to find a block to reuse, and only moves the break up if that failed. Seems like you should make a function that searches for a reusable block of the requested size, and returns NULL if it couldn’t find one!

As for implementing that function, first-fit is dead simple. All you have to do is iterate over the entire linked list starting at heap_head, and return the first block that is:

Note that C for loops fit with linked lists very well…

for(Header* n = heap_head; n != NULL; n = n->next) {

}

Once you get this implemented right, ./driver 2 will output this (look closely at what the messages say!):

-----------------------------------------------------------------------------
Running test_reuse...

    should have 2 used 80B blocks:
        [U 80][U 80]
    first 80B block should now be free:
        [F 80][U 80]
    first block should be used and STILL 80B, NOT 76!:
        [U 80][U 80]
    should have one free 80B and one used 80B:
        [F 80][U 80]
    should have two used 80B:
        [U 80][U 80]
    should have one used 80B:
        [U 80]
    should be empty:
        <empty>

After test_reuse, the break is back where it started!

3. Making sure first-fit really works (./driver 3)

Test 3 tests the first-fit algorithm a little more rigorously. There’s nothing more you should have to write for this, just run ./driver 3, and if everything is working, you should see:

-----------------------------------------------------------------------------
Running test_first_fit...

    should have 3 free blocks of increasing size separated by 16B used blocks:
        [F 40][U 16][F 80][U 16][F 120][U 16]
    the 120B block was correctly reused, so now it should be marked used:
        [F 40][U 16][F 80][U 16][U 120][U 16]
    the 40B block was correctly reused, so now it should be marked used:
        [U 40][U 16][F 80][U 16][U 120][U 16]
    the 80B block was correctly reused, so now it should be marked used:
        [U 40][U 16][U 80][U 16][U 120][U 16]
    should be empty:
        <empty>

After test_first_fit, the break is back where it started!

You’re halfway there. Assuming you have good code style, you have a 50%.

4. Splitting blocks (./driver 4)

Now we’re getting fancier. Your algorithm to find a reusable block just finds one that is big enough for the allocation, but sometimes that block is way too big for what the user asked for. Let’s say your heap looks like this:

A heap with a large free block in the middle.

but the user only wants a little block:

The previous diagram, but the first half of the empty block has been highlighted.

Now we have to split the original large block into two smaller blocks: one big enough to hold the requested block, and one smaller empty block, like so:

The previous diagram, but now the orange block has become its own block, and there are two links instead of one.

Undersized blocks

There is an additional complication: you can’t split every free block. Consider this case:

In that case, there wouldn’t be enough space for a new block, because the 32 bytes that the user wants and the 32 bytes for the new header leave 0 bytes of space after the new header!

Therefore, you need to do some calculations before splitting the block. Draw it out. Remember, you need space for the new header and a minimum number of bytes for the data. The MINIMUM_ALLOCATION and/or MIN_BLOCK_SIZE constants at the top of mymalloc.c will be useful here.

If you determine that splitting would leave an undersize block, don’t split, but also don’t change the size of the block in the header. Remember, you’re allowed to give the user more space than they asked for. If they asked for 56 and you give them 64, they won’t know the difference. This does cause a small amount of internal fragmentation though!

Notes:

Implemented correctly, ./driver 4 will output this:

-----------------------------------------------------------------------------
Running test_splitting...

    should have free 256B block at start:
        [F 256][U 16]
    first block should now be used and still 256B:
        [U 256][U 16]
    first block should be free again, and still 256B:
        [F 256][U 16]
    should have a free 208B block after first one:
        [U 16][F 208][U 16]
    should have a free 160B block after first two:
        [U 16][U 16][F 160][U 16]
    should have a free 112B block after first three:
        [U 16][U 16][U 16][F 112][U 16]
    should have a free 64B block after first four:
        [U 16][U 16][U 16][U 16][F 64][U 16]
    all blocks should be used (should have reused the 64B block):
        [U 16][U 16][U 16][U 16][U 64][U 16]
    should be empty:
        <empty>

After test_splitting, the break is back where it started!

5. Coalescing blocks (./driver 5)

When the user frees a block, you might end up with multiple free blocks in a row, like these three here:

A heap where there are three free blocks in a row.

This is a waste, because what if the user wanted an allocation the size of those three put together? Then our algorithm would skip them and move the break.

So there is a simple rule to follow: whenever you free a block, look at the previous and next blocks, and if either one or both are free, combine the free blocks into one larger free block.

Note: you don’t have to look further than one block away! If you follow this rule on every deallocation, it will be impossible to have e.g. 4 or 5 free blocks in a row.

Once coalesced, the three free blocks in the above diagram would become a single large block, like so:

The previous diagram, but the three consecutive free blocks have been coalesced into one.

Notes:

This is a big test. It has to test lots of possibilities. Read the output carefully if your test fails, to know approximately where to look in your code to solve the problem. Here is what it outputs on success:

-----------------------------------------------------------------------------
Running test_coalescing...

    should have 5 used 40B blocks:
        [U 40][U 40][U 40][U 40][U 40]

about to test freeing head of heap (no coalescing)
    freed the first block; should have one free 40B block:
        [F 40][U 40][U 40][U 40][U 40]

about to test coalescing with previous neighbor by freeing 2nd block
    freed the second block; should have one free 112B block:
        [F 112][U 40][U 40][U 40]
    freed the second block; should have one free 184B block:
        [F 184][U 40][U 40]
    freed the second block; should have one free 256B block:
        [F 256][U 40]
    reused that block, so should have two used blocks:
        [U 256][U 40]
    should have one used 256B block:
        [U 256]
    should be empty:
        <empty>
    reallocated stuff. should have 5 used blocks:
        [U 40][U 40][U 40][U 40][U 40]

neither of these frees will coalesce:
    second block should now be free:
        [U 40][F 40][U 40][U 40][U 40]
    fourth block should now be free:
        [U 40][F 40][U 40][F 40][U 40]

about to test coalescing with next neighbor by freeing 1st block
    first block should be free 112B:
        [F 112][U 40][F 40][U 40]

about to test coalescing with TWO neighbors by freeing 2nd block
    first block should be free 256B:
        [F 256][U 40]

about to free tail. it should coalesce, then move break down
    should be empty:
        <empty>
    last phase. should have 5 used blocks:
        [U 40][U 40][U 40][U 40][U 40]
    second block should be free:
        [U 40][F 40][U 40][U 40][U 40]
    should have one free 112B block at start:
        [F 112][U 40][U 40][U 40]
    third block should be free:
        [F 112][U 40][F 40][U 40]
    third and fourth blocks should be gone, should have 2 blocks:
        [F 112][U 40]
    should be empty:
        <empty>

After test_coalescing, the break is back where it started!

6. Is it stable? (./driver 6)

You’re probably done? But just to be sure, test 6 is THE BIG ONE. Well, it does a bunch of allocations and frees in an unpredictable fashion. But it should be a good stress test for your allocator.

It doesn’t output much. It takes about 10-15 seconds to run in my VM. If it’s running for a minute or more, your allocator might be stuck in a loop somehow. This is the output:

-----------------------------------------------------------------------------
Running THE BIG ONE...


After THE BIG ONE, the break is back where it started!

If it works, you’re done!

Submission

The autograder will open up about a week after the project is released. Just like on project 1, it will have a rate limit. However, the autograder is just going to run the same tests on your code that make testall does, so using the autograder isn’t going to give you more insight into the problems with your code than just running them yourself.

It’s an auto-grader, not an auto-TA. Get help from a human.