Final Project - A Dynamic Memory Allocator

CS 3410 Spring 2019

Schedule Design Doc Meeting by: Sunday, May 5, 2019

Design Doc Meetings: May 6-7, 2019

Deadline: 4:30pm, Thursday, May 16, 2019

There are no slip days or grace period for this deadline. Note the 4:30pm university set due date, not midnight.

In this assignment, you will implement a dynamic memory allocation library (aka malloc) that supports the allocation, freeing, and resizing of blocks of memory. Your implementation will be assessed based on its correctness, its utilization of the memory it manages, its performance speed, and how well you test it. Lastly, we will be comparing your implementation of malloc to your classmates' in a competition for the best malloc!

You can find the files for this project in your Github repository. You may find these git tips useful.

What to submit:

  • alias.txt: 1-line file containing your Leaderboard Alias, to be used to identify you on the Leaderboard. The alias 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 alias not follow these rules, the 3410 TAs are more than happy to create a great name for you. Remember to keep it clean, folks.
  • heaplib.c: your implementation of malloc!
  • spinlock.c: your implementation of a spin lock in RISCV!


By now you should be familiar with static vs dynamic allocation. Statically declared memory is allocated on the stack and exists only for the life of the function in which it was created; 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. Your dynamic memory allocator will always be associated with a void *heap that points to the beginning of the heap that you must manage. (The heap pointed to by heap is a simulated version of the actual heap that the C Standard Library manages.)

A dynamic memory allocator is a bit like an actual library (with books). When someone asks for 512 bytes of memory, the allocator finds 512 free contiguous bytes of memory for the caller and returns the address of the first of these 512 bytes. These 512 bytes are now "checked out" and cannot be given out by any subsequent requests until they are explicitly freed. The bytes are freed when the user explicitly tells the allocator it no longer needs the bytes beginning at that address.

For this assignment, it will be important to understand not only what it means to correctly implement a dynamic memory allocator, but also what it means to correctly use a dynamic memory allocator. If at any point your code segfaults, you must know whether the fault lies in the library or the user of the library. For example, a user should never write past the fixed-size heap. If they do, the problem could be that the user has written past the chunk of memory they were given (this would be the fault of the user), or it could be that the memory allocator gave the user a block of memory which did not actually reside entirely inside the heap (this would be the fault of the allocator). To help you learn this distinction, we begin by having you write tests that should correctly use the dynamic memory allocator. (You started this in lab 12; you will be extending it in this project.) Then, if any of the tests experience an error, you will know the fault lies in the implementation. Once you have a test suite that you can trust, you can use it to test your own implementation.

Remember the best way to implement a large task is to break it up into very small, testable subtasks. Code a little, test a lot. Code a little, test a lot... and so forth.

Malloc Implementation Specs

Your dynamic memory allocator will consist of four functions, which are declared in heaplib.h and will be implemented (by you) in heaplib.c. The functions hl_alloc(), hl_release(), and hl_resize() correspond to the actual C Standard Library functions malloc(), free(), and realloc(). You should use your understanding of these functions to guide your implementation, but nowhere in your submission should you call these three functions.

int hl_init(void *heap, unsigned int heap_size)

Sets up a new heap beginning at heap of size heap_size (in bytes). Returns 1 if setup was successful and 0 otherwise. This function does not allocate the heap (of size heap_size) pointed to by heap. That should be done already by the user calling this function.

  1. the allocated heap must be heap_size in bytes
  2. heap_size must be >= MIN_HEAP_SIZE (here, 1024)
If precondition (1) is violated, non-graceful failure is acceptable. hl_init must gracefully fail with the correct return value if precondition (2) is violated.

See the given tests in the tests.c file for what it means to allocate the heap before calling hl_init.

This hl_init function should be called exactly once for each heap being managed.

Your memory allocator must live entirely inside the heap it is managing. 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 variables or structures. Every variable or structure must live inside either the heap or in the local function being executed. Your design should work for any heap size that is at least 1024 bytes in size.

void *hl_alloc(void *heap, unsigned int block_size)

Allocates a block of memory of size block_size bytes from the heap starting at heap.

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

  1. hl_init must have been called exactly once for this heap
