Lesson 11: Memory Management

[sampsyo]

These tasks are about implementing a garbage collector!

[keikun555]

Summarize what you did.

• Lesson 11 Task
• Modified brili.ts
• The modifications include:
  • A modified Heap class that has a referenceCounter map and size variables.
  • A disable-free-and-don't-garbage-collect flag without garbage collection to measure how much memory is allocated.
  • A disable-free-and-garbage-collect flag that makes frees no-ops and enables reference counting garbage collection
  • A remaining_heap_pointers profiling measurement that reports how many objects are remaining in the heap.

Explain how you know your implementation works—how did you test it? Which test inputs did you use? Do you have any quantitative results to report?

• I used this turnt.toml configuration for differential analysis and made sure my modifications don't break the interpreter. I ran turnt with the command turnt -j $(find . -iname "*.bril" | sort) | tee turnt.out and turnt was ok for all the benchmarks, in this output file

❯ rg "^not ok.*benchmark" turnt.out
❯

• This brench configuration which measures how many heap objects are remaining when turning free into a no-op with and without the reference counting garbage collector
• I ran brench with the command brench -j nproc benchmarks.toml | rg -v ",missing|,timeout" | tee benchmarks.csv to filter out missing and timeout results. The garbage collector frees all heap objects that were not freed in the without-garbage-collection baseline.

❯ rg -NIe "baseline,[^0]" -A 1 benchmarks.csv
sieve,baseline,1
sieve,gc,0
vsmul,baseline,2
vsmul,gc,0
quicksort,baseline,1
quicksort,gc,0
max-subarray,baseline,1
max-subarray,gc,0
mat-mul,baseline,4
mat-mul,gc,0
fib,baseline,1
fib,gc,0
eight-queens,baseline,1
eight-queens,gc,0
primitive-root,baseline,5
primitive-root,gc,0
two-sum,baseline,2
two-sum,gc,0
adler32,baseline,1
adler32,gc,0
binary-search,baseline,1
binary-search,gc,0
adj2csr,baseline,4
adj2csr,gc,0
bubblesort,baseline,1
bubblesort,gc,0
--
conjugate-gradient,baseline,30
conjugate-gradient,gc,0
--
norm,baseline,1
norm,gc,0
--
mat-inv,baseline,2
mat-inv,gc,0
cholesky,baseline,4
cholesky,gc,0
--
dot-product,baseline,2
dot-product,gc,0
--
mem,baseline,3
mem,gc,0
ptr,baseline,1
ptr,gc,0
--
access_many,baseline,1
access_many,gc,0
access,baseline,1
access,gc,0
ptr_call,baseline,1
ptr_call,gc,0
alloc,baseline,1
alloc,gc,0
fib,baseline,1
fib,gc,0
ptr_ret,baseline,1
ptr_ret,gc,0
mem_id,baseline,1
mem_id,gc,0
alloc_many,baseline,1000000
alloc_many,gc,0
access_ptr,baseline,2
access_ptr,gc,0
--
store-char,baseline,1
store-char,gc,0
store-float,baseline,1
store-float,gc,0
--
free_offset,baseline,1
free_offset,gc,0
double_free,baseline,1
double_free,gc,0
leak,baseline,1
leak,gc,0
❯

What was the hardest part of the task? How did you solve this problem?

• Increment before decrement For an instruction that would assign the same pointer to itself, i.e. a: ptr<int> = id a, I was initially decrementing the heap object and then incrementing it again. This could make the reference count to the heap object 0, and would free the object. I realized this when I was testing using turnt, and fixed all instances of such decrement-increment combinations to increment first.
• Decrement function stack variables when the function returns When a function returns, we must decrement the stack variables in the function. I do this whenever we call evalFunc, in the evalCall function when we have a call operation and in the evalProg function when we call the main function. I initially had the implementation in the evalCall function in this else statement which meant that only value calls would trigger the garbage collector, which broke test/interp/mem/access_ptr.bril. To debug this, I used console.error to log the heap and the referenceCounter before and after the function call to find the problem.

[bennyrubin]

Summary

