Malloc Tests Lab
CS 3410 Spring 2019
Lab 12 (5 malloc tests) Due: 11:59pm, Sunday, April 28, 2019
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 file for this lab in your Github repository. Be
sure to make good use of git with all of its
What to submit
For Lab 12 upload
tests.c to CMS. An
autograder will provde you with pre-deadline feedback.
If you receive a file that looks like this
This is a compilation error.
This section describes the specifications of the dynamic memory
allocation library you will write for
Project 6 * Malloc.
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
heaplib.h and will be implemented (by you)
P6 * Malloc, but for now you will be testin.
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
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
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
Do not assume that
heapptr is 8-byte aligned.
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
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
currently resides in the heap pointed to by
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_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
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
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
blockptr has the value 0 (
the function should behave like
hl_resize() correspond to the actual C Standard Library
heaplib.c should you call these three library
Compiling and Running Your Code
You have will be given the following files as part of
P6 * Malloc
tests.c is the only one you will work on for Lab 12):
heaplib.h -- contains the interfaces of the
functions you are to test and implement
heaplib.c — this is the file containing your
tests.c — this is the file containing your test suite
compile.sh — this is how you will compile your malloc
run_each_tests.sh — this is how you will run your malloc
implemation against tests
spinlock.h — this contains the headers for the spinlock
you are to implement
spinlock.c — this is the file containing the spinlock
you should implement with RISCV assembly
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
uses your library. The test file will contain many test files but will not
be exhaustive. You should consider implementing some of your own tests.
You should be prepared to do this after your lab.
Completing 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
tests.c. (Feel free to add additional
tests). You can implement the rest of the tests on your own to test
the validity of your malloc implementation 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
tests.c is intended to be a thorough test for the
correctness of any heaplib implementation. At the moment, however, it
only tests three things:
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
tests.c to catch the first five of
them. (The fixed code will be
helpful for your
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.
When you have completed
tests.c it should report the first five of the
correctness problems with a broken implementation of malloc. 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
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).
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
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
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.
Lab 12 will be graded on catching all 5 broken mallocs using the first 5 test cases, but we highly
encourage you to implement as many malloc tests as you can since they will be instrumental in
testing your malloc implementation in
Project 6 * Malloc.
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.