Final Project - A Dynamic Memory Allocator

CS 3410 Spring 2017

Lab 12 (5 malloc tests) Due: 11:59pm, Sunday, April 30, 2017

Project 6 (13 malloc tests) Due: 11:59pm, Saturday, May 6, 2017

Project 7 (MALLOC!) Due: 4:30pm, Monday, May 15, 2017 (no slip days allowed)

Reminder: You must work in a group of two for this final project. You should keep the same partner for all parts. This partner need not be the same partner as the earlier projects.

In this assignment, you will first read over the specs of a dynamic memory allocation library that supports the allocation, freeing, and resizing of blocks of memory. You will write a suite of tests that can be used to test an implementation of a dynamic memory allocation library and determine if it was implemented to specfications-correctly and robustly. You will need to put your problem-solving skills to work!

Then you will write your own implementation of a dynamic memory allocation library, that supports the allocation, freeing, and resizing of blocks of memory. Your implementation should be correct and robust, which you should be able to run your tests on. Lastly, we will be comparing your implementation of Malloc to your classmates' in a race for the best and fastest Malloc!

You can find the files for this project in your Github repository. Be sure to make good use of git features, such as branching, merging, stashing, and more!

What to submit

For Lab 12 and Project 6 upload ctests.c to CMS. An autograder will provde you with pre-deadline feedback.

For Project 7 complete and submit:

teamname.txt: 1-line file containing your Team Name, to be used to identify you on the Leaderboard. The team name can consist of alphanumerics only plus _ (underscore) or - (hyphen) but no other symbols. It cannot start or end with a symbol, and must have no more than 32 characters. Should your teamname not follow these rules, the 3410 TAs are more than happy to create a team name for you. Keep it clean, folks.
heaplib.c: your implementation of malloc!

The Specs

This section describes the specifications of the dynamic memory allocation library you will write for Project 7.

By now you should be familiar with static vs dynamic allocation. Statically allocated memory is allocated on the stack and exists only for the life of the function in which it was allocated; dynamically allocated memory is allocated on the heap and exists from the moment it is allocated until it is explicitly freed. Support for dynamic memory allocation is part of the Standard C Library.

A dynamic memory allocator maintains the memory associated with the heap. The most basic task will be to keep track of which bytes of the heap are currently in use (i.e., are allocated) and which bytes are not in use (i.e., free). On real systems, the heap can grow with the needs of a process. For this assignment, however, we will consider the heap to be a fixed-size block of memory. The functions you implement will take a void *heapptr argument that points to the beginning of the heap that you must manage. (Of course the heap here being pointed to by heapptr is a simulated version of the actual heap that the C Standard Library manages.) Your dynamic memory allocator will consist of the following four functions, which are declared in heaplib.h and will be implemented (by you) in heaplib.c.

`int hl_init(void *heapptr, unsigned int heap_size)`

Sets up a new heap beginning at heapptr and of size heap_size (in bytes). Note that your hl_init function does not actually need to allocate or create the heap. It is given a block of memory of the correct size, starting at the location pointed to by heapptr. (The test cases we provide will show you a few ways in which this block of memory can be created.) The hl_init function should be called once before there are any calls to hl_alloc, hl_release, or hl_resize.

Your memory allocator must live entirely inside the heap it is managing. This means that all meta-data (pointers, size fields, flags indicating free or in-use) must all live in the heap itself. You may not use any global arrays, variables, or structures. A good test of this is whether your implementation supports multiple heapptrs. Your code should naturally support multiple heaps.

Do not assume that heapptr is 8-byte aligned.

If heap_size is not large enough to hold the meta-data required to manage the heap (as you have designed it), setup fails, and the function returns 0. Returns non-zero if successful.

`void hl_alloc(void heapptr, unsigned int block_size)`

Allocates a block of memory of size block_size bytes from the heap pointed to by heapptr.

Returns a pointer to the block of memory on success; returns 0 (NULL) if the allocator cannot satisfy the request.

Blocks of memory can be of size 0. The returned address should be aligned at multiples of 8 bytes. The function is allowed to allocate more than the requested size, but never less. The memory "allocated" by this function does not need to be zeroed out.

`void hl_release(void heapptr, void blockptr)`

Frees the block of memory pointed to by blockptr (that currently resides in the heap pointed to by heapptr). If blockptr has the value 0 (NULL), the function should do nothing. (If it has some non-zero value that was never the return value of a call to hl_alloc or hl_resize, the program behavior is undefined. You need not fail gracefully.) For utilization purposes, released memory should be able to be allocated again by subsequent calls to hl_alloc.

The memory released by this function does not need to be zeroed out.

`void hl_resize(void heapptr, void *blockptr, unsigned int new_block_size)`

Changes the size of the memory block pointed to by blockptr (that currently resides in the heap pointed to by heapptr) from its current size to size new_block_size bytes, returning a pointer to the new block, or 0 if the request cannot be satisfied. the contents of the block should be preserved. If the location of the block changes (because it is not possible to make the block pointed to by blockptr larger and a new, larger block elsewhere needs to be used), you can copy the contents by using memcpy or cast blockptr to a char * and copy the contents byte by byte.

The new block size might be smaller than the current size of the block. As it was for hl_alloc, the return value should be 8-byte aligned. If blockptr has the value 0 (NULL), the function should behave like hl_alloc.

Note: Your functions hl_alloc(), hl_release(), and hl_resize() correspond to the actual C Standard Library functions malloc(), free(), and realloc(). Nowhere in heaplib.c should you call these three functions.

Compiling and Running Your Code

You have been given the following files as part of this assignment (the ones in bold are the files you will modify and submit):

heaplib.h -- contains the interfaces of the functions you are to test in Project 6 and implement in Project 7.
heaplib.c -- this is the file you will complete for Project 7, functions you are to test in Project 6 and implement in Project 7.
ctests.c -- a single test file with room for 13 tests. this is the file you submit for Project 6
test_correctness.c -- the code that calls your ctests
Makefile -- compiles 3 versions of 4 executables (see below)
heaplame.c -- a very bad implementation of a dynamic memory allocator. It has a few bugs, and you may fix them if you would like. See the heaplame section for a case study of how it works.

The Makefile you have been given will compile the executable: test_correctness. The heart of this assignment is your implementation of the functions declared in heaplib.h. You are implementing a library, which does not contain a main. The ctests.c file uses your library; with its own main in test_correctness.c. The test file is not complete (part of the assignment (Project 6) will be for you to complete it!), but it is a good start.

How you compile your code will determine whether your tests use the implementation of heaplib.h in heaplame.c or heaplib.c. Since you will spend much more time working with heaplib.c, this is the default. If you type make help you will see a slightly longer version of the following message:

Your custom heaplib.c implementation targets:
  make                   : heaplib.c
  make debug             : heaplib.c with debugging symbols
  make print-debug       : heaplib.c with debugging symbols and PRINT_DEBUG

The lame implementation targets:
  make lame             : heaplame.c
  make lame-debug       : heaplame.c with debugging symbols
  make lame-print-debug : heaplame.c with debugging symbols and PRINT_DEBUG
...

The first target (built by typing make or make lame produces "production level" versions of both executables. This is how we will compile your code when we test it.
The second target (built by typing make debug or make lame-debug) is an executable that contains all the symbols (variable and function names, line numbers, etc.) required to run your code in gdb.
The third target (built by typing make print-debug or make lame-print-debug) is an executable that has both debugging symbols and has defined the PRINT_DEBUG macro that will enable all the debugging print statements in your code.

Go ahead and peek at the Makefile. It doesn't bite and is fantastically documented. (Look, but don't touch!)

Case Study

Malloc strategy: the lame part

Heaplame - a lame, but helpful case study ...

We have provided you with a lame implementation of the assignment in heaplame.c.

It begins by defining a structure called block_header_t as follows:

typedef struct _block_header_t {
    unsigned int max_size;
    unsigned int curr_size;
    bool in_use_f;
} block_header_t ;

This implementation turns the entire heap into a single block that can be allocated just once. The beginning of the heap is reserved as a header to this block and maintains information about the block - there are three fields in this header. The first field holds the size of the heap. This field will be set by hl_init and never changed again. The second field indicates how many bytes the current block is sized to. The third field states whether the lone block is in use.

Let's step through this lame implementation of some of the functions. Figures 1 and 2 show the state of memory before and after a call to hl_init with a heap of size 32 beginning at address 0x100:

Figure 3 shows what a subsequent call to hl_alloc with a block size of 4 bytes would change the heap:

Figure 4 shows that the allocated block has been filled with data 'abcd'. Figure 5 shows how a call to resize would change the heap:

These diagrams are not intended to show you the correct behavior of the functions you should implement. Instead they show you an accurate depiction of what is currently implemented so that you may fully understand the code you have been given. Notice, for example, that the current implementation does not allow you to allocate the rest of the heap for new blocks. Furthermore, it doesn't even check if the requested block can even fit in the heap. This is a huge flaw in this approach from a utilization standpoint.

Known Correctness Bugs. In addition to being really unfriendly (allowing only one block to be allocated!), the lame solution in heaplame.c is incorrect in several respects:

no functions check for or report the failure case
no functions return pointers that are 8-byte aligned
heapptr is assumed to be 8-byte aligned

.... and possibly more???

Although the implementation is woefully inadequate as a solution to the assignment, it provides you important examples of heap management, casting, pointer arithmetic, and debugging.

Fixing the heap utilization problems (the orphaned memory resulting from hl_resize and hl_release) would require a significantly different approach than the lame implementation. You will be asked to come up with a completely new approach to a dynamic memory allocator--one that is robust enough to accomplish the task.

Coding strategy: the helpful part

Casting. Take a look at the implementations of hl_init and hl_alloc. Notice that casting the heapptr to a block_header_t * is a straight forward and very readable way to set and access the fields of the otherwise unspecified heap. (Aside: Casting can be a very helpful way to peek at memory. Want to know whether a machine is little or big endian? Write a number into an integer, create a pointer to the integer, cast the pointer to a char * and dereference it. Now you're looking at the byte of the integer in memory at the lowest address!)
Debug-only print statements. Notice the print_block_header function. Although this function may be incredibly useful to a programmer when implementing and debugging, this is not the kind of information that should be printed to the screen when some program includes and makes calls to your heaplib.c library. Novice programmers notoriously litter their code with print statements that are commented in and out as they code. This is not good form, especially since some straggling printf's almost always remain in the final version of the code. This is particularly devastating when performance matters (which it does for this assignment).

One solution to this problem is to create a variable such as debug_mode_f (_f often indicates a flag in C) and put the print statement inside an if statement that checks the variable:

if (print_debug_f) {
    print_heap(heap);
}

This solution has the nice property that (if tied to a command line option) the flag can be turned off and on each time you run the program. The problem with this approach is that even your "production-level" code will be littered with if statements that always evaluate to false.

The code you have been given solves the problem by placing the print statement as the controlled text in a conditional group:

#ifdef PRINT_DEBUG
    print_heap(heap);
#endif

The preprocessor (part of the compiler) will only insert the controlled text if the PRINT_DEBUG has been defined/set.
This Macro approach requires re-compiling in order to insert the print statements. This may not be the best strategy for every scenario, but it is for this assignment. Do not use any print statements inside your heaplib.c that are not wrapped in an #ifdef flag. Compiling and Running Your Code discussed how to turn the flag on and off at compile time.

Pointer arithmetic. To implement this assignment, you will want to use pointer arithmetic. As a basic example, see the following snippet of code:

// warning: this code is buggy
int hl_init(void *heapptr, unsigned int heap_size) {
    block_header_t *heap = (block_header_t *)heapptr;
    heap->next_free = heap + sizeof(block_header_t);
    ...

This code initializes the next_free pointer to point to the first free byte, which lives past the header. A careful programmer will not assume to know the size of all types on any machine that their code might run on. (There might not even be one right answer!) Instead, we use sizeof. The code above, however, is still flawed. Because heap is of type block_header_t *, adding some number to it, say 16, will move the pointer forward "16 block_header_ts worth" (in other words, 16 x sizeof(block_header_t)). Two correct versions would be:

heap->next_free = heap + 1;

(move ahead 1 block_header_t worth) or

heap->next_free = (char *)heap + sizeof(block_header_t);

(temporarily cast heap to be a char * so that adding 16 just adds 16 chars to the address.)

If you did not understand the problem in the above paragraph or why both solutions work, you are not ready to begin this assignment! Go brush up on your pointer arithmetic.

Using Macros. Given the amount of pointer arithmetic required for this assignment, you may find your code littered with many small but hard-to-read lines of code that are performing essentially the same task repeatedly. For example, you may find that you frequently add some number of bytes to an address that needs to be cast to a char *. For readability, you may be tempted to create short helper functions for these tasks. Knowing what you now know about the overhead of a function call and knowing that your code will be tested for speed, you should instead use macros. A macro is a <keyword, definition> pair. Any reference to the keyword will be replaced by the definition at compile time. You may be familiar with simple macros such as:

#define ALIGNMENT 8

which is a great way to rid your code of magic numbers. Macros can also be more complex, taking arguments. For example:

/* Useful shorthand: casts a pointer to a (char *) before adding */
#define ADD_BYTES(base_addr, num_bytes) (((char *)(base_addr)) + (num_bytes))

We recommend using macros for any complicated but simple tasks; your code will be much more readable, maintainable, and debuggable at no performance cost.

Using sizeof. Notice that nowhere in this code are the sizes of types assumed to be known. Different types are of different sizes in different environments. We will test your code on the course VM. Even still, your library code should have no "magic numbers" that make assumptions about sizes, even if they are correct on the course VM. One solution is to call sizeof() throughout your program. uintptr_t in <stdint.h> is guaranteed to contain the size of pointer on the machine where the executable is running. You may find this useful.
Ternary Operators. You will also notice that a ternary operator is used in the print_block_header function of heaplame. This is very useful as it allows you to have a conditional output without explicitly writing an if statement.

block->in_use_f ? "Yes" : "No"

The value before the ? is a boolean expression, and if true, evaluates to "Yes", otherwise it evaluates to "No".

Note that the ternary operator has very low precedence, so be sure to wrap your ternary operator usage in parentheses! i.e.

(x ? 1 : 2)

instead of

x ? 1 : 2

Student implementations of dynamic memory allocators are notoriously ugly and impossible to debug. Yours should not be. First, because you will make your own life a living hell. Second, because we will deduct style points for anything egregious. We have given you sample code with all sorts of tricks in it because these are tricks that expert programmers know about and use regularly. Now that you have been shown these techniques, you will be expected to use them.

Cost of a ridiculously long project writeup? 15 minutes. Shedding your status as a novice and being able to produce code that is readable, debuggable, and super fast? Priceless.

Project 6: Tests for Correctness

Testing is a huge part of writing good code and will be a significant part of your grade for this assignment.

You will begin writing a series of tests that check to see whether an implementation of this dynamic memory allocation library was done correctly. We have prepared approximately 13 broken malloc implementations that do not meet the specs in some way. Your task is to write tests that accurately flag these broken versions as broken while at the same time accurately flagging a correct implementation as correct.

For lab 12, you will only need to write the first 5 of these tests, located in ctests.c. (Feel free to add additional tests). The rest of the tests will be implemented in Project 6.
For lab 12 only, you will have unlimited runs of the autograder, so that you can become familiar with how this system will work.

ctests.c is intended to be a thorough test for the correctness of any heaplib implementation. At the moment, however, it only tests three things:

whether hl_init works
whether hl_alloc fails when there is not enough space
whether the pointer returned by hl_alloc is 8 byte aligned

There are many more possible correctness problems. Modify ctests.c to catch all of them. Feel free to correct the errors in heaplame.c as a sanity check for your tests. (The fixed code will be helpful for your heaplib.c.)

The goal is to convince yourself that your code is correct. Try to come up with a number of cases that really stress your allocation functions. It's a good idea to test corner cases as well. For example, create a test that uses two different heapptr pointers to two different chunks of memory. Make sure that a user is never given permission to write past the end of the heapptr associated with any allocation request. (Note: a user could always write past the heapptr, but if a user requests 32 bytes and is given a pointer to the very last byte in the heapptr, this is a correctness problem. Similarly, a user should never be given permission to write into memory that was already reserved (and not freed) in a previous call to hl_alloc. Think about how you might test whether data in a block is preserved over time.

You should maintain the structure of the program output:

A 1-line description of each test, ending in whether the test passes or fails when you run ./test_correctness [test #] . This description should be put at the top of your ctests.c file.

If you wish to add additional print statements, please use the PRINT_DEBUG macro. We will be writing scripts to look for the output of ./test_correctness to make sure that you catch bugs in the broken mallocs.

When you have completed ctests.c it should report all the correctness problems with heaplame.c. You will submit this file to CMS. Each submission will trigger an automatic autograder run and you will receive an email with the result of your tests running on our broken versions of malloc. This test will be graded on how thoroughly it tests the correctness of yours and our broken implementations of heaplame.c and heaplib.c. Points will be deducted for false positives (finding errors where there are none) and false negatives (not finding errors when they are there).

You will have 3 autograder runs per day for Project 6.

What is correctness? For the purposes of this assignment, any error that would occur even in an infinite heap is considered a correctness error. For example, not guaranteeing pointer alignment is a correctness error. Not implementing hl_release will be considered a utilization error, not a correctness error.

What constitutes as flagging as broken? You can either return FAILURE from your test function, or you can have the code SEGFAULT. The second option may seem unintuitive at first, but it is helpful to realize that if an implementation of malloc is indeed broken, it will have bad behavior such as SEGFAULT.

Note that your tests should not flag a working malloc as broken.

A thorough correctness test will not only earn you points and glory, but it will be invaluable in finishing subsequent tasks for this assignment.

Project 7: Designing Your Own Memory Allocation Library

Now it's time for you to implement your own dynamic memory allocation library that supports the allocation, freeing, and resizing of blocks of memory. Your code must follow both the interface and the functional specifications which were outlined above.

In all other ways, however, you should be creative: design your own data structures; put your problem-solving skills to work! You are free to implement existing/known approaches to solving this problem or come up with your own original ideas. As you consider your options, you should under no circumstances look at others' code (including code on the internet) or show your code to anyone outside of your group of two.

Your implementation will be graded based on correctness first. Correct implmentations of heaplib.c will then be evaluated on both memory utilization and throughput. (Incorrect implementations will not be tested for utilization and throughput--and will forgo the points associated with these tests--because these metrics are meaningless in the context of an incorrect program. (Example: if you implemented hl_alloc by simply returning NULL your performance would be great, but what good would it do?)

Utilization. When a heap is initialized, it is given a fixed memory area that it can use to fulfill allocation requests. (Note: the actual heap on a real system can grow as needed within the virtual address space of the process. The fixed-sized heap in this assignment is an artificial but simplifying restriction.)

Overhead: the first aspect of heap utilization relates to how much meta data your implementation requires. Meta-data is the information about the payload, the size of each block, whether it is free, etc. etc. Less meta data allows you to dedicate more of the heap to service alloc requests. However, you may find that more meta data will support better and/or faster heap management (more careful allocation, free, and resizing strategies).
Management: the second aspect of heap utilization relates to the management of the heap itself. Careful implementations of alloc, resize, and free will keep your heap less fragmented and more able to fulfill future allocation and resize requests. However, you may find that careful heap management may mean slower response times to calls to your heap library.

Throughput. Another important aspect of your design will be how quickly your library completes the jobs associated with allocating, freeing, and resizing memory. Different approaches may improve throughput but either require meta-data that might increase overhead or fragment the heap. You will have to consider these tradeoffs when designing your approach knowing that both metrics will part of your grade.

You will have a lot of design choices to make that create a tradeoff between heap utilization and throughput. Here are just a few:

Implicit vs. Explicit Lists. One design choice you will have is whether the list of free and allocated blocks that you maintain is an implicit list or an explicit list. In an implicit list, the size field is enough to help you find the next block. All blocks (both free and allocated) will be in the same list. In an explicit list, pointers determine which block comes next. Now you can have the blocks in any order. This strategy support multiple lists, doubly linked lists, ordered lists, and even trees.

Allocation Strategies. Think about the pros and cons of some common allocation strategies. A first-fit approach always gives the user the first memory block in the region that is big enough to fulfill the request. This provides the fastest response time, but is not necessarily the most space-efficient use of your memory region. A best-fit approach gives the user the smallest memory block that fulfills the request. The allocator will not be as quick because it might search the entire list to find this smallest block, but this is a more efficient use of space. You might be able to speed up this search by maintaining pointers to free memory blocks of certain sizes. You will have to decide whether these efficiency techniques are worth the space overhead that they require.
Fragmentation. After responding to many calls to hl_alloc and hl_release the heap could become chopped up into small interwoven blocks of allocated and freed memory. When your memory region becomes fragmented, the sum of the free blocks of memory might satisfy an hl_alloc request, but since they are not contiguous, the request will fail. Whether you implement a first-fit or best-fit allocation strategy is just one way in which you control the fragmentation of your memory region. You should also think about how your implementations of hl_release and hl_resize play a role in your ability to avoid fragmentation and satisfy future allocation requests.

Implementing Your Memory Allocation Library

With all of the information above and any research you care to do on your own (that does not involved looking at code), come up with a heap management strategy and implement it in heaplib.c. Remember that you are not allowed to change the interface to any of the library functions. Any changes you make to heaplib.h will be ignored when we grade your code. (CMS will not even accept heaplib.h as part of your submission.) Remember that correctness is your first priority.

As you implement your ideas, you should regularly run ./test_correctness to catch any correctness problems. Catching bugs as they appear is much easier than catching them all at once at the end! You may want to add more test cases to your ctests.c file. Remember to test not only the specs of the assignment but also any invariants of your specific approach. For example, if you implement a balanced tree, you might want to add a test in ctests.c that checks to see whether your tree remains balanced at all times.

The Leaderboard

The autograder will run your code 5 times per day for Project 7.

We will run your code and test it for correctness. Code that passes our correctness tests will then be tested for overhead, maintainence, and performance. At some point during the following week we will set up a leaderboard that shows how your code fares on these three tests compared to other groups in the class. We don't actually expect one group to be at the top of all three lists. Instead, we hope you will be able to see from this exercise that design choices are full of tradeoffs, often sacrificing one metric for another.

The leaderboard can be found here: Leaderboard

Tips

Although technically Lab 12 and Project 6 are due before Project 7, you should probably work through the tests in order, completing the test and fixing heaplib.c back and forth. You will benefit immensely if you allow your implementation to inform your testing and vice versa.
Continuously implement the very smallest, testable unit of work possible and then immediately test it for correctness. (Here, your testing helps your implementation.) If no such test exists, write one. (Here, your implementation helps your testing.)
You may find gdb, the GNU debugger, helpful while completing this assignment. (Tutorials can be found on unknown road). At the very least, the make print-debug option will give you some insight.
This assignment has a lot of programs and a lot of targets. If something strange is happening, you might be making or executing the wrong thing. For example, if you make a change to your heaplame.c and then type make and then ./test_correctness it may look as though your change did nothing. In fact, you should have typed make lame and the change in your code was simply not incorporated into your executable. This is just one example of the ways in which you may occasionally confuse yourself. Take a step back and ask yourself "What am I compiling? What am I running?"

Grading

Lab 12 will be graded on catching all 5 broken mallocs using the first 5 test cases.

Project 6 will be graded on catching all 13 broken mallocs using your 13 test cases.

Project 7 will be graded first on the correctness of your malloc implementation. Afterwards, you will receive points based on how well your implementation utilizes the given heap and the speed at which it is able to handle requests.

A rough breakdown of your grade is as follows:

60%: Correctness
25%: Utilization
15%: Speed

Note that you will not receive points for utilization and speed if your implementation does not pass the correctness tests!

Acknowledgements

This assignment is the literal descendant of an assignment originally written by Robbert Van Renesse at Cornell. It is the spiritual descendant of the textbook "Computer Systems: A Programmer's Perspective" by Bryant and O'Hallaron, which your instructor thinks is a fantastic book.