If preconditions are violated, non-graceful failure is acceptable.

The returned address should be aligned at multiples of 8 bytes, but heap is not required to be 8-byte aligned. 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. Requested blocks of memory can be of size 0.

void hl_release(void *heap, void *block)

Releases the block of memory pointed to by block (which currently resides in the heap pointed to by heap). Acts as a NOP if block == 0 (NULL).

  1. block must have been returned to the user from a prior call to hl_alloc or hl_resize
  2. hl_release can only be called ONCE in association with that prior call to hl_alloc or hl_resize
If preconditions are violated, non-graceful failure is acceptable.

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 *heap, void *block, unsigned int new_size)

Changes the size of the block pointed to by block (that currently resides in the heap pointed to by heap) from its current size to size new_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 (even if the location of the block changes -- this will happen when it is not possible to increase the size of the current block but there is room elsewhere on the heap to satisfy the request). If block has the value 0 (NULL), the function should behave like hl_alloc.

  1. block must have been returned to the user from a prior call to hl_alloc or hl_resize
If preconditions are violated, non-graceful failure is acceptable.

Note: The new block size might be smaller than the current size of the block. As for hl_alloc, the return value should be 8-byte aligned. You can copy the contents of a chunk in memory by using memmove or cast block to a char * and copy the contents byte by byte.

Spinlock Specs

Your malloc implementation is required to be thread-safe, so that multiple threads trying to allocate dynamic memory at the same time do not cause malloc to break. For this assignment, you will handle this requirement with a simple spinlock implementation. This will require you to use the LR and SC RISC-V instructions via inline assembly.

We will fill this in with more information in the near future. For now, focus on other aspects of the implementation; spin locks can be added after the rest is implemented.

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

  • Makefile -- compiles 4 possible executables, each with 3 possible versions (see below)
  • heaplame.c -- a deliberately flawed malloc implementation for testing purposes
  • heaplesslame.c -- a copy of heaplame.c that you are welcome to modify (will not be submitted)
  • heaplib.h -- the interfaces of the functions you are to test and implement
  • heaplib.c -- your implementation will go here
  • tests.c -- your test suite will go here
  • test_heaplib.c -- contains the main() function that will call your tests
  • spinlock.h -- the interfaces for the lock you are to implement
  • spinlock.c -- you will implement this with inline RISCV assembly

Before compiling your code, run python to initialize the necessary environment.

When you run make, it will compile the executable test_heaplib, which will run your tests.c file, which will test the library you implement in heaplib.c. The tests file currently contains a few tests but is not exhaustive; you should add your tests from lab 12 as well as any other tests necessary to catch broken mallocs. Your tests file will be graded on how many of our broken mallocs they catch, not on how many tests there are (see the test suite section for details).

Once compiled, you can run a specific test with ./test_heaplib n where n is the test number.

You may pass different arguments to make to change which version will be built and which library to use. 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 first target produces a "production level" executable. This is how we will compile your code when we test it.
  • The second target 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 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.
Since you will spend much more time working with heaplib.c, this is the default library that will be used. To use a library other than heaplib.c:
  • Run make lame (or make lame-debug/make lame-print-debug) to use the heaplame.c implementation instead of heaplib.c.
  • Run make ll (or make ll-debug/make ll-print-debug) to use heaplesslame.c.
  • Run make riscv (or make riscv-debug/make riscv-print-debug) to use heaplib.c with a RISC-V toolchain. Use this if you want to step through any assembly in gdb.

You can also put scan-build in front of any of these make commands, e.g. scan-build make. This will run a static analyzer over your codebase, which you can find out more about here. Go ahead and peek at the Makefile. It is fantastically documented. You do not need to modify the Makefile for this assignment. (If you choose to modify it, keep in mind that we will use the original when we test your code.)

Heaplame Deep Dive

We have provided you with a lame implementation of the assignment in heaplame.c. This implementation is meant to give you a way to start understanding how a dynamic memory allocator might work, but beware: (1) this implementation is buggy. In several respects, it does not follow the specs above and (2) this approach is inherently simplistic. The overall approach of heaplame.c is to keep track of only N_SUPPORTED_BLOCKS:


This means that the user may only allocate 5 blocks at a time. (Pretty lame, huh?) The information for each block (the size and the starting address of the block) is stored in a the following defined structure called block_info_t:

typedef struct _block_info_t {
    unsigned int block_size;
    void *block;
} block_info_t;

This block information is stored in an array in a containing structure called block_header_t:

typedef struct _heap_header_t {
    unsigned int heap_size;
    block_info_t blocks[N_SUPPORTED_BLOCKS];
    bool in_use_f[N_SUPPORTED_BLOCKS];
} block_header_t ;

This implementation dedicates the beginning of the heap to the metadata (which is initialized in hl_init), and the remaining portion of the heap to the 5 blocks allocated for the user.

In the beginning (see Figure 1) there is an array which the user has created (either by statically allocating it on its stack or by calling malloc). This is the area of memory which simulates the heap. If you look in heaplib.h, you will see the following definition:

#define MIN_HEAP_SIZE 1024

Let's step through the implementation of some of the functions. Figure 1 shows the state of memory before a call to hl_init with a heap of size 1024 beginning at address x100:


After the call to hl_init, the meta data has been initialized and the heap looks as shown below in Figure 2:


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


Figure 4 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. In fact, the code you have been given is woefully incomplete and incorrect. You should take some time to look at the implementation, run it through a few of the given tests, and write your own tests that expose the ways in which the code is broken or inadequate.

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

  1. no functions return pointers that are 8-byte aligned
  2. heap is assumed to be 8-byte aligned
  3. not all functions behave correctly when given null block pointers

.... and possibly more???

Although the implementation is not a working solution, it provides you important examples of heap management, casting, pointer arithmetic, and debugging.

Fixing all of the problems in this implementation would require a significantly different approach than the lame implementation. You are encouraged to spend some time thinking about how to debug this code (and to place your fixes in heaplesslame.c for sanity's sake, but it should not be viewed as the baseline for your own implementation, which should be far more sophisticated. For Part 2 of this assignment, 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.

  • Casting. Take a look at the implementations of hl_init and hl_alloc. Notice that casting the heap to a heap_header_t * is a straightforward and very readable way to set and access the fields of the otherwise unspecified heap.

  • print_debug functions. Look at the function print_debug_entering_init. It only prints "Entering hl_init()" to the screen. Although this function may be useful to a programmer when implementing and debugging, it is not the kind of information that should be printed to the screen when a program includes and makes calls to your heaplib 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. Print statements can be particularly devastating during a long run -- at best they make the code painfully slow; at worst they fill up the hard drive and make the computer unusable.

  • 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) {

    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 body of the print statement as the controlled text in a conditional group:

    void print_debug_entering_init() {
    #ifdef PRINT_DEBUG
        printf("Entering hl_init()\n");

    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. If you didn't want to create a separate function, you could also simply wrap the printf directly:

    #ifdef PRINT_DEBUG
      printf("the value of x is %d\n", x);

    This may not be the best strategy for every scenario, but it is good 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 need to understand pointer arithmetic. As a basic example, see the following snippet of code:

  • int array[4];
    int *ptr = &array + 1;

    What do you think ptr points to? Not sure? Paste the code into the C Tutorial, click on "Visualize Execution", and step through it. When you add 1 to the pointer, the unit of addition is int, meaning that you're taking the base address of array, and saying "go one integer later". The 1 is actually 1 integer, or 4 bytes.

    When you are manipulating pointers in this assignment, you may often want to add "raw bytes". For example, if you want to get the address that is 16 bytes into your heap, which you've already cast to be a heap_header_t *, you would need to write:

    heap_header_t *header = (heap_header_t *)heap;
    void *sixteen_later = ((char *)header)+16;

    Because we suspect you might want to do addition like this a lot, we've provided you with a simple #define:

    #define ADD_BYTES(base_addr, num_bytes) (((char *)(base_addr)) + (num_bytes))

    which you can could then use as follows:

    heap_header_t *header = (heap_header_t *)heap;
    void *sixteen_later = ADD_BYTES(header, 16);
  • C is not the same everywhere! You should not assume that you know the size of all variable types in C. An int might be 4 bytes on one machine and 8 bytes on another. This is one reason why it is VERY important to use the VM or the Linux machines we have provided for this class for this specific assignment. If you never run your code on the machines we test them on, you may be in for a horrible, seg-faulty surprise. It is always a good idea to use sizeof() instead of assuming you know the size of any variable or type in your code. Alternatively, uintptr_t in <stdint.h> is guaranteed to contain the size of a pointer on the machine where the executable is running. You may find this useful.

  • Another aspect of C is that the compiler will align your structures for you. How it performs the alignment varies not only by machine but also by operating system, so once again, do not make any assumptions. As an example, look at the definition of heap_header_t.

    typedef struct _heap_header_t {
        unsigned int heap_size;
        block_info_t blocks[N_SUPPORTED_BLOCKS];
        bool in_use_f[N_SUPPORTED_BLOCKS];
    } heap_header_t ;

    How large is this structure? hl_alloc calculates the size of the header to be:

    sizeof(unsigned int) /* heapsize */
    + sizeof(block_info_t) * N_SUPPORTED_BLOCKS /* block info */
    + sizeof(bool) * N_SUPPORTED_BLOCKS /* in use */

    However, if you simply said sizeof(heap_header_t) you might get a different answer because the size of the structure is typically rounded to a size that is divisible by 4 (or sometimes 8). This is one of the reasons we require you to keep your block pointers also 8-byte aligned. (This is also one of the reasons we did not put the in_use_f flags inside the block_info_t structure.) You should decide exactly how you want to pack your data in the heap. It will be important for you to understand structure alignment so that as you make these decisions you understand how to implement them.

  • Using 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 debug-able at no performance cost.

  • 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

Make sure your dynamic memory allocator implementation is easy to read and debug. Not only will it make it easier to progress on this project, but we will also deduct style points for egregiously-designed code. The given sample code has 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 long project writeup? 15 minutes. Shedding your status as a novice and being able to produce code that is readable, debug-able, and portable? Priceless.

Malloc Test Suite

Our autograder contains an extensive lineup of tests as well as several variations of broken mallocs. You will be graded on how well your implementation passes our tests, as well as how many of our broken mallocs are caught by your test suite. This is why submitting a solid test suite will be important for this project! We strongly recommend you complete this part before starting work on your own implementation.

Look in test_heaplib.c and tests.c to see how the test suite is structured. There is room for 24 tests.

Spec Tests (0-15)

"Spec tests" detect ways in which a heaplib implementation does not meet the given specifications. There are many ways in which heaplame.c is not up to spec. Your task is to write tests that detect these problems. Use the known problems in heaplame as a way to foresee and avoid possible problems that your code could experience once you get to implementing it.

heaplesslame.c currently contains a copy of heaplame.c, but you are free to modify heaplesslame.c until it passes all of the tests that heaplame.c failed. heaplesslame.c will not be submitted to CMS, but many students in the past have found it helpful to their understanding to have completed it before starting their own implementations.

Stress Tests (16-23)

"Stress tests" detect errors that might only occur after many calls to the heaplib library. This could be due to subtle bugs, corner cases, or just errors that only manifest under extreme conditions (like the heap filling up).

There are two classic problems that result from a buggy implementation of heaplib:

The first we will call a structural integrity problem. At some point a field in the heap thought to contain a pointer will no longer contain a valid address. Perhaps you have a next pointer in a linked list, but you accidentally overwrite it with the size of a block. Now you try to dereference the address 42. This will result in a segmentation fault. Bugs that corrupt the structural integrity of your heap lead to fatal errors at runtime. You can test for structural integrity problems by simply hammering the library with a bunch of calls to alloc, resize, and free. If the test finishes, it is a success. If a segmentation fault occurs, the test has failed.

The second problem we will call a data integrity problem. In this case, a buggy implementation will either give the user a bad block of memory (maybe a block that goes past the edge of the heap, for example, or a block with some overlapping region that has already been given out in a previous request to alloc that has not yet been freed) OR the library itself writes something into the block portion of the heap, which it should never do unless that block has been freed by the user. You can test for data integrity by requesting blocks from the library and then filling the block with data. After subsequent calls to the library, check and see whether the data is still intact.


  • Make sure you use legal, well-formed calls. Also, make sure that the errors are a result of the heap library, and not your test:
    • if you ask for 24 bytes and then fill 42 bytes, you will probably corrupt data on your heap, but that's the test's fault not the library's.
    • if you try to call free with a pointer that was never returned by the library from a previous call to alloc, the library might very well seg-fault, but that's the test's fault not the library's. You cannot free something that was never allocated in the first place.
  • It is recommended that you have one test that uses just alloc and free and another one that includes resize. This way you can test your both before and after you have implemented resize.
  • It is recommended that your stress tests have at least 100 calls to each function. Please use loops and arrays that hold pointers. The tests should not be hundreds of lines long!
  • It is recommended that your stress tests call for blocks of varying sizes. Structural and data corruption often manifests itself only when different blocks are requested for, not when the same chunk of memory is requested and freed repeatedly.
  • Our robustness tests (which we will use to grade your code) check for both structural and data integrity. However, how you write these tests is your choice.

You should maintain the current structure of the test suite:

  • A 1-line description of each test, ending in whether the test passes or fails when you run ./test_heaplib [test #]. This description should be put at the top of your tests.c file.
  • A comment before each test indicating which functions you are testing, what specification you are checking, and how an error would manifest.
  • Embed all print statements inside the PRINT_DEBUG macro.

You will submit your tests.c file to CMS. Each submission will trigger an automatic autograder run and you will receive an email with the result of your tests. We will run your spec tests on variations of heaplame that have isolated individual errors. We will run your stress tests on a suite of "broken mallocs". The more of them your stress tests flag as broken, the better your grade.
The test suite will be graded on how thoroughly it catches implementation errors. Tests that yield false positives (finding errors where there are none) will be discounted.

IMPORTANT: You are graded on how many broken mallocs your test suite finds, not on how many tests you have! In semesters past, students have asked for more test placeholders. This is why you have room to write 23 tests. However, you certainly do not need all 23 of them to receive full credit on testing.

You will have 5 autograder runs per day. Failure to compile still counts as a run.

What constitutes a good test? A good test should flag a broken implementation as broken, but it must not flag a correct implementation as broken. If your tests violate the preconditions or the usage model of heaplib, they will be ignored when grades are assigned.

What constitutes 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 SEGFAULTing.

Designing and Implementing Your Own Memory Allocation Library

Now that you have written solid tests, it is time for you to implement your own malloc library. Your code must follow both the interface and the functional specifications which were outlined above.

You are free to implement malloc as we suggest or use your own original ideas. As you consider your options, you should under no circumstances look at anyone else's code (including code on the internet).

Your implementation will be graded based on correctness. Correct implementations of heaplib.c will then be evaluated on memory utilization and speed. (Incorrect implementations will not be tested for utilization--and will forgo the points associated with these tests--because these metrics are meaningless in the context of an incorrect program. (Example: you can fulfill many allocation requests when you give everyone the same overlapping bytes in the heap...)

Utilization. When a heap is initialized, it is given a fixed memory area that it can use to fulfil 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 block, the size of each block, whether it is free, etc. Less meta data allows you to dedicate more of the heap to service alloc requests.
  • 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 fulfil future allocation and resize requests.
  • 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 fulfil the request. This is the easiest to implement. A best-fit approach gives the user the smallest memory block that fulfils the request.
  • 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. Whether you support the coalescing of blocks (explained in the pdf) is another.

The Leaderboard

The autograder will run your code up to 5 times per day. Note that this autograder only tests the heaplib implementation. Due to prohibitive server loads, ensuring the correctness of your spinlocks is not accounted for in the P6 malloc leaderboard. It is up to you to ensure that your lock/unlock functions work as intended.<

Your code will first be tested for correctness. Code that passes our correctness tests will then be tested for overhead, and heap maintenance. 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 hope you will be able to see from this exercise that design choices are full of trade-offs, often sacrificing one metric for another.

The leaderboard can be found here: Leaderboard


  • These slides can help give you an idea of the different kinds of implementations you can use.
  • 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_heaplib 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?"


You 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.

A rough breakdown of your grade is as follows:

  • 25%: Testing
  • 55%: Correctness
  • 10%: Utilization
  • 10%: Speed

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


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.