Programming Assignment 3

CIS 20 Fall 2019 – Programming Assignment 3 – Part 1
Heap Allocator using Implicit Free Lists
❖ Learn how the internal operations of malloc() and free() work.
❖ Complete a heap allocator using the implicit free list data structure.
❖ Implement the allocate, free, split, and coalesce heap operations.
Video 1 ​- Set up and project overview
Video 2​ – Implicit free lists data structure
Video 3 ​- Alloc and free algorithms
Video 4​ – Split and coalesce algorithms
Files and Functions

File Description
Makefile Contains the configuration to build the project.
Run maketo build
Run make cleanto clean
Run make teststo build tests
Do NOT modify this file.
memlib.h Header file for the memlib library. You will use this library to help you
emulate the OS heap operations.
It defines the following library operations:
void mem_init(void);
void mem_deinit(void);
void *mem_sbrk(int incr);
void mem_reset_brk(void);
void *mem_heap_lo(void);
void *mem_heap_hi(void);
size_t mem_heapsize(void);
size_t mem_pagesize(void);
Do NOT modify this file.
memlib.c Implementation of the memlib library.
Do NOT modify this file.
main.c Entry point for the application. You can put whatever you want in here to
test your implementation. You will not turn this file in.

​​ ​​ ​​

Compiles to cis20_alloc_part1 binary
alloc.h Header file for the alloc library (our custom heap allocator).
It defines the following library operations:
void cis20_init();
void cis20_deinit();
void *cis20_alloc(size_t numbytes);
void cis20_traverse_heap();
void cis20_free(void *ptr);
Do NOT modify this file.
alloc.c Implementation for the alloc library.
You are responsible for completing:
❖ cis20_init
❖ cis20_alloc
❖ cis20_free
❖ block_split
❖ block_coalesce
You WILL turn in this file. Write your code here.
test0-6.c These are test files that test different aspects of the heap allocator.
You will turn in any tests that you wrote beyond test5 (e.g. test5, test6, etc).
ref_test0-6.out Correct for the test0-6.c

Building the Project
Accept your assignment here​ and clone to your Cloud9 environment.
Only use Cloud9 for writing, compiling, and running this project. If you complete your project on your
personal computer and it does not compile and run on Cloud9, you will not receive credit.
Compile/build your project by running:
$ make clean; make
Run the first test file to ensure that the test runs:
$ ./test0
Running Tests
Install colordiff:
$ sudo apt-get install -y colordiff
I have provided 4 test driver files and output files.
Run tests individually and save their output to a file.
$ ./test1 > my_test1.out
I have provided reference outputs: test1.out – test4.out
Use the reference outputs to help you determine if your heap allocator is working properly.
Do not modify ​test0.c – test6.c​. I will use those to grade your assignment.
When I grade your assignment, I will run diff to determine if your output matches the key:
$ colordiff my_test1.out ref_test1.out
The purpose of each test is explained at the top of each test file.
You should add additional test files by naming them ​testXXX.c
Makefile is configured to compile all C files that start with “test”. You can and should share your test files and
their output with peers via Slack. This will help you improve the accuracy of your heap allocator.
Allocating the Default Heap Block
When the cis20 library is initialized, you must create the default heap block. This unallocated block will exist to
start the heap. It may not be the first block used because it only has a size of 24 bytes. Remember that 8 bytes
of every block are reserved for the header and footer. Thus, a 24 byte block only has 8 bytes available to store
user program data!
Within the cis20_init function, replace TODO with the following:
// Request 24 bytes from the OS.
char *first_block = (char *) mem_sbrk(24);
// Write header and footer into first block.
block_write_hf(first_block, 24, 0);
Run test0 to verify that your heap initialization is working.
Helper Functions
Read the entire ​alloc.c​ file before starting. I have not provided the types for the variables in the pseudocode
– you must infer those by reading and understanding the existing code. You will have to use the following
helper functions: ​make_header, is_allocated, get_size, get_capacity, get_data_addr,
closest_block_size, block_write_hf​.
cis20_traverse_heap​ will use the block headers to traverse your heap blocks. It prints out helpful
information to show you how accurately you’ve laid out your heap. It is crucial that you use this output to
understand what is being held in your heap blocks.
For example, here is some ​cis20_traverse_heap ​output from test2:
– Heap State – size: 96 bytes ——————–
0x010​ size: 24 data size: 8 alloc: 1
hdr: ​0x19​ ftr: ​0x19
data: p1
0x028 size: 32 data size: 16 alloc: 1
hdr: 0x21 ftr: 0x21
data: p0
0x048 size: 40 data size: 24 alloc: 1
hdr: 0x29 ftr: 0x29
data: p2
Each row represents one heap block.
The block address was shortened to 3 digits to make it more legible.
The header and footer values were shortened to 3 digits to make it more legible.
How to Allocate a New Block
You must complete the implementation of ​cis20_alloc​.
cis20_alloc​ should behave just like ​malloc​. It will attempt to find an existing free block by traversing the
implicit free list. We will implement the first-free algorithm for finding free blocks. When the first block that is
large enough is found, that block is allocated to the caller of ​cis20_alloc​.
Here are two examples of using ​cis20_alloc​ to allocate objects on the heap:

Allocating a String on the Heap
char *str = (char *) cis20_alloc(8);
strcpy(str, “hello!”);
Allocating a Struct on the Heap

struct foo
long a;
int b;
truct foo *my_foo = (struct foo *) cis20_alloc(sizeof(struct foo));
my_foo->a = 42;
my_foo->b = 99;
I have provided the pseudocode for the first-free algorithm.
Here is the pseudocode for ​cis20_alloc​:
current_header = heap_begin
block_fit = NULL
block_size = 0
request_size = closet_block_size(numbytes + sizeof(size_t) * 2)
while current_header < heap_end:
size = …
is_alloc = …
if size is 0:
if not is_alloc and size >= request_size:
block_fit = current_header
block_size = size
current_header += size
if block_fit is null:
“Unable to find block to accommodate %lu (%lu) bytes.\n”,
printf(“Requesting new block of size: %lu\n”, request_size);
char *new_block = (char *) mem_sbrk(request_size);
printf(“New block starts at “);
if (long) new_block is not -1:
block_fit = new_block
block_size = request_size
heap_end = mem_heap_hi()
printf(“Unable to expand heap\n”);
return NULL;
printf(“Block found at “);
block_size = block_split(block_fit, request_size);
printf(“block size: %d\n”, block_size);
block_write_hf(block_fit, block_size, 1);
// Return data start addr
return get_data_addr(block_fit);
Run test1 and test2 to verify that you have correctly translated the code.
How to Free an Allocated Block
You must complete the implementation of ​cis20_free​.
cis20_free​ should behave just like ​free​. It will use the address given to lookup the header and footer of the
block. It must then overwrite the header and footer to mark each block an unallocated. This function does not
have to zero-out any of the data bytes. By marking the header and footer and unallocated, the heap allocator
will know to disregard the block data; although the ​cis20_traverse_heap​ function will still show you the
data (with the word junk to indicate that the space has been free).
Here is the pseudocode:
// Subtract one word to get to header.
header_ptr = ((char *) data_ptr) – sizeof(long);
block_size = …
// Overwrite old header/footer. Set alloc to 0.
block_write_hf(header_ptr, block_size, 0);
// After freeing, attempt to coalesce.
Run test2 to verify that you have correctly translated the code.
How to Split a Free Block
Block splitting only occurs during ​allocation​. In fact, ​block_split​ is already called by the ​cis20_alloc
function, but it does not do anything useful yet.
By default, the ​block_split​ function does not actually split the block, instead it just returns the size of the
The intent of the function is to split large blocks when not all of the block space is needed. This is meant to be
an optimization so that excessive fragmentation can be avoided.
For example, if the block is 64 bytes and only 24 bytes are being requested, the block should be split into two
blocks 24 bytes and 40 bytes:
char *block_fit = … ​pointer to 64 byte block​ …
// Returns 24 because the original block (block_fit) was resized.
int block_size = block_split(block_fit, 24);
The split operation takes a few steps:
1. Resize the original block to match the requested size.
2. Create a new block after the original block by writing a header and footer with the block size and
marked as unallocated.
3. Return the requested size to indicate that the original block has changed sizes.
The implementation of this algorithm is entirely up to you.
Run test3 to verify that you have implemented the code correctly.
How to Coalesce Free Blocks
Block coalescing only happens when a block is freed. In fact, ​block_coalesce​ is already called by the
cis20_alloc​ function, but it does not do anything useful yet.
By default, the ​block_coalesce​ function does not actually coalesce nearby blocks. You must implement
forward and backward coalescing. ​cis20_alloc​ will coalesce forward if possible or backward if possible, but
not both (even if it’s possible). The ​block_coalesce​ function does not return any value.
When a block is freed, ​block_coalesce​ will add the size of itself to its header address to reach the header
of the next block. Upon reading the header, if it finds that the next block is also free, then the header (and
footer) of the original block will be updated to stretch across both blocks (effectively merging the blocks). This
is forward coalescing.

Before After
free block acoalesce

block a size: 24
block a
header alloc: 0
block a
block a
size: 24
alloc: 0
block b
size: 24
alloc: 0
block a
block b
size: 24
alloc: 0
block a
block a
Run test4 to verify that you have implemented the forward coalescing correctly.
Backward coalescing can be accomplished similarly. When a block is freed, block_coalesce will subtract 8
bytes from the header address to get the location of the previous block’s footer. Upon reading the footer, if it
finds that the previous block is also free, then the header of the previous block will be updated to stretch across
both blocks. Remember: to get the header location of the previous block, you must subtract the size of the
previous block​ from the ​current block header address​.

Before After
free block bcoalesce

block a
size: 24
alloc: 0
block a
block a
size: 24
alloc: 0
block b
size: 24
alloc: 0
block a
block b
size: 24
alloc: 0
block a
block a
block a
Run test5 to verify that you have implemented the forward coalescing correctly.
Writing Your Own Tests
It is impossible to know whether you have implemented your heap allocator correctly without thorough tests. I
have provided 6 simple tests for you. To receive full credit for this assignment, you must implement at least 3
thorough tests of your heap allocator.
To create a test, create a C file that begins with “test”. Make is configured to compile all files that begin with
“test”. Explain the purpose of your test with comments at the top of your test file.
Make sure to create a reference output file called ​ref_test#.out​. The autograder will expect these files.
Turn In
Turn in the following files to Gradescope:
❖ alloc.c
❖ Any test files and test output that you created (you must include both the ​.c​ and the ​.out​ files).
If you submit via GitHub, you do not need to worry about selecting individual files – the autograder will deal with
that for you.
You should not change the function prototype of any function included in ​alloc.h​; otherwise, the autograder
will reject your submission.

Leave a Reply

Your email address will not be published. Required fields are marked *