Link to repo

Brili garbage collector

test directory that contains the brench results and some handwritten tests.

Implementation & Testing

For this assignment, I implemented a simple reference counter garbage collector for the brili typescript interpreter. I did this by adding a field to each memory object that indicates its reference count. It was fairly straightforward to do this following our discussion in class, with some trickiness in catching all the cases of incrementing and decrementing (I elaborate in the challenges section).

To test, I had some simple hand written cases that I made sure worked. The program will print at the end of execution if there is any memory that is still allocated on the heap. I then used brench and compared the following two configurations to check for equality:

• Normal brili on the memory benchmark programs
• My garbage collection brili on the memory benchmark programs will all the free statements removed

After getting all of the above to work, I am pretty confident in my solution.

Challenges

There were lots of tricky cases to consider, some of which I missed which lead to spurious errors. For example, you have to increment the ref count of arguments passed to functions, increment ref count of pointers that are returned from a function before they’re cleaned up by cleanup pass that happens at the end of functions, recursively decrement the refcount if a pointer points to a pointer and is freed, etc.

There is also the case where you set a variable to the same pointer (such as id or ptradd) and the order of incrementing and decrementing matters, so you don’t accidentally clean up the memory when the refcount hits 0.

This assignment certainly gave me an appreciation for how careful you must be with memory management and how easy it is to get it wrong.

[he-andy]

Summary

I, @evanmwilliams, @emwangs, worked together on this assignment. We chose to use brilirs for this assignment due to our lack of familiarity with typescript. The repo is linked here

Implementation & Testing

We implemented a simple reference counter by adding an extra map to the Heap struct in brilirs that maintains the count of the live pointers to any base address in memory. The counter is incremented only through the call and id ValueOps and is decremented either through a free of a pointer previously pointing to it's base address, a reassignment of a pointer to a different base address, or the end of the scope of a pointer. When the rc hits 0, the memory is freed and recursive calls are made to free any memory that the freed memory was pointing to.

We added a --gc to the brilirs command line interface to indicate whether garbage collection should be performed. If the --gc flag was enabled, the free instruction is automatically ignored to prevent accidental double frees. Brilirs actually indicates whether there were memory leaks in the program, so no additional implementation was neeeded to track memory leaks. We used the benchmark/mem directory to test our implementation with brench to test the correctness of our implementation.

brench.toml:

extract = 'total_dyn_inst: (\d+)'
benchmarks = 'benchmarks/mem/*.bril'

[runs.baseline]
pipeline = [
    "bril2json",
    "brili -p {args}",
]


[runs.gc]
pipeline = [
    "bril2json",
    "brilirs --gc -p {args}",
]

Results

benchmark,run,result
sieve,baseline,3482
sieve,gc,3482
bubblesort,baseline,253
bubblesort,gc,253
primitive-root,baseline,11029
primitive-root,gc,11029
adler32,baseline,6851
adler32,gc,6851
adj2csr,baseline,56629
adj2csr,gc,56629
max-subarray,baseline,193
max-subarray,gc,193
mat-mul,baseline,1990407
mat-mul,gc,1990407
fib,baseline,121
fib,gc,121
vsmul,baseline,86036
vsmul,gc,86036
quicksort,baseline,264
quicksort,gc,264
two-sum,baseline,98
two-sum,gc,98
eight-queens,baseline,1006454
eight-queens,gc,1006454
binary-search,baseline,78
binary-search,gc,78

Challenges

The biggest challenge we faced was understanding the brilirs codebase. We had to read through the codebase to understand how the brilirs compiler worked and how we could implement our reference counter.

[matth2k]

• Summary

  • Semi-space Garbage Collector in Bril

• Implementation Details

  • I used the reference brili interpreter written in TypeScript as a baseline.
  • Within the Heap class, I implemented a method called doCollection() that traces through the roots and the rest of the allocation graph. Allocations that are reachable from the roots are copied from the "from space" to the "to space".
  • Because each function has its own environment that can contain pointers, I needed to modify the State struct to contain a separate roots set. In my implementation, the roots of the current scope are the pointers in the current environment unioned with the roots of the call stack. I think using dynamic scoping to collect the roots might be incorrect in some cases, but this approach worked for me for every memory benchmark.
  • I wrote a small utility called removeFree.py, that removes free instructions inside Bril programs and replaces them with a dummy instruction that clobbers the pointer variable. This is an easy way to limit some memory leaks from dead variables hanging in the environment.
  • I used GitHub Copilot to help me with some of the TypeScript syntax that was unfamiliar to me.

• Evaluation

  • I evaluated my garbage collector by running it at different intervals with increasing frequency. To elaborate, I ran three scenarios:

    1. Run the garbage collector when we run out of space in the "from space"
    2. Run the garbage collector on every allocation
    3. Run the garbage collector every single instruction

  • Using these three configurations helped me test my garbage collector for correctness as well as give some insight into the patterns of space reclamation.

    • Thankfully, my garbage collector did not corrupt the heap, no matter how often I ran it.
    • When running the garbage collector at every instruction, I collected some data to get the max heap footprint of each program:

  Benchmark	Memory Footprint (num elements)
  major-elm	3
  vsmul	6119
  quicksort-hoare	51
  two-sum	6
  adj2csr	3073
  quicksort	6
  quickselect	6
  max-subarray	10
  adler32	512
  bubblesort	5
  binary-search	5
  fib	10
  sieve	100

  You could probably accomplish even lower numbers if you applied some more dead code optimization passes.

• Anything Hard or Interesting?

  • I naively thought I could just use a function's environment as the roots, but I quickly released the garbage collector is more elaborate than that.
  • It is hard to not re-copy something from the "from space" to the "to space" twice. Otherwise you will triplicate some data and have pointers that should point to the same data that do not. I prevented this by performing garbage collection on the base pointers, not the offsets. Then I cached the translation

• References Used

  • Cheney's algorithm

[vivianyyd]

Will and I worked on lesson 11 together.
Brili with GC

Summary

• We added a Tracing garbage collector to brili.ts that runs every 5 times it is called (which is after every alloc instruction). The garbage collector is also forced to run at the end of the main function return.
• The interpreter was modified to perform a "nop" to any "free" instructions, and the code passes all Bril benchmarks, with currently no signs of memory leaks.

Implementation details

• We first implemented a "stack" that keeps track of all current environments as an array would we would push or pop Envs from.
• We performed tracing by performing a DFS starting on every value on the stack that is a Pointer type (we did this type check by seeing if it having a "loc" property). Every time we follow a pointer, we go to the head of the memory segment it is located in and read through all the data in that segment, recursing on all pointers within that segment.
• Anything in the heap whose "key" was not visited was freed.
• To test the code, we also made some adversarial tests; for example, we have a test that calls a function 99999 times, whose only instruction is to call alloc. We make sure then that the heap does not exceed a certain size.

What was the hardest part of the task? How did you solve this problem?

• One bug we ran into was that we incorrectly assumed that Env was the stack. Rather, it was only the environment for the scope of each function, so our GC was freeing too often. We fixed this by keeping a stack containg the current environments.

[bcarlet]

Summary

• Modified Bril Interpreter

Details/Testing

I modified the brili TypeScript interpreter to implement basic reference counting. I modified the Heap class to keep track of a reference count for each memory location base, and I inserted increment and decrement operations for each instruction that might create/modify/delete a pointer.

To test that the implementation doesn't leak memory, I wrote a utility to remove all free instructions from the Bril memory benchmarks, and I checked that the size of the heap is zero before each benchmark exists.

Difficulties

I didn't encounter any major difficulties for this task, other than simply reading the reference interpreter carefully to find all the places where reference counting operations needed to be inserted.

[20ashah]

Summary

• Repo
• @JohnDRubio @AliceSzzze and I implemented a garbage collector for Bril in the typescript interpreter using the reference counting algorithm

Implementation Details

• We added a refcount field to the State type. refcount is a map from an object’s address to its reference count.

• We implemented a decrementRefCount function and an incrementRefCount function.

• decrementRefCount decrements an object's reference count then checks to see if that object needs to be freed. If so, recursive calls are made until the end of the “reference chain” is reached. Once the base case is reached, the object with a reference count of zero is freed from the heap and removed from the refcount map. If the reference count is not zero after being decremented, the refcount map is simply updated.

• incrementRefCount was simpler to implement. We just needed to add the object’s address and reference count to the refcount map if it wasn’t already an entry in the refcount map. Otherwise, we incremented the object’s reference count.

• We also added a function called decrementEnvRefs. This function calls decrementRefCount on pointers in a given environment.

• Locations in the interpreter where we inserted calls to decrementRefCount / incrementRefCount included:

• evalCall: In case the call returned a reference, we needed to increment the reference count of the address returned and decrement the reference count of whatever instr.dest may have pointed to prior to the call instruction. We also made a call to decrementEnvRefs to decrement the reference count of all objects allocated during the call.

• “id” instruction case: If the address stored in a pointer is assigned to another pointer, then we call incrementRefCount on the object stored at that address and decrementRefCount on whatever the LHS pointer may have been pointing to previously. We were careful to increment the reference on the RHS before decrementing the reference on the LHS to avoid accidentally freeing LHS in the case of LHS and RHS being aliases of each other

• “alloc” instruction case: We increment the reference count of the object stored at the address returned by alloc and decrement the reference count of whatever instr.dest may have pointed to prior to the alloc instruction.
  “ptradd” instruction case: We increment the reference count of the object stored at the address returned by ptradd and decrement the reference count of whatever instr.dest may have pointed to prior to the ptradd instruction.

• evalProg: Upon exiting the main function of the Bril program, we call decrementEnvRefs to decrement the reference count of any allocated objects from the main program.

• Lastly, we commented out the logic in the free instruction, effectively converting the free instruction into a nop.

Testing

For testing, we used turnt to test all of the bril benchmarks to make sure that adding our garbage collector didn’t change the behavior of any of the bril programs. As our baseline we ran turnt on all of the bril benchmarks without any garbage collection behavior (keeping the free instruction). We then ran turnt with our reference counting logic (with free as a no-op), and saw that brili printed out the same results for each bril program. To further test our implementation, we also made sure that after the program finishes, we print the heap to verify that all the garbage that should be collected has been collected and that there are no memory leaks.

• Turnt output baseline
• Turnt output after gc

Anything hard or difficult?

Considering all of the cases when decrementRefCount and incrementRefCount was a bit challenging. One obstacle we ran into was correctly implementing the base case in the recursive calls to decrementRefCount.

Overall, this was a fun project and it’s cool to see how we can implement a relatively simple algorithm which converts language from being a manual memory-management language to a garbage-collected language.

[NgaiJustin]

Summary

• Repo (link)

Details

I implemented a reference counting based garbage collector for Bril. I modified the existing Typescript bril interpreter to get a new brili-gc.ts

I create a CountedX class which is essentially a generic wrapper that contains a value and a counter. The counter is used to keep track of the number of references to the value. When the counter reaches 0, the value is freed. The CountedX class is used to wrap the values in the interpreter state. The interpreter state is a map of variable names to values. The interpreter state is modified to use CountedX instead of the raw values.

I went through each line of the interpreter and injected the reference counting logic.

Testing/Evaluation

To test, I added a --gc flag that can be used to enable/disable the garbage collector. I also added a --sf flag that, when toggled, will skip over all the free instructions (essentially treating them as noops). I also extended the --p flag to also print the heap size after at the end of the program's execution.

I used brench to compare the baseline brili implementation with the skip-free no garbage collection version and the skip-free garbage collection version. I used the remaining_heap_size as the metric to compare the implementations. The remaining_heap_size is the number of values that are still in the heap at the end of the program's execution. The remaining_heap_size is extracted from the output of the brili implementation using a regex option in brench. If the output matches the baseline, the brench output will display the extracted value which represents the remaining heap size. By comparing the remaining heap size, we can see that the skipfree version has a smaller heap size than the baseline version. Below is the brench output for the mem benchmarks.

brench.toml

extract = 'remaining_heap_size: (\d+)'
benchmarks = '../../benchmarks/mem/*.bril'

[runs.baseline]
pipeline = [
    "bril2json",
    "brili -p {args}",
]

[runs.skipfree]
pipeline = [
    "bril2json",
    "brili-gc --sf -p {args}",
]

[runs.skipfree_gc]
pipeline = [
    "bril2json",
    "brili-gc --sf --gc -p {args}",
]

lesson_tasks/l11/results.csv

benchmark,run,result
sieve,baseline,-
sieve,skipfree,1
sieve,skipfree_gc,0

bubblesort,baseline,-
bubblesort,skipfree,1
bubblesort,skipfree_gc,0

primitive-root,baseline,-
primitive-root,skipfree,5
primitive-root,skipfree_gc,0

adler32,baseline,-
adler32,skipfree,1
adler32,skipfree_gc,0

adj2csr,baseline,-
adj2csr,skipfree,4
adj2csr,skipfree_gc,0

basic,baseline,-
basic,skipfree,2
basic,skipfree_gc,0

max-subarray,baseline,-
max-subarray,skipfree,1
max-subarray,skipfree_gc,0

mat-mul,baseline,-
mat-mul,skipfree,4
mat-mul,skipfree_gc,0

fib,baseline,-
fib,skipfree,1
fib,skipfree_gc,0

vsmul,baseline,-
vsmul,skipfree,2
vsmul,skipfree_gc,0

quicksort,baseline,-
quicksort,skipfree,1
quicksort,skipfree_gc,0

two-sum,baseline,-
two-sum,skipfree,2
two-sum,skipfree_gc,0

eight-queens,baseline,-
eight-queens,skipfree,1
eight-queens,skipfree_gc,0

binary-search,baseline,-
binary-search,skipfree,1
binary-search,skipfree_gc,0

Difficulties

I was stuck for a while because I would double increment the reference of the pointer when I intially alloced it, this lead to the GC doing nothing and I was confused as I tripled checked my logic (though in this process I fixed other issues). Eventually when I was about to scratch my CounterX class and just use a seperate map I found the issue.

I intially tested on a handcrafted small example that would allocate a ptr and immediately free it (though this free instruction would be ignored when running with the --sf flag). After handling all the instr level logic with points, I ran the brench tests and found that I had a lot of remaining counts in the heap. I then realized that I was not handling the passing of ptrs across function calls (increment when passed in, and decrement when the stack is popped). After fixing this, I was able to get the remaining heap size down to 0 for all the benchmarks.

[ryanwmao]

@xalbt and I worked together on lesson 11.

Summary

garbage collection

Implementation

• We used the brili.ts code from the repository as a starting point.
• The bril-ts folder from the repository is also included in our local repo
• We implemented a simple reference counter within the Heap class to do our garbage collection. The new functions allow for reference counts to be incremented and decremented externally, and within the interpreter code, we call the functions as necessary to aid in garbage collection.
• We changed the free operation to a nop.

Our brench.toml:

extract = 'remaining_heap_size: (\d+)'
benchmarks = '../benchmarks/mem/*.bril'

[runs.gc]
pipeline = [
    "bril2json",
    "brili -p {args}",
]

Difficulties

• Navigating the original brili code was challenging at first, and was a big obstacle in our understanding of where to insert instructions and where to perform our operations.
• Overall, the implementation wasn't too challenging, but we can imagine that a more complex IR that includes scoping within the function and/or complex objects would be significantly more difficult to handle.

Testing

Results:

benchmark,run,result
sieve,gc,0
bubblesort,gc,0
primitive-root,gc,0
adler32,gc,0
adj2csr,gc,0
max-subarray,gc,0
mat-mul,gc,0
fib,gc,0
vsmul,gc,0
quicksort,gc,0
two-sum,gc,0
eight-queens,gc,0
binary-search,gc,0

[yxd97]

Summary

• I implemented a garbage collector with reference counting.
• Code, the new intepreter is named brili-gc.

Implementation

• Terminology: I will use the ``reference count of pointer p'' to refer to the reference count of the object that p points to, just for simplicity.
• I first added a refcnt map from pointer bases to numbers in the Heap class to keep track of reference counts (RCs), with three new member functions incrRC, decrRC, and clearRC to add RC by 1, decrease RC by 1, and clear RC to 0, respectively. The Heap's alloc function was set to automatically increase the RC to 1 for newly allocated pointers.
• Then I went through all senairos (instructions) that can change the RC:
  • p = alloc size will set the RC of p to 1. If p was previously pointing to an object, the RC of that object is decreased by 1.
  • p = id q will increase the RC of q by 1. If p was previously pointing to an object, the RC of that object is decreased by 1.
  • p = ptradd q offset will see if p was previously pointing to an object, and decrease the RC of that object by 1 if true.
  • p = load q will see if p was previously pointing to an object, and decrease the RC of that object by 1 if true.
  • p = call @... will do the same if the function returns a pointer.
  • store p val will check if p points to a pointer (pointer to pointer). In that case, the intepreter will check if the target pointer points to any object. If so, it will decrease that object's RC by 1.
• Although we do create a new pointer from ptradd, the RC is not increased. This is to account for the fact that only freshly allocated pointers and its aliases (produced by id) points to objects, and thus can be freed. This is done by adding a freeable boolean field in the Pointer type.
• The garbage collector will launch whenever a function returns. Upon return, all pointers that are local to this function will be killed (their RCs are cleared to 0), but if a pointer is an alias of a global pointer, the RC is decreased by 1. After setting the RCs, the GC will scan through the heap to add objects with 0 RC to a free list. To account for pointer to pointers, if a pointer object is marked as free, the RC of object it points to will be decreased by 1; the scanning will iterate until there is no change in the free list. Finally all objects in the free list is freed.

Testing

• While building the grabage collector, I greated small test cases in tests/basic to verify the functionality. To see what is happening, I added a -t flag to brili-gc which will print out function call traces with heap contents and the actions of the GC to stderr.
• The brili-gc intepreter is also tested on all programs from the mem suite of bril benchmarks. My GC is able to collect and free all objects upon the return of main. (As a reference, all *.err files under tests/mem are empty)

Challenges

The most challenging part is to account for all possible cases that may change the reference counts. Especially, it could be hard to realize that the pointers produced by alloc are different from ptradd. Another challenge is to figure out which pointers to kill upon function return. I have to make sure the RCs of function arguments, return values, and their aliases are set correctly.

[alifarahbakhsh]

Repo

I have implemented a simple reference counting garbage collector for Bril. It works correctly for all of the benchmarks in the canonical mem benchmarks, except for one. I did not have time to investigate the issue, although I suspect it has something to do with how I handle function calls.

The implementation was fairly straightforward once I found my way around brili.ts. The only challenge I had was realizing that the act of returning from a function is important to consider, and even without ret one should collect unreachable "objects". It would have been more challenging if pointers could point to pointers in Bril.

[stephenverderame]

Summary

Repo

I implemented a tracing, generational garbage collector. The nursery generation used a bump allocator and the mature generation used a hash map mapping "pointers" to Rust-allocated memory buffers. One slight modification from traditional generational garbage collection is that each generation can be collected independently. Thus, having multiple, smaller generations would bring the behavior closer to an incremental collector on the granularity of generations. The current implementation just uses two, however it is as simple as changing a constant and adding a new object into an array to change the number and size of the generations.

Implementation

I modified the brilirs interpreter to use my gc library, which is a drop-in replacement for their existing Heap struct. Notably, a MemoryManager always defines a free function, however the GC just turns this into a NOP while the original heap, frees the memory. This choice also allows not having to have different tests that work with brili and ones that work with the modified brilirs since brili asserts that all memory is freed and no double frees occur.

For the remembered set, I took some ideas from card tables and the unified GC paper. I had each cross-generation pointer map surjectively to a reference count. This mapping is done by simply taking the remainder of the pointer divided by the number of reference counts being kept track of. Any pointer that maps to a nonzero reference count would be considered a root. Therefore, this implementation uses tracing within a generation but reference counting for cross-generation pointers. This also means that cross-generation cycles cannot be collected, but this isn't too big of a problem because in this case, they'd all eventually end up in the final generation and be cleaned up there.

Testing

For testing, I made sure that all benchmarks with the GC had the correct behavior. Moreover, I introduced memory statistics which keeps track of things like number of promotions, number of live values in the generation, remembered set size, allocated memory in a generation etc. I created a few small tests to ensure that things like allocated values and remembered sets were being updated correctly.

Challenges

One difficulty was correctly handling the promotion of allocations and the case when we want to allocate memory to a generation but there isn't enough space. In this case, we need to first run a collection, promoting any values into allocations of an older generation which may trigger more collections. Then, we must retry the allocation. If this fails again, then we have to pass the allocation to an older generation, hoping that they have more space. If we keep passing along an allocation until there is no more generations, we must then return an error.

Overall, this logic was a bit involved.

Another challenge was implementing the write barrier to correctly update the reference counts for cross-generation references.

Another key thing not to forget is to update the roots and other generations for the new pointer location when a promotion occurs.

[zachary-kent]

Summary

• Collaborators: @zachary-kent , @rcplane, @Enochen
• We implemented a reference counting garbage collector in the TypeScript implementation of brili. Modified brili and brench file.

Implementation

• We modified the State type, extending it with two fields: rc and freeCandidates:
  • rc : Map<number, number> maps base pointers to their reference count
  • freeCandidates : Set<number> is a set of memory locations with reference count 0 that have not been freed
    These fields maintain all of the information needed to track the reference count of memory locations
• Then, we implemented incrementRc, which increments the reference count of a memory location and removes it from the freeCandidates set, if present.
• We also implemented the freeCandidates function, which frees every pointer in freeCandidates. Freeing these candidates may decrease the reference count of other pointers, which become elgible for freeing if this count drops to 0. We implemented this using a worklist algorithm, where the worklist is initialized to freeCandidates. While the worklist is not empty, we pop a pointer p from the worklist. We free the pointer p and process the process the descendants of p in the points-to graph, if there are any. First, we check the type of the data that p points to. If this type is not itself a pointer, we continue to the next iteration of the loop, as p has no descendants in the points-to graph. Because p may have size greater than 1, we have to iterate over every pointer in this array, decrementing their reference count and adding these pointers to the worklist if their reference count drops to 0. This way, we process "cascading" decreases in reference counts.
• We implemented decrementRc, which decrements a pointer's reference count and places it in freeCandidates if its reference count drops to 0. It does not, however, free the pointer itself.
• We now modified the execution of the interpreter to maintain reference counts. When executing a value operation, we decrement the reference count of the pointer previously stored to its destination (if any), and increment the reference count of the pointer newly stored there (if any). We also implement the same logic for store instructions, incrementing the reference count of the pointer previously stored at the target location (if any), and incrementing the reference count of the pointer newly stored there (if any). When executing a function call, we also increment the reference count of all pointer arguments to the callee; when the function returns, we decrement the reference count of any pointers stored as local variables, including the parameters.

Testing

• Fortunately, brili already has built-in functionality for checking memory leaks and illegal frees. Thus, to test our garbage collector, we modified brili to treat every free as a nop and used brench to run every benchmark, confirming that we had no memory leaks or illegal fress.

Difficulties

• There were many corner cases to worry about. We enumerate some of the tricky ones here:
  • Value operations where an identifier is overwritten with the same base pointer it stored previously. If pointers are freed "eagerly," first decrementing the reference count of the pointer can cause it to be freed when its reference count is 1.
  • Returns from function calls; on returning from a function, we decrement the reference count of all locals, including the returned value, if any. This may cause the reference count of a returned pointer to drop to 0 and it to be freed despite being used by the caller.
• Both of these issues were addressed by processing decrements "lazily" using the above worklist scheme; we free potential candidates only after each instruction is completely excecuted, preventing premature frees.

[MelindaFang-code]

Summary

Implementation of Garbage Collection using reference pointer gc-brili.ts
@collinzrj and I worked together for this task.

