Description
In this week’s assignment you will do two things.
First, you get additional practice reading assembly code, figuring out what C program it came from, and counting memory references — skills that will be useful on the midterm and beyond.
Second, we will examine dynamic allocation and de-allocation in C. The goal here is to help you clarify your understanding of this topic, particularly dangling pointers, memory leaks, and how to avoid them. You’ll start by implementing a simple memory allocator, to get you more familiar with how it works under the hood.
Then, you will examine a program that contains a dangling pointer bug to identify the problem and fix it. Download the code file Download the file www.students.cs.ubc.ca/~cs-213/cur/assignments/a5/code.zip. It contains the following files, some in subdirectories named q2 and q3: 1. q1.[cs] – Question 1 2. refcount.[ch] – Questions 2, 3 3. q2: main.c, mymalloc.[ch], Makefile – Question 2 4. q3: {list,tree,element}.[ch], main.c, and Makefile – Question 3 Question 1 — Reading Assembly Code [10%] Read the included q1.c and q1.s files.
You will see that q1.c declares two structs, allocates some objects from those structs and initializes them. It has a procedure named q1() that is blank. The code listed in q1.s implements the code in this procedure (without the procedure call itself). Read q1.s carefully and run it through the simulator to figure out how it manipulates these structs.
Then do the following. 1. [2%] Comment every code line of q1.s with a high-level comment (i.e, a C-like comment). 2. [6%] Modify the procedure q1() in q1.c to perform the same computation as q1.s. Do not modify the other parts of this C file; they are used to test and mark your code. Note that you can optionally provide different values for the structs on the command line. The C code you write must work for arbitrary values. 3. [2%] Examine the code you wrote for q1(). Count the minimum number of memory reads and writes that are required to execute these five statements together.
Note these numbers may be different from q1.s, which takes each line individually (e.g., reading the value of i each time, which is not really necessary). Ignore register allocation for this questions; i.e., you can assume that you have an infinite number of registers available. Place these two numbers in the file q1.txt on two separate lines with the number of reads listed first (just these numbers and nothing else). Then carefully explain your answer by listing each of the reads and writes that are required (describe the access using variable names) in the file q1-desc.txt.
Question 2 – malloc and free [55%]
In this assignment, you will implement a functioning but simple version of malloc and free from scratch. Real implementations of malloc/free must deal with two issues that we will ignore: fragmentation and efficient allocation, which makes the real implementation much more complex (over 5000 lines of code) than what you will write. Your goal is simply to ensure that (a) every active allocation is located in its own, distinct location in memory and that (b) memory that is freed is reused whenever possible in subsequent calls to malloc.
The goal is to arrive at a simple, yet functional implementation which is able to service requests using an explicit free list (textbook section 9.9.13; basically, freed blocks are added into a linked list and searched during malloc). You will be guided through the approach, but start early because it’s easy to make mistakes and have to spend time debugging.
To start off, look at the code sample provided. It has a Makefile and two main modules: mymalloc. {c,h} and main.c. You will modify and hand in the implementation in mymalloc.c, but leave mymalloc.h and main.c alone (you can modify them for local testing if you like, but the autograder will not use your versions). You can add helper functions, variables, and constants as you wish in mymalloc.c. mymalloc exports three functions.
Read through the documentation in the header file to know what they do, and see main.c for how they get used. The initial implementation you are given does not reuse freed memory. Instead, every call to malloc takes its memory for the current top of the heap, and then advances the heap top by the size of the allocation. This is simple and fast, but of course means that every program has a memory leak.
Your goal is to change malloc and free so that freed memory is reused whenever possible. main.c implements three test-cases which will stress your malloc implementation. Your goal is to pass all of the tests. The autograder will use the exact same tests, so if you pass every test locally you should be able to pass the tests on the autograder.
To compile, run make in this directory to make the mymalloc binary. To run a test, run ./mymalloc , or use ./mymalloc all to run every test in sequence. The provided implementation of malloc passes sanity, but fails the others. Implementing malloc and free 1. The first problem you need to solve is to record the size of each allocated block as part of the block, in a prefix metadata hidden from the caller. You’ll need to know this size when returning blocks to the freelist when myfree is called.
You’ll use the same technique here as we do to store the reference count for reference counted objects, so use the provided refcount.c as a guide. Modify your implementation to add the metadata prefix to the beginning of the allocated block, thus increasing its size, and to shift the return value pointer to bypass this prefix. Be sure that the address you return is properly aligned to an 8-byte boundary, which is something malloc must always do.
Test your implementation by (a) ensuring that it still passes the sanity test and (b) adding a test to check that the size you store in the object has the correct value (e.g., by adding that test to the test_sanity procedure used in the sanity test). 2. Next, you’ll implement myfree by building a singly-linked list out of the blocks of free memory; each call to myfree adding to the top of the list. You can take a look at list.c and list.h from Question 3 for an example implementation.
Note, however, that list.c implements a doubly-linked list, so your implementation will be simpler as you need only a next pointer and no prev (or elem) pointer. Note also, that you will store this next pointer inside of the freed block itself. Do the following. Create a static head pointer to point to the most recently freed block of memory. On each call to myfree, store the current value of the head pointer into the block being freed, as its next pointer, and change the head to point to this freed block; thus forming a linked list out of the freed blocks.
Test your implementation to make sure it still passes the test_sanity test and then temporarily modify myfree to check that the freelist has the correct size after each call to myfree. Note that at this point mymalloc is not using the freelist and so the size of the freelist is equal to the number of times myfree has been called, which you can determine using a static counter variable.
Once this test passes, comment out this test code before proceeding to Step 3, because once mymalloc starts using the freelist, your test code will no longer be valid. Note: pointers on the autograding machine will be 8 bytes in size. 3. Finally, change mymalloc to use the free list. Check the size metadata of each block on the freelist to find one that is big enough to hold the allocation; it is fine to use a block that is bigger than the requested size.
You can experiment with different ways to choose a matching block: possible choices include first-fit, which returns the first block found that is big enough, or best-fit, which returns the smallest suitable block. Make sure to unlink the returned block from the free list. 4. By this point, you should be able to pass all the tests. If you don’t (which is extremely likely at first), you’ll have to debug your implementation by adding printf statements and/or using gdb or lldb.
Start your testing with the freelist1 test, which is the simplest test and thus the easiest to use for debugging. Don’t try the other tests until this test passes. Then do the same with each of the other tests in this order: freelist2, fixedsize, and random. Hand in only the file mymalloc.c.
Question 3 – Reference Counting [35%]
NOTE: This question has been moved to Assignment 6. Do not submit anything for this question this week, but of course you might start on it early if you have time. The weighting of the other two questions will be adjusted to 15% and 85%. The program in the q3 directory can be built using make while in that directory.
You can then run the program by typing ./main A B C D The program takes an arbitrary number of string arguments. It is supposed to print out a binary search tree, which is formed out of a subset of arguments, twice. However, as you can clearly see, the program does not produce this output; it correctly prints only one tree. It has a bug. To see the correct output of the program, you can remove all the free() calls in the program, replacing the dangling pointer bug with a memory leak.
The implementation uses two libraries, list and tree, implementing a doubly-linked list and a binary search tree respectively. Both libraries are free of bugs if used independently, but exhibit a bug when used together.
1. Find the bug and write a careful description of it in the file q3.txt. The bug is a dangling pointer somewhere. You may also want to read the header files carefully to see whether the libraries are being misused.
2. Now, fix the bug using reference counting. You must use the provided refcount.c and .h files for reference counting (the Makefile is already setup to use them; add “#include “refcount.h”” to C files as needed). You can change the interface in element.h and any of the implementation in element.c (retaining its ability to store strings and numbers).
You should not change any of the other .h files, and make minimal changes to the other .c files aside from adding reference counting (e.g. calls to element-specific keep_ref/free_ref functions that you define). Elements must still be shared between the list and tree – you should not simply make copies of the elements (which would introduce inefficiency).
3. After fixing the bug, test your program to ensure that it produces the correct output and that valgrind reports no memory leaks. To do so, you must run the program through valgrind, which is available on the undergrad servers but likely not on other platforms you might use for other parts of the assignment.
The test you need to run is the following: valgrind –tool=memcheck –leak-check=yes ./main If you have a memory leak you will see an error that looks something like this: ==31419== LEAK SUMMARY: ==31419== definitely lost: 240 bytes in 2 blocks ==31419== indirectly lost: 240 bytes in 2 blocks If you have a dangling pointer you may see an error that looks something like this: ==31993== Invalid read of size 1 ==31993== at 0x4E7D000: vfprintf (vfprintf.c:1629) If you eliminate both bugs (your goal) then you should see output something like this: ==1272== HEAP SUMMARY: ==1272== in use at exit: 0 bytes in 0 blocks ==1272== total heap usage: 4 allocs, 4 frees, 480 bytes allocated ==1272== ==1272== All heap blocks were freed — no leaks are possible ==1272== ==1272== For counts of detected and suppressed errors, rerun with: -v ==1272== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2) Or you might see (depending on which version of valgrind you use): ==9402== LEAK SUMMARY: ==9402== definitely lost: 0 bytes in 0 blocks ==9402== indirectly lost: 0 bytes in 0 blocks ==9402== possibly lost: 0 bytes in 0 blocks ==9402== still reachable: 4,096 bytes in 1 blocks ==9402== suppressed: 25,084 bytes in 373 blocks
What to Hand In
Use the handin program. The assignment directory is ~/cs-213/a5. It should contain the following plain-text files: 1. The files q1.s, q1.c, q1.txt, and q1-desc.txt for Question 1; 2. a subdirectory named q2 just like you see in the code file; 3. in the q2 directory: mymalloc.c;
