Group Project 4 - A Dynamic Memory Allocator

CS3410 Spring 2016


Due: 4:30pm, Tuesday, May 17


Reminder: you must work in a group of two for this project. You don't need to have the same partner as the earlier projects.

In this assignment, you will implement a dynamic memory allocation library that supports the allocation, freeing, and resizing of blocks of memory. Your code must follow both the given interface and the functional specifications of the assignment. 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.

   Assignment Navigation:

Introduction

By now you are 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. For this assignment, however, you will write your own versions of these functions.

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 defined (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. (When it comes time for you to test your code, 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 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, 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 utlization 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, 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): The Makefile you have been given will compile four executables: heaptest, test_c, test_u, and test_t. 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 four test files use your library; each has its own main. None of the test files are complete (part of the assignment will be for you to complete them!), but they are a good start.

How you compile your code will determine whether your tests use the implementation of heaplib.h in heaplib_naive.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 prof              : heaplib.c with profiling symbols
  make debug             : heaplib.c with debugging symbols
  make print-debug       : heaplib.c with debugging symbols and PRINT_DEBUG

The naive implementation targets:
  make naive             : heaplib_naive.c
  make naive-prof        : heaplib_naive.c with profiling symbols
  make naive-debug       : heaplib_naive.c with debugging symbols
  make naive-print-debug : heaplib_naive.c with debugging symbols and PRINT_DEBUG
  <snip>

The first target (built by typing make or make naive produces "production level" versions of all four executables. This is how we will compile your code when we test it.

The second target will be discussed later under "Optimizing Your Code".

The third target (built by typing make debug or make naive-debug) is an executable that contains all the symbols (variable and function names, line numbers, etc.) required to run your code in gdb.

The fourth target (built by typing make print-debug or make naive-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!)

Naive (but helpful) Case Study

We have provided you with a naive implementation of the assignment in heaplib_naive.c.

   Malloc strategy: the naive part

It begins by defining a structure called heap_header_t as follows:
typedef struct heap_header_t {
  unsigned int size;
  int bytes_free;
  char *next_free;
} heap_header_t ;
This strategy dedicates the beginning of the heap to maintain information about the heap; 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 there are left in the heap. This field will be useful when trying to determine whether a particular hl_alloc call can be successfully serviced. The third field is a handy shortcut that keeps track of the next unused byte in the heap. Notice that this field is not strictly necessary, since it would be possible to calculate the location of this byte, given the starting address of the heap and the number of free bytes remaining. But hey, it's naive, right?

Let's step through this naive 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 support the reuse of a resized block. This is a huge flaw in this approach from a utilization standpoint. Similarly, hl_release does nothing, meaning that released memory cannot be allocated again by subsequent calls to hl_alloc.

Known Correctness Bugs. In addition to being a terribly inefficient use of space, the naive solution in heaplib_naive.c is incorrect in several respects:

  1. no functions check for or report the failure case
  2. no functions return pointers that are 8-byte aligned
  3. heapptr is assumed to be 8-byte aligned.
  4. hl_reszie does not copy the values from the original block to the new block
.... and possibly more.

   Coding strategy: the helpful part

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

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.

Task #1: Test for Correctness

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

test_c.c is intended to be a thorough test for the correctness of any heaplib implementation. At the moment, however, it only tests two things: whether hl_resize actually copies the data from the original block of memory to the resized block of memory and whether the pointer returned by hl_alloc is 8 byte aligned. There are many more correctness problems in heaplib_naive.c. Modify test_c.c to catch all of them.

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 heap pointers to two different chunks of memory. Make sure that a user is never given permission to write past the heap associated with any allocation request. (Note: a user could always write past the heap, but if a user requests 32 bytes and is given a pointer to the very last byte in the heap, 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:

If you wish to add additional print statements, please use the print-debug macro. Do not change the format of the given print statements. We will be writing scripts that look for these exact lines when we run your tests. (For example, we will grep for "Pass_Rate".)

When you have completed test_c.c it should report all the correctness problems with heaplib_naive.c. You will submit this file to CMS. This test will be graded on how thoroughly it tests the correctness of yours and your fellow students' implementations of heaplib_naive.c. Points will be deducted for false positives (finding errors where there are none) and false negatives (not finding errors when they are there).

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.

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

Task #2: Fix heaplib_naive.c

Fix problems 1, 2, 3, and 4 listed above and any other correctness problems which you are now able to detect by running test_c. Do not change the definition of heap_header_t. Do not create any new typedefs. Once your fix is working, submit it on CMS.

Fixing the heap utilization problems (the orphaned memory resulting from hl_resize and hl_release) would require a significantly different approach than the naive implementation. You will not be asked to fix this problem. Instead, 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.

We will try to give you early feedback about Task #1 and Task #2 sometime after Prelim 2. You will be allowed to re-submit these files based on this feedback. Exact dates and times to be announced later.

Designing Your Own Memory Allocation Library

Once you have completed Task #1 and Task #2 you are ready to begin the heart of this assignment. Think about the ways in which the naive implementation was deficient. This is your chance to come up with a better strategy to manage your heap.

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. By the metrics we will introduce, the original (incorrect) version of heaplib_naive.c has fantastic utilization and throughput!)

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.) Some of this area will be used up by meta-data: information about the memory area, the size of each block, whether it is free, etc. etc. The standard approach to heap management (which our naive implementation did not do!) is to give each block its own header, indicating its size and whether it is free or allocated. This would support freeing a previously allocated block. (Notice the tradeoff: each block requires meta-data, but for this, you gain the ability to reuse free blocks...)

On the one hand, you want to minimize meta-data. On the other hand, some of this meta data will support a more careful heap management (careful allocation, free, and resize strategies). Ultimately, we will judge your utilization via "size tasks" (which measure how large a heap is required to fulfill a series of calls to heaplib). You will be asked to write one such "size task" for Task #4.

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 require meta-data that might reduce utilization. You will have to consider these tradeoffs when designing your approach knowing that both metrics will part of your grade. We will judge your throughput via "speed tasks" (which measure the execution time of a series of calls to heaplib). You will be asked to write one such "speed task" for Task #5.

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.

Task #3: 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_c to catch any correctness problems. Catching bugs as they appear is much easier than catching them all at once at the end! You may discover that you need to add more test cases to your test_c.c file. Remember to test the specs of the assignment and not the invariants of your specific approach. For example, if you implement a balanced tree, you might be tempted to add a test in test_c.c that checks to see whether your tree remains balanced at all times. A test like this should be in an implementation-specific heap consistency checker, not a "did you follow the specs of the library" correctness test. You are encouraged but not required to create a consistency checker and you could easily add something like this to the general-purpose heaptest.c which you have been given.

Task #4: Test for Utilization

The file test_u.c tests your code for utilization by determining approximately how much memory a heaplib implementation requires in order to complete a particular task. A well-managed heap will require less memory than a poorly managed heap.

You will be asked to create a "size task" that is the body of the function pass_sizetask() in sizetask.c. You will define a task whose space requirements will set different heap implementations apart from others: a badly-utilized heap would require significantly more space than than a well-utilized heap. The best test would produce a wide spectrum of heap requirements. If every implementation requires the same amount of space, your test will not be an effective measure of heap utilization. You may want to try to judge space management at both a meta-data level and a block-handling level. The choice is yours, however. (The given function, for example, might highlight differences in size of headers, but it doesn't address whether freed blocks can be coalesced, reused, etc.). It is up to you to determine what you think a good test of utilization will be.

Note: you may have arbitrary numbers in this task, but you should still avoid "magic numbers". Notice that the code currently in pass_sizetask() (which you should replace with your own test) does several things 64 times. Some of those 64's are independent (ITERS vs. REQ_SIZE), and some are "linked" (multiple uses of ITERS). If instead of using the #define ITERS, we had just used the number 64 in multiple places, changing one of those 64s would break the code. Well-written code supports bug-free updates.

Task #5: Test for Throughput

The file test_t.c tests your code for throughput by performing a series of calls to allocate, resize, and free memory blocks. A well-written library will be able to service these requests quickly, although the absolute fastest library likely compromises memory utilization.

You will be asked to create a "speed task" that is the body of the function standalone_speedtask() in speedtask.c. You will define a task whose approximate space requirements are known up front and available (to the caller who must first set up the heap for the task) via the function get_heap_size(). Since you won't know the meta-data requirements of each library that will be tested with this "speed task", the heap estimate should be on the generous side.

The program test_t will set up a block of memory for the speed task, start a timer, and then call standalone_speedtask() with a pointer to that block of memory. When the speed task is finished test_t stops the timer. It will then compute a throughput of operations per clock. You must complete the function get_num_ops() with the correct number of operations that your speed task requires. The calculation will not make a distinction between the operations (alloc, release, or resize), so it's a good idea to use a large number of all three since some library implementations may have quite unbalanced runtimes between these three functions. It would also be appropriate to run the speed test multiple times and take an average, although the program test_t which you are given does not. A good test will produce a large spectrum of runtimes across various library implementations. The more informative your test is when running it on everyone's code, the more points you will receive. It is up to you to determine what you think a good test of throughput would be. Note: At a minimum, your test should run long enough that gprof is able to produce meaningful timing results (see Task #6 ). Your test must be less than 5 seconds in length or we will not be able to run it as part of our Leaderboard creation.

Task #6: Optimize Your Code

Do not begin this task until you have completed Task #3 and Task #5.

Hopefully your dynamic memory allocation library was written with careful attention to speed. This task will allow you to profile your code and potentially improve your throughput score by finding out exactly where your code spends most of its time. For this task, you will make a version of your executable that has been modified to support profiling. You will use a program called gprof which will repeatedly interrupt the execution of your executable and make a note of which function the executable is currently in. With enough samples, it will report to you the amount of time your executable is spending in each of its functions.

Note: In Task #7 you will be asked to report on this task and how you improved the performance of your code in response to profiling it. The way to prove that your code got faster based on your profiling and code optimization efforts is to show before and after test_t results. So the process is as follows:

  1. Run test_t and keep a copy of the results.
  2. Make the profiling-enabled versions of your executable:
    make prof
    
  3. Now you can profile any of your four executables, though for obvious reasons, we recommend that you use test_t:
    ./test_t
    
    This will run the executable and generate the file gmon.out. Now run gprof:
    gprof test_t
    
    to see where you code is spending its time. Note: if your speed task is not long enough, gprof will not be able to gather timing information. At the top of the output you will see "no accumulated time". Go make your speed task longer and try again. (Remember to rerun test_t (Step 1) if you change it.
  4. Now that you see where your code is spending most of its time, try to optimize it in some way. Your optimization could be related to your heap management. It could also be code optimization that has more to do with C or your new-found knowledge of processors and performance bottlenecks. Remember to continue to compile with optimizations set to -O0. Turning on compiler optimizations does not count!
  5. Run test_t (not compiled for profiling!) again. You now have a "before" and "after" version to report on in the next step.

This is an exercise to show that you know how to both profile your code and measure the effects of your improvements. Full credit will be given to anyone who successfully follows these steps even if you are unable to make a remarkable leap in performance. We don't want your arbitrarily making your slow up front, and we know you can't always squeeze blood from a stone.

Task #7: Presenting Your Results

You will upload a pdf to CMS with the following components:

The Leaderboard

We will run your code and correctness tests on our autograders at regular intervals to be announced in the coming weeks. At some point during the following weeks we will also set up a webpage that shows how your code fares across the size and speed tasks of the other groups in the class. It will also indicate how well your tests are faring when used to assess the library implementations of other groups in the class.

Tips

Grading

Coming soon!

What to submit

Due: 4:30pm, Tuesday, May 17

Complete and submit the following 7 files to CMS:

Grading

Coming soon!

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.