CIS 20 Fall 2019 – Programming Assignment 3 – Part 1
Heap Allocator using Implicit Free Lists
Goals
❖ 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.
Videos
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;
s
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:
break
if not is_alloc and size >= request_size:
block_fit = current_header
block_size = size
break
current_header += size
if block_fit is null:
printf(
“Unable to find block to accommodate %lu (%lu) bytes.\n”,
request_size,
numbytes);
printf(“Requesting new block of size: %lu\n”, request_size);
char *new_block = (char *) mem_sbrk(request_size);
printf(“New block starts at “);
print_short_address(new_block);
printf(“\n”);
if (long) new_block is not -1:
block_fit = new_block
block_size = request_size
heap_end = mem_heap_hi()
else:
printf(“Unable to expand heap\n”);
return NULL;
else:
printf(“Block found at “);
print_short_address(block_fit);
printf(“\n”);
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.
block_coalesce(header_ptr);
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
block.
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 a | coalesce |
block a size: 24
block a
header alloc: 0
block a
data
block a
footer
size: 24
alloc: 0
block b
header
size: 24
alloc: 0
block a
data
block b
footer
size: 24
alloc: 0
header
block a
data
block a
footer
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 b | coalesce |
block a
header
size: 24
alloc: 0
block a
data
block a
footer
size: 24
alloc: 0
block b
header
size: 24
alloc: 0
block a
data
block b
footer
size: 24
alloc: 0
block a
header
block a
data
block a
footer
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.