CS 213 Spring '01
Lab 3

Lab Assignment L3 ( L3.ps, L3.pdf )

"The lab that gives 213 its zip..."
Due: Wednesday, March. 21, 11:59PM
Checkpoint: Tuesday, March 13, 11:59PM

You can check the current garbage collection stats to see how you and your classmates are doing.

Your score for this assignment is based out of 70 points:
10 points - checkpoint, you should know this by now
50 points - correctness
    30 - actual program tests, 5 points for each test
    20 - tracefile tests
      10 - noncoalescing tracefiles
     10 - coalescing tracefiles (coalescing.rep and random2.rep)
     IMPORTANT: you will only get full credit if you get reasonable
     utilization on these tests, ie more than %50. coalescing.rep
     won't actually fail like random2.rep
5 points - style, see below
5 points - performance, see handout

Five points of your assignment are allocated based on style. Style is a subjective criterion, but we will use the following as a guideline in assigning style points:

You will lose 1-3 points for the following:
-Poor commenting (either lack of quantity or quality)
-Memory leaks
-Heavy use of constants (ie, using 12 instead of sizeof(Tree))
-Inadaquate writeup in handin.txt.
-Undescriptive variable names, functoin names, comments (ie, foo..)
-Compiler warning with -Wall turned on

You wil gain 1-3 points for the following:
-Good function decomposition
-Good code reuse
-Highly portable code
-Excellant writeup in handin.txt

You can't score more than 5 or less than 0 points for style.

You must run gmake handin to submit your code for the checkpoint. gmake update will only submit your code to the webserver and will run the all the tests (not just the checkpoint tests). No code submitted with gmake update will be graded.

The checkpoint is worth 10 points. Your grade for the checkpoint is based on whether you pass the tests the -k option of the driver runs. You either get all the points or none. However, if you don't have the program working, you will get partial credit for handing in late. For each day late, you lose two points, so:
On time 10
Wed night 8
Thu night 6
Fri night 4
Sat night 2
Any later 0

Please don't handin unless you actually have a working version.


After coalescing two blocks, don't forget to zero our the header of the inner block so you don't end up with stale heap pointers in the user data section of the block.

Read the assignment several times and go over confusing parts with your partner. Make sure you understand all the code in malloc.c before you write anything.

Q: How do we know the top of the stack?
A: It is in the given somewhere in the code. Also, you could daisy chain through the ebp values until you get to the top of the stack.

Q: What is the data area for?
A: There are three types of objects in a program.
1. Those that are allocated in the stack (which are local to functions)
2. Those that are dynamically allocated by malloc.
3. Those defined globally. These cannot be allocated on the stack, because, there is really no stack at the time they area allocate -- global variables are allocated at the compile time.
The data are contains these global variables. So you should stride through the are via a pointer and everything that "looks like " a pointer is a root.

Q: What does "looks like a pointer" mean?
A: Any word whose value is between dseg_lo and dseg_hi looks like a pointer. it just looks like one, because it actually may not be one. For example, if you define an integer as follows:

    void foo () { 
            int i = 0xFFA01 
then it may happen that the value 0xFFA01 is an address in the heap. Unfortunately, when you see the word corresponding to i in the stack you cannot tell its type, it might as well be a pointer. in the end both pointer and ints are stored in the same way. in general, any word in the stack or register or the data area can be a pointer and you would not know if it actually is or not. so, CONSERVATIVELY, we will assume that everything that looks like a pointer is a pointer.
This conservative assumption makes sure that we always mark memory blocks that are reachable. (as an aside, even a constant in the code may look like pointer, fortunately, if they are used to access pointers they will be in a register or saved somewhere in the stack, or data area and will be taken care of).

Q: How can we find the "pointers" in a block.
A: You see if each word in the block looks like a pointer. A word looks like a pointer if its value (unsigned integer value) falls between dseg_lo and dseg_hi. So you should stride through the memory allocated for the block and adds those that looks like a pointer to your stack.

Q: How can i find the start of a block. the alloc_tree gives me the size and the children and not the start of the block?
A: Note that the tree itself is allocated in the heap, i.e. the address of the node that "contains" returns is actually the address of the node in the memory. since the block is embedded in a node, you can determine the address of a block from that of the node easily by accounting for the other members of the node (size, prev and next).

Q: Similarly, when deleting the a block, i need an address that the block contains to be able to delete it -- that is just how the splay tree interface works. So where do i get that address?
A: The previous question might be helpful with this.

Q: This assignment looks hard. how am i supposed to figure everything out?
A: Start early. Discuss things with your partner. Go to office hours. Go over the lecture notes and book. Don't hesitate to ask for help.

The provided code will not call garbage_collect for you. You have to decide where and when the best time to call garbage_collect is.

Revisions and Updates:

For the performance metric, a shorter time is better so the ratio should be T_ref/T not the otherway around.

When you gmake update the script will build your code with optimizations turned on (-O).

Back to CS213 home page.