We choose reference counting for bril typescript interpreter because it most straightforward. For Bril there are few cases to consider as what type of instructions would constitute as necessary to update the reference counter. After discussion we think these are the cases

• Id, if we assign a pointer to another value
• Array, in which we would be allocating a continuous block of memory, and each of the entry might be referencing another pointer
• Load/Store, since the pointers may themselves store reference to pointers, so any load or store operation would possibly increase the reference count of the base address
• If we are overwriting an existing pointer with another pointer value, then we would possibly loose that reference, so whenever reassigning pointer values, we should check if the destination already points to a pointer and decrement its reference count.

Another concept we spent some time to figure out is what happens when sth goes out of scope, e.g. exit from function call, and how to deal with those variables. We used a pretty brute-force approach by keeping a pointer_stack that keeps track of the pointers before entering and after finishing the function call. Then we go through the stack and decrease the reference count of pointers. An edge case we encountered here is that for functions that return pointers, the pointer value should still remain and its reference count shouldn't be decreased to zero and removed. To do this the sequence of updating the reference count matters (we need to first increment the RC of the returned ptr and then iterate through the stack and decrement the rc of ptrs on the stack)

Test

we mainly take advantage of the existing benchmark bril test, and also added a few small test cases for the corner cases and debug purposes. Main tools we use are 'turnt' to compare the experimental outcomes with the manual free brili.

• We add test case to test an example of overriting pointers like this:

ptr = alloc ...;
# do stuff with ptr
free ptr;
ptr = alloc ...;
# do other stuff with ptr
free ptr;

• we remove all the free instructions from the benchmark folder, and see if the function still produce the same results. This proves that our algorithm works well with handling functions,

Hardest Part

we encountered some problem with typescript first since it has some weird behavior when trying to access a map using the bracket '[]' operator, causing the values we read become undefined.

In addition, it is quite hard to figure out the corner cases. For instance, while developing we also find out that the main function call procedure is different from normal function calls, and should be dealt quite differently.

[jiahanxie353]

Summary

Modify brili.ts to support reference counting for garbage collection

Implementation details

I added several functions to the Heap class to increment/decrement reference count for memory location base and modify the size of the Heap accordingly. For the instructions that might change the reference count, namely id, load/store, alloc, ptradd, I modified the count.

Testing

I used brench to test my implementation using benchmarks. And I used profiling to print the heap size after program executing to compare between the original brili and my brili-gc. My brili-gc will free all objects on the heap that were otherwise not freed by the original brili.

Challenge

Learning TypeScript is one of the difficulties I had when I started the task, but later I got the hang of it. The task per se is straightforward but requires careful thought on incrementing/decrementing the pointer count for every possible cases. In addition, function calls and ret is tricky, in which we need to decrement the stack variables' reference count.

[obhalerao]

I worked with @SanjitBasker on this project.

Summary

Repo link

Implementation details

We modified brili.ts to support garbage collection. To do so, we implemented a version of reference counting in which memory blocks are placed in a queue to be freed at a later time once their reference count hits zero. Then, whenever a new object is allocated after a given object is freed, the garbage collector will go through the queue of blocks and free up the blocks until enough space is freed to support the new memory block before allocating the memory block. (Admittedly, from the way the brili interpreter allocates memory, this is a bit superfluous, but we wanted to simulate how a real garbage collector would work when interacting with memory directly.)

Testing

To test, we took all the benchmarks that use memory, ignored all the free instructions, and ran our new interpreter to ensure that no blocks were left unfreed by the end of the program. To do so, we used brench to ensure that the two programs produced equivalent outputs for all the valid test cases and they did not error for a lack of removing all the objects on the heap.

Challenges

A particular challenge we faced was how to deal with functions that return a pointer; our initial approach was to decrement the count of all the local pointers when returning from a function, but it turns out that we did not want to do this exactly for pointers that were returned. To solve this, we still decremented the reference count of pointers that were returned, but we did not schedule it to be freed if the reference count reached zero (since it would escape the function). This proved to be sufficient for the benchmarks given.