Lesson 11: Memory Management

[sampsyo]

These tasks are about implementing a garbage collector!

[michaelmaitland]

Introduction

I implemented a reference counting garbage collector in the bril-ts interpreter.

Implementation

The Collector

I created a class ReferenceCountGarbageCollector that has the following functions:

• alloc
• dec
• decAll
• inc
• incAll
• assign

I kept track of counts to objects using a map with key of Key.base and value corresponding to the counts referencing that Key. We use the Key.base field as a key to this map since different offsets into the same entry in the heap correspond to the same object.

alloc initializes the count to that object to 0.
dec decrements the count to a given object and frees the object if the count hits 0.
decAll calls dec on all pointers in the specified Env
inc increments the count to a given object
incAll calls inc on all the pointers in the specified Env
assign checks if the Ident is in the environment and if that Ident is of pointer type. If so it calls dec on the Key that that Ident holds. Then we call inc on the Key that is being assigned.

Using the Collector

There are a few places where the collector must be put to use. The collector must be used for the following instructions:

• alloc
• ptradd
• id
• ret

For an alloc inst, we use the gc.alloc and gc.assign functions.

For a ptradd function we use gc.assign

Although not entirely clear that this was allowed by reading the docs, the interpreter allows us to call id p where p is a pointer type. For this reason, we must use the gc.assign function.

Lastly we must handle the case where a function calls ret p where p is a pointer type. We also use gc.assign here.

In addition to this, we use the incAll and decAll in the new function environment before a function call. This way, all passed arguments trigger an inc call, and all variables at the end of the function call dec.

The Free instruction

Now there is no need for the free instruction since garbage will be collected. I could have left it to actually free in the heap but opted to make it act as a nop. The drawback to this is that acyclic garbage may not be freed and we cannot free certain memory until the end of the function since there is no nullptr in bril.

The reason I decided to make it a nop will be detailed in the testing section.

Pointers to Pointers

I did not implement GC in the case where there are pointers to pointers since I do not recursively deal with children. I did not check and see if it was even possible to create a pointer to pointers in bril.

Testing

The Free Instruction

As explained above, free acts as a nop. This made it extremely easy to run turnt on all the benchmarks without having to remove the free instructions. If the collector did not do its job correctly, the check to make sure the heap has been emptied in the interpreter causes the interpreter to throw an exception.

Turnt

I used turnt to make sure that all of the benchmark files passed their test. This checked to make sure that I did not modify the semantics of the program since turnt checks to make sure that the expected output is printed. Additionally, turnt would fail if not all the memory was freed as described in the previous section.

I am passing for all benchmarks.

Test Cases

I also added support for 6 test cases:

no-free.bril

@main {
  ten: int = const 10;
  myptr: ptr<int> = alloc ten;
}

This test case makes sure that memory is automatically freed. Otherwise, the interpreter would throw an exception.

loop.bril

@main {
  ten: int = const 10;
  one : int = const 1;
  ptr1 : ptr<int> = alloc ten;
  i : int = const 0;
.loop:
  cond : bool = lt i ten;
  br cond .body .done;
.body:
  ptr2 : ptr<int> = ptradd ptr1 one;
  i : int = add i one;
  jmp .loop;
.done:
  free mtptr;
  print i;
  ret;
}

This test case makes sure that gc.assign works as expected. Initially, I was incrementing ptr2 over and over without decrementing it because it was doing a ptradd to the same variable over and over, causing me to never free at the end.

gc-call.bri

@f {
  ten: int = const 10;
  myptr: ptr<int> = alloc ten;
}

@main {
  call @f;
}

This test case checks to make sure that we increment and decrement all variables at the start and end of a function call.

double-alloc.bril

@main {
  ten: int = const 10;
  myptr: ptr<int> = alloc ten;
  myptr: ptr<int> = alloc ten;
}

This case checks to make sure we handle the case where we alloc into the same variable multiple times. The second alloc makes the first alloc freeable.

id-ptr.brill

@main {
  ten: int = const 10;
  myptr: ptr<int> = alloc ten;
  myptr2 : ptr<int> = id myptr;
}

This test case makes sure that we are doing a gc.assign call on an id instr.

ret-alloc

@f : ptr<int> {
  ten: int = const 10;
  myptr: ptr<int> = alloc ten;
  ret myptr;
}

@main {
  myptr : ptr<int> = call @f;
}

This test case makes sure that we do a gc.assign when we are returning a pointer from a function. Getting this test case was a little tricky. I experimented with where to do this check in the interpreter.

Summary

Overall, I'm pretty confident with my code since I have identified many specific cases where the collector must be used and why it needs to be used. Also because it passes for all the benchmarks.

I also enjoyed this project. I felt that my solution was clean and modular. This project made me think thoroughly how to use the collector. In class we discussed how to implement the collector but didn't talk that much about how to use it. I had to experiment, test, and iterate to a working solution. This was my favorite task so far.

[sampsyo]

Good call on this:

Although not entirely clear that this was allowed by reading the docs, the interpreter allows us to call id p where p is a pointer type. For this reason, we must use the gc.assign function.

It makes sense to allow pointer assignments like this, so cool that this works.

FWIW, this would be a good place to expand, hypothetically:

I did not implement GC in the case where there are pointers to pointers since I do not recursively deal with children. I did not check and see if it was even possible to create a pointer to pointers in bril.

That is, there is nothing that prevents alloc and whatever from working on types like ptr<int>, so you can have heap-allocated pointers to heap-allocated data. Following these recursive references is something that a "real" reference counter would need to do when freeing data whose count drops to zero.

Super awesome that everything appears to work (and actually free all the memory) on all the benchmarks when the free instruction is turned into a no-op. That seems like a great way to stress-test the effectiveness of a GC. (Maybe we should add some sort of benchmark with a reference cycle in it to trip up future generations of GC implementors…)

[anshumanmohan]

@5hubh4m, @ayakayorihiro, and @anshumanmohan worked together on this assignment, and our work is here.

Implementation

We implemented a straightforward stop-the-world tracing collector with one space and no compaction. We found this assignment relatively manageable. Our work is in two broad parts:

Tweaks to Memory

We need a few edits to the memory model to make it amenable to garbage collection.

The main change is in Env, which goes from
type Env = Map<bril.Ident, Value>;
to
type Env = Map<bril.Ident, Value>[];.
That is to say, an array of maps that simulates the call stack. This creates some straightforward cleanup downstream.

The Actual Collection

A Heap contains
private readonly storage: Map<number, Value[]>
and a Value is an ADT:
Value = boolean | BigInt | Pointer | number;.
This means that we need not be conservative; we can precisely follow Pointers to check for reachability.

We change the existing free operation into a no-op. Every 10,000 instructions trigger a collection, and the end of the main function also triggers a collection. A garbage collection is a trace, which lists everything that is to be freed, followed by collect, which essentially calls the dearly departed free operation on each of these. The meat of the matter is clearly trace, so we discuss it a little further.

The method trace identifies roots by walking over the given environment and picking out values that were made with the Pointer constructor. These go into the "grey" set. Everything else goes into the "white" set. We follow a worklist strategy, iterating over the grey locations and promoting locations from white to grey and grey to black in the usual way. This buys us recursive power without some of the hassle of actual recursion.

Testing

We tested our work on the bril examples in:

1. the benchmarks directory
2. the test/mem directory

Of course, only a small number of the benchmarks use the memory extension. We found that outputs were unchanged, which is good, and that no memory leaks were introduced, which is better.

Challenges

We thought this went pretty quickly. The main challenge was getting used to some of the funkier syntax and language decisions that the TypeScript language makes.

[sampsyo]

Excellent! I am thrilled to hear that doing tracing on the current implementation of the heap in brili was not too complicated. Sounds great!

With apologies, one tiny terminology nit from GC-land: you said that "no memory leaks were introduced," but actually, people usually define leaks in terms of liveness rather than reachability. A consequence is that people writing code in GC'd languages nonetheless sometimes worry about memory leaks, which can only arise from accidentally keeping a reference to something that you didn't mean to keep a reference to (and which you are certain you will never access again in the future). So your GC may have collected all the garbage, but that doesn't necessarily mean that all the programs are leak-free!

One interesting example of recent research along these lines is the BLeak memory leak detector for JavaScript/browsers.

[5hubh4m]

That’s fascinating and something I was thinking about; and its not even hard to do. If you allocate a big array in your main but you only ever use it in the first half of execution, you will never free it until the end of execution.

[gsvic]

I implemented a reference count garbage collector. My implementation can be found here.

Details

I implemented a new class called GC. The main structure that I am using to keep track of the reference counts is the following map:

private readonly referenceCounts: Map<Key, number>

To make my implementation minimally invasive, I created the following handleAssignment method which invoked when the GC needs to do something.

handleAssignment(dst: string, state: State, pointer: Pointer)

I've added this call only for the id and alloc instructions. Given the dst string, my method first checks if there is already an object pointed by that variable name, and if so, it decrements that object's counter. At the end, it will either insert a new reference for the given pointer or increment the already existing one. I also implemented a clean method, which is invoked at the end of the program's execution. This method checks if there are any references for any allocated object, and it frees the memory for each of those objects.

clean(state: State)

Backwards Compatibility

Keepfree support

I kept the support of free along with the implementation of the garbage collector, as I thought of that as a hint that the developer could give while writing the code. In case that free is explicitly called, then the corresponding deference will be deleted from the garbage collector by invoking the removeReference method.

Disabling free

It is possible to disable the free command by just providing -df as an argument to bril, like bril -gc. df can be used along with gc as bril -gc -df (enabled garbage collection and disabled free).

Usability

The garbage collector can be easily enabled by adding the -gc argument when calling brill, like bril -gc.

Testing

I run all the tests under the benchmarks directory by providing a couple of different combinations of the gc and df methods. I have also added two tests under test/gc that do some allocation using alloc but they never free.

Default

In the first test, I am just testing using thebril command without providing anything else. All tests are passing, while the execution looks pretty much the same as before my changes

Using -gc only

All the tests passing as well, the GC is enabled while the free is also working along with the collector.

Using -df only

With free disabled and without enabling GC, as expected, every benchmark that has at least one alloc fails with the following error

error: Some memory locations have not been freed by end of execution.

Using -gc and -df

The final experiment using GC only, while the free is deactivated. Again, all the tests are passing while some memory is deallocated during execution, verified with some extra logging I put during debugging my implementation.

[sampsyo]

Awesome; this all sounds great! Sounds like everything went as expected.

I have a couple of questions on this detail:

I also implemented a clean method, which is invoked at the end of the program's execution. This method checks if there are any references for any allocated object, and it frees the memory for each of those objects.

First, it kinda looks from your code like clean works by iterating over all the reference counts and freeing the "zeroes." In that sense, it seems like this approach is ever so slightly toward the tracing side of the spectrum from RC, according to this week's paper's classification! That is, instead of immediately freeing something as soon as you drop its reference count to zero, you're kinda "batching" these up into a second pass. Is that right?

Second, does clean work recursively? I couldn't quite tell what would happen if you have a pointer to a pointer, and the first pointer's reference count goes to zero.

[gsvic]

Good question! So, my clean method is executed after the main method is evaluated. For this reason, clean does not remove only the zeroes, but any element in the referenceCounts map, as there might be still references in an allocated object before the end of execution, and in that case the if (!heap.isEmpty()) check would fail. Is that approach correct?

Second, the clean method does not work recursively, it just traverses the referenceCount map. However, as we keep track of every object that is either allocated (with alloc), or aliased (with id), the referenceCount map should include all allocated objects.

Let me know about your thoughts!

[sampsyo]

Ah, I see! I guess a consequence of running clean after main finishes is that you won't be freeing stuff along the way—only at the very end, after the program is done, right? The odd thing about this is that it would be equivalent to not do reference counting at all and just free everything as the program finishes.

But since you are doing some freeing at run time (namely here), it's not 100% clear to me why freeing within clean is necessary at the end too…

[gsvic]

Hm, I feel like I miss something here. So, I'll give an example of how my GC would work for the following example

@main {
  a: int = const 16;

  c1: ptr<int> = alloc a; //  (obj1 -> ref_count: 1)
  c2: ptr<int> = alloc a; //  (obj1 -> ref_count: 1, obj2 -> ref_count: 1)

  c1: ptr<int> = id c2; //    (obj1 -> ref_count: 0, obj2 -> ref_count: 2)
  // obj1 is deallocated
  c3: ptr<int> = id c1;       (obj2 -> ref_count: 3)

  ret;
}

In this case, after c1 reassignment the reference count of obj1 drops to zero and is deallocated. However, there are still three references to obj3 before execution finishes. So in that case, how obj3 would get deallocated without calling clean at the end, as long as its reference count never drops to zero? Probably I miss something in RC logic.

[sampsyo]

Ah, I get it now! The issue in this case is the variables that "survive" to the end of the function—not only main, but also other functions. At the point where they ret, all the "roots" (pointer-typed local variables) need to do an RC decrement.

So a more standard way to do this would entail:

• clean is called at the end of every function, and processes that function's local variables.
• clean, instead of freeing everything in the RC map (ignoring reference counts), just decrements the reference count for all of those local variables. (This may trigger deallocations when counts drop to zero.)

[JonathanDLTran]

Summary

Code is at: code
Benchmarks used at: benchmarks

I implemented ismple reference counting for the Bril language, including the memory extension. To run, you can do bril2json < test | brili-gc -p args
replacing test and args appropriately. You will have to use the brili-gc typescript I wrote, run yarn, then yarn build, yarn unlink and then yarn link to have the executable for brili-gc.

In this assignment, because I focused on reference counting, I only needed to look at certain instructions. I considered id, alloc, free, store, load and ptradd instructions. To allow for the counting analysis, I created a map from pointers to the count for that pointer, and also created a map allowing pointers to point to another pointers.

Free is trivial, and eliminated. Alloc adds a new pointer, and a counter is incremented to be 1. If there was a prior pointer to the variable that was given an allocation, that prior pointer is decremented. Anytime a decrement occurs, it is done recursively, such that if an object's counter reaches 0, if the object itself points to another object, that other object also has a recursive decrement operation applied.

Stores cannot change the counters for any pointer. However, a store may allow a pointer to reference another pointer. The map of pointers pointing to other pointers is updated here.

Loads can allow another variable to reference a pointer, if a pointer value ends up being loaded. This means loads increment a counter for a value if the value is a pointer.

Finally, if ptradd ends up assigning a different variable to a pointer, then the pointer gets its counter incremented appropriately.

Testing

To test, I used brench to compare just the brili interpreter, versus the brili-gc interpreter, in which the free operation has no effect. I tested over every benchmark in the bril repository, and made sure the outputs were identical in both and there were no memory freeing issues.

Difficulties

Learning Typescript was a little difficult. In particular, I was not aware Typescript did not have keep types at runtime, which made it hard for me to figure out how to discriminate between various union types. I later ran into issues trying to figure out whether a value was a bigint, number or boolean, which caused some debugging trouble as well.

A problem more related to reference counting was how I needed to free all references at the end. Because reference counting is conservative, it leaves some references at the end that it cannot eliminate at runtime. I forgot to do this at the end of the program and had to add this in.

I also initially failed to recursive update the counts for chains of pointers. I also had an issue where if I have a pointer to an array, I failed to check all the elements of the array, which could be pointers. I fixed this issue, by having the pointer map point to a list of potential pointers, which in the array example would be the instantiated pointers in the array.

Perhaps something that would be interesting to study would to figure out better schemes to do reference counting. In particular, it would be interesting to see if there are better places in the program to defer reference counting to. For example, rather than doing reference counting all at once, it would be interesting to do it at certain locations in the program.

[sampsyo]

Awesome. Addressing loads and stores (in pointers to pointers) seems like the key to supporting full-blown RC on the entire heap.

Because reference counting is conservative, it leaves some references at the end that it cannot eliminate at runtime.

I think what you mean here is that the pointer-valued stack variables (roots) need to be handled at the end of a function call? That is, when popping the stack frame for a function, all those roots need to trigger an RC decrement as they are destroyed.

[JonathanDLTran]

Yep, as I understand stack variables need to be eliminated unless the pointer is returned from the function.

[zzzDavid]

My implementation is here.

Description

I extended the brili interpreter with a reference counting garbage collector. The idea is to update the reference count whenever a instruction that could change the reference count executes:

• alloc: set reference count to 1
• id: if it copies a pointer, the reference count increase by one
• call: function calls are slightly tricker. When a function returns, the pointers allocated inside will expire unless it is returned. To differentiate the pointers allocated outside the function, I add one to all the reference count before calling into the function.
• ret: when a function returns, we decrease all the reference count by one, so that pointers allocated locally has count zero and will be collected. One exception is when ret's argument is a pointer, such as in the mat-mul.bril benchmark. In this case we increase the ret's argument reference count by one before decreasing all, so its reference count ends up as one and won't be collected.

Implementation

I added the GarbageCollector to the state struct:

type State = {
  env: Env,
  readonly heap: Heap<Value>,
  readonly gc: GarbageCollector,
  readonly funcs: readonly bril.Function[],

  // For profiling: a total count of the number of instructions executed.
  icount: bigint,

  // For SSA (phi-node) execution: keep track of recently-seen labels.j
  curlabel: string | null,
  lastlabel: string | null,

  // For speculation: the state at the point where speculation began.
  specparent: State | null,
}

At the end of each function, gc.freeall() is called to find pointers with zero reference count and free them.

Test

I disabled the free instruction in the interpreter by doing this. Then I run the benchmarks with

$ turnt benchmarks/*.bril

All testbench cases passed, which indicates that the garbage collector doesn't alter the result or break the program.

[sampsyo]

Sounds great; I'm glad this worked out! I have one question about this design decision:

At the end of each function, gc.freeall() is called to find pointers with zero reference count and free them.

Any particular reason to choose this instead of freeing stuff immediately when its reference count drops to zero, as in a "pure" RC scheme? Is the idea just to batch up some of the overhead?

[zzzDavid]

Yes it's just to batch up the free operations

[charles-rs]

My implementation is here

Description

I modified brilirs to support a simple mark and sweep garbage collector.
The nice types for values make this relatively simple, as it is clear what is and isn't a pointer, and each pointer contains the "base" which is the thing returned from alloc, so we don't need to worry about freeing the middle of a block.

The main design decision I had to make was when to run the garbage collector, which for simplicity i run before every allocation. In reality, this could be reduced to every nth collection, but for the sake of a toy implementation it was convenient to see it happening every time (more abt this in testing)

Implementation

i had to extend the Environment type to include all of the variables in scope in parent functions, as they also need to be used as roots for the trace. Then, i made a free_garbage function which frees either the reachable or unreachable things, depending on a flag. It uses the typical white/grey/black graph traversal to determine reachability.

The reason for the functionality of freeing all reachable things was that I call this at the end of main so that the check for unfreed memory is still helpful

Testing

To test this, first we need to determine what we want it to do. We want to remove all the frees, and have the same behavior, as well as not having significantly increased memory overhead. (It would be possible to just free everything at the end of main on these benchmarks probably...).

Part 1 of testing was using turnt on the benchmarks: I removed all of the frees, and ensured that they had the same output. They didn't, since dyn instr count was different, so i turned off that check, and this worked without too much issue

Part 2 was to make sure that things were actually being freed when they should. For this, I added prints to the mark sweep process, and then wrote some tests that alloc in a loop, and then inspected the prints. The frees were happening when i wanted them to, and were happening recursively, so all good.

Difficulties

The above discussion may trick you into thinking this was easy, but I assure you it was not. I had never even seen rust code till a few days ago, and the learning curve was quite steep. I ended up passing the old environments around via deep copy, as I could not figure out how to use a stack like data structure to share them. In the future, I will attempt to learn languages by reading tutorials, and not by working on preexisting projects.

[sampsyo]

Sounds great! Good idea to add a set of all roots (from all stack frames) to the environment.

Then, i made a free_garbage function which frees either the reachable or unreachable things, depending on a flag. […] The reason for the functionality of freeing all reachable things was that I call this at the end of main so that the check for unfreed memory is still helpful

Any particular reason this happens only at the end of main? It seems like things could be freed whenever a function returns, i.e., when the set of roots associated with a given stack frame cease to be roots.

[charles-rs]

ah, i think i said this in not the most clear way:
Every time you call alloc, unreachable things are freed.
At the end of main, unreachable AND reachable things are freed, as the interpreter doesn't really have a sense of returning from main

[sampsyo]

I think I see, but how about this somewhat "purer" alternative: don't treat main differently from any other function. When any function returns, remove its variables from the root set and do a collection. So when main returns, the root set will be entirely empty. So when you do a "normal" collection (freeing the unreachable stuff), then everything will be freed.

Not a big deal, of course; just trying to think through the somewhat odd practice of freeing reachable objects.

[chhzh123]

Since I am an aficionado of Python, I did not use the TypeScript-based interpreter for this task. Instead, I built a Python-based Bril interpreter bril-py and implemented the garbage collector in that Bril Virtual Machine (BVM) :) Actually, BVM is very straightforward to implement, and it did not take me much time to make the whole thing work. The code can be found here, which is very concise and less than 200 lines.

Bril-py Interpreter

Using bril2json, we can obtain the JSON representation of the Bril program, which can be directly used as the input of the interpreter. Basically, the interpreter is a stack machine, but since the instructions in JSON representation have already had the operand information, we do not need to evaluate the expressions using a real stack, which greatly simplifies the work of the interpreter. However, a frame stack is needed to maintain the context of a function. I created a Frame class to record the data, instructions, and blocks in the function.

The virtual machine takes the main function as the top-level, append the arguments into the frame as initial data, and then starts evaluating the frame. The eval_frame function is essentially a dispatcher that takes in an instruction and calls the corresponding function to evaluate the instruction. Except for common binary instructions and control flow instructions (jmp and br), there are two more things to mention:

1. Function calls may trigger creating a new frame, and the new frame will be pushed into the frame stack to evaluate. The frame will be popped out and destroyed when the function returns. This is also where memory management (garbage collection) happens.
2. Due to time limitations, I did not use heap to model the dynamically allocated memory. Instead, I used a simple linear memory model to simulate memory allocation. I also added a memory leakage detector in my interpreter, so if there exists some memory that is not freed by the end of the program, my interpreter will throw an error. Similar to the double free cases, it will also raise an error.

I used the tests in previous assignments to test the correctness of my interpreter, and they all perform well and output the same results as the original Bril interpreter.

Garbage Collector

After I built the bril-py interpreter, the garbage collector can be easily plugged into it. I implemented a reference counting garbage collector. Only several instructions may cause the references to change:

• alloc: Set the reference count of the allocated memory as 1. But if the variable overwrites the previous memory as shown in the following case, the reference count of the previous memory should be firstly decremented.

  one: int = const 1;
  a: ptr<int> = alloc one;
  a: ptr<int> = alloc one;
  

• free: This directly set the reference count of the memory to 0, but should not be used with automatic garbage collection.
• ptradd: This also leads to the reference count of the memory that the base pointer points to. Also be careful about the reassignment that may cause the original pointer invalid.
• id: If the operand is a pointer, the reference count is simply incremented by 1.
• ret: Those memory allocated in the function should be freed when they leave the function scope. There is one exception: if the function returns a pointer to allocated memory, then this pointer should not be freed.

  @foo : ptr<int> {
    one: int = const 1;
    p: ptr<int> = alloc one;
    ret p;
  }
  
  @main {
    p : ptr<int> = call @foo;
  }
  

I removed the free instructions from the Bril program and tested if the garbage collector works correctly. Those test examples can be found in the test folder. Some of them are from previous assignments, and some of them are from the bril benchmark. The output is the same as the original one, showing my garbage collector can indeed automatically manage memory.

In the beginning, I wanted to do something fancier, but I found Bril did not have those advanced language features, so even having a strong garbage collector, there are no test programs in Bril that can leverage these features. For example, I had a hard time thinking about how to construct a reference cycle in Bril, but later I found it seems it is impossible since Bril does not have OOP facilities and does not allow pointers pointing to pointers. For a similar reason, tracing garbage collectors may not be that useful. Common Bril program can be executed in less than one hundred lines, and function calls are also very limited, which means most of the garbage collection can be done when the function returns.

[andreyyao]

I think pointers to pointers can be constructed in bril?

[sampsyo]

Awesome; pretty cool that it wasn't too hard to implement a new interpreter from scratch!

I was curious about what you meant by "linear memory model" here:

2. Due to time limitations, I did not use heap to model the dynamically allocated memory. Instead, I used a simple linear memory model to simulate memory allocation.

It looks like what you have is a flat array of values. Allocation works with a "pointer bump," i.e., new allocations always go at the end of memory. Freed memory is never reused. This is a perfectly good way to implement an accurate heap model, so I don't think you have to worry about correctness! The only problem, of course, is the space wasted by freed memory; to make this more "realistic," you'd want to use a free list or something to allow yourself to allocate into that freed space sometimes. Or else do compaction.

Also, @andreyyao is right that pointers to pointers are possible (you just need foo: ptr<ptr<int>> = alloc 1, for example). So it is probably possible for your reference counter to leak memory when doing loads and stores to these pointers. Fortunately or unfortunately, I don't think any current benchmarks do that…

[chhzh123]

Thanks @andreyyao for pointing it out, and thanks @sampsyo for the comments!

You just need foo: ptr<ptr<int>> = alloc 1, for example. So it is probably possible for your reference counter to leak memory when doing loads and stores to these pointers.

Yeah, it is tricky though... Maybe keeping track of the base object is necessary. The garbage collector needs to recursively find the memory that is not storing pointers. For example, for a: ptr<int> = alloc 10; pa: ptr<<ptr<int>> = alloc 1; store a, pa;, we need to know pa's final destination is array a, and increase the reference count of a by 2 (one for a, and another for pa). Not sure if this is a right way to tackle this situation.

It looks like what you have is a flat array of values. Allocation works with a "pointer bump," i.e., new allocations always go at the end of memory. Freed memory is never reused. This is a perfectly good way to implement an accurate heap model, so I don't think you have to worry about correctness! The only problem, of course, is the space wasted by freed memory; to make this more "realistic," you'd want to use a free list or something to allow yourself to allocate into that freed space sometimes. Or else do compaction.

Right. This is what exactly I did in my interpreter. Yeah, to reuse the freed memory, I need to construct a linked list or cyclic array to make the "pointer bump" go backward.

[sampsyo]

I think the idea is that every time to store to a pointer-valued memory location, you'd need to do something analogous to what you do for id: (1) see what the old pointer value was pointing to and decrement its reference count, and (2) increment the reference count to the new thing. For the first step, yeah, you'll need a way to know—for every pointer—where to find the relevant reference count.

[atucker]

My code is here.

Implementation

I modified the typescript implementation of brili here.

My first thought was that the easiest way to do this would be to just modify the Heap object directly, but then I realized that that's kind of at odds with my interpretation of the assignment -- I'm not imagining that I'm rewriting the whole memory allocation/freeing process, I'm imagining that I'm changing the language that's built on top of that.

So with that being said, I created a refcounter object to pass around as part of the state. The main complicated parts of the refcounter were 1) keeping track of references which stopped existing when we returned from a function, and 2) a maybe-bad choice that I made in how to deal with the fact that after freeing a pointer you still had access to its variable and could technically do stuff to the variable as long as you didn't try to read from it, but that accommodating this shouldn't break the reference counter.

Simpler parts of reference counting

I incremented the reference count whenever the program allocs a variable, and decremented the reference count whenever I freed a variable. These cases make sense, but don't quite cover everything that we need to handle.

Id

One way for multiple references to exist to an object is to use the id call. So I have it check if it's iding a pointer, and if so then it increments that pointer's reference count.

It's a little more complicated than that, since if you overwrite a pointer variable, then that pointer loses a reference, and you have to decrement it. This is tested in id_switch.bril.

I realized during the writeup that it's also a little trickier than that, since there's also a case (tested in multi_id.bril) that if you id a pointer variable to itself (i.e. pointer: ptr<int> = id pointer) then this should be a noop for the refcounter, instead of doing something like:

• deleting the pointer (from refcount hitting zero since we're losing a reference to the pointer).
• incrementing the refcount (and potentially now forgetting to free it later).

Pointer addition

Pointer addition is also a little tricky, with basically the same pitfalls as id.

Keeping track of references when entering/exiting a function

Exiting a function

I quickly realized that one of the main points that we have to decrement a refcount is when we leave the function where that variable was defined. So I wrote a function to decrement the refcounter for every variable that we had in the environment if it was a pointer.

But then, I realized that you shouldn't decrement the return variable, so I fixed that.

Entering a function

This worked reasonably well, but when I went to test it it was wildly wrong. The main issue was that variables could be passed to a function as arguments, and so if you pass a variable as an argument to the function and then return from the function this should be a noop in terms of the refcounter. To fix this, I incremented the reference count for every argument to a function when the function is called. I don't 100% feel that that was the right choice -- it seems like conceptually it would be better to clean up every variable that wasn't an argument, but since I'm writing in typescript I didn't quite know now I wanted to do that and did this instead.

Manipulating freed variables

The weirdest thing about my implementation came up around freed variables. The basic problem is that when you free a variable the refcount should go to zero, but the variable still exists!

@main() {
  size: int = const 10;  
  vals: ptr<int> = alloc size;
  free vals;
  vals: ptr<int> = id vals;
  ret;
}

This is totally benign when you allocate then free a variable in a function and then return from that function, but as I understand it bril is okay with you using the variable for a freed pointer as long as you don't try to read from the variable.

My ideal logic would just be that freeing a variable also removes it from the environment, but that would crash the bril interpreter when you try to use it later with an error related to trying to use an out-of-scope function. So instead, I mark it as a dead reference, and then if you try to use it again I provide a more helpful error message about trying to use a freed variable.

Basically this entire deadref idea is more precise bookkeeping around the fact that a pointer was freed but its variable is still in scope. Maybe setting it to undefined would be a better way of dealing with this.

Testing

Helpfully, the bril interpreter reference implementation throws an error message if you make it to the end of a program execution and there's still anything in your heap. This means that simply not-crashing means that your garbage collection worked well.

I tested by finding all of the benchmark code which uses alloc, commenting out all of their free statements, then checking that brili-gc runs the program to produce the normal output. That code is in this directory.

I also wrote some special test cases in *_switch.bril, bad_*.bril, and multi_id.bril. These address issues that came up while I was thinking about the implementation phase.

[sampsyo]

Wow, this is a pretty tricky thing you noticed!

a maybe-bad choice that I made in how to deal with the fact that after freeing a pointer you still had access to its variable and could technically do stuff to the variable as long as you didn't try to read from it, but that accommodating this shouldn't break the reference counter.

To summarize, it is definitely illegal to load or store through a pointer that has already been freed. But are you allowed to do other stuff with it, like ptradd or print or loading/storing the pointer itself elsewhere? We haven't really said either way! It doesn't seem very useful to have that, but it also seems annoying to prohibit it, so there's no clearly correct answer. I think it would be OK to leave that pointer hanging around and just pointing to nowhere—if the program crashes, that's OK, because the program was incorrect anyway.

FWIW, most people dealt with this by making free into a no-op—removing the programmer's ability to manually free stuff, requiring the GC to do all the freeing. That is also a very reasonable approach.

Also, really nice work writing up the trickiness involved in function calls and returns! I think many of the RC submissions for this task did not deal with this correctly, mostly leading to memory leaks that needed to be cleaned up when main returned.

[tonyjie]

My implementation is here

Design

I implement a Reference Counting-based Garbage Collector. It is implemented in brili.ts to extend the brili interpreter. The main idea is to maintain a Map<address, reference count> which address is the memory location, and reference count is the referenced times of this location.

I implemented several functions for our RCGC class

• inc(base): increment the reference count of the given address by one
• dec(base): decrement the reference count of the given address by one
• incAll(): increment all the reference counts in counts Map by one
• decAll(): decrement all the reference counts in counts Map by one. If the count==0, free the address in the heap.

I need to update this map using the above functions when encountering every instruction:

• alloc: use inc(base)
• id: use inc(base)
• call: use incAll()
• ret: if the return value is a Pointer, we need to keep it: so we inc the count of return pointer. Then use decAll().

The reason we incAll() and decAll() when encountering call and ret bril instruction is because: we want to distinguish pointers initialized in different functions. When a function return, the pointers initialized in the scope of this function should be freed.

Build the new brili interpreter with GC

under the GC branch in my bril repo

cd here

yarn
yarn build
yarn link

Test

I created several testcases with different features here. bril2json < {filename} | brili would PASS all the testcases.

I also removed all the free in benchmarks dir to get a new benchmarks-gc

turnt *.bril would PASS all the benchmarks.

Discussion

• The first thing I learned is how interpreter works, which is not clear to me before. A read-eval-print loop REPL expresses it clearly. We can also see that from brili.ts code.

• I also noticed that there are still some corner (or not corner) cases that I didn't cover yet. When I'm wondering if I need to deal with ptradd instruction, I came up with a tricky bril example as follows:

@f : ptr<int> {
  one: int = const 1;
  ten: int = const 10;
  ptr_base: ptr<int> = alloc ten;
  ptr_move: ptr<int> = ptradd ptrbase one;
  ret ptr_move;
}

@main {
  five: int = const 5;
  ptr_move : ptr<int> = call @f;
  store ptr_move five; 
  # ERROR here: we would FREE the memory allocated when f end, because we return ptr_move but not ptr_base. 
}

In brili.ts, we would only really alloc memory in heap when calling alloc, while ptradd would just add an offset to the Pointer value. In my current implementation, I would just free the memory when ptr_base is not alive anymore, regardless of other pointers like ptr_move.

It's possible to support above example, but if ptr_move: ptr<int> = ptradd ptrbase eleven makes it out of the scope of allocated memory, we need to consider it again...

[sampsyo]

Thanks for the useful writeup! About that last example… I do think that example should probably work (ignoring the reference to ptr1 in the ret instruction, which I think is supposed to refer to ptr_move instead?).

I think the key insight here is that we should keep track of reference counts at the granularity of allocated regions, not individual values within those regions. So that ptradd instruction would increment the reference count to the ptr_base region to 2. Then, when the function returns, ptr_base goes out of scope but ptr_move is retained, so the reference count goes to 1. Does that make sense?

[tonyjie]

Yes, there's a typo for the ptr1, it should be ptr_move (I just fixed it).

What makes it kind of complicated is that we need to keep track of allocated regions that each pointer is reponsible to. For example, if we move the ptr by 11 ptr_move: ptr<int> = ptradd ptrbase 11, then ptr_move would point to an unallocated address.

[sampsyo]

Hmm… are you assuming you're allowed to use ptradd to go "past the end" of an allocation? That shouldn't really be allowed; we should add to the docs that such an out-of-buonds pointer should be illegal to load/store through.

[sampsyo]

Discussion expanded in docs: sampsyo/bril@8d75df6

[barabanshek]

My implementation is here. I implemented a reference count based GC for bril-ts. Here is how it works.

Implementation

I defined a class GC that incapsulates my GC and pass it in the state variable to the interpreter. My GC operates at base addresses of pointers. It keeps tack of all references to all memory locations. The GC class implements the following methods:

• appendNewLocation() - add a new memory location to the GC <location, ref_counter> map;
• freeLocation() - free memory for the location;
• incrLocCounter()/decrLocCounter() - incr/decr reference counter for locations; when decrementing, if the value becomes zero - call freeLocation();
• assignPointer() - deal with new assignments to a memory location;
• handleOutOfScope() - deal with the case when we go out of the function scope (i.e. need to decr reference counters).

Then I used the GC class to handle the following scenarios:

• call: use assignPointer() to increment counters for function arguments that are pointers;
• return: use assignPointer() to increment counters for the return values that are pointers;
• id: use assignPointer() to increment counters for assignments that deal with pointers;
• ptradd: same, use assignPointer() to increment counters for assignments that deal with pointers;
• <at the end of each function>: use handleOutOfScope() to decrement counters for all memory locations for all pointers that the function defines.

Testing

I used my own set of test-cases here to verify that it works. It passes all my cases. However, some programs from the benchmark/ folder fail. In total, I have 34/40 benchmarks working, and 6 failing. The explanation is bellow.

Limitations/Issues

Loops (SOLVED, but it raises the recursion issue explained bellow)

With my approach, I got an issue that I don't know how to solve in a more-or-less easy way. The problem is that my current implementation does not know how to deal with loops. Every time it executes assignment in a loop, it keeps incrementing the reference counter for the corresponding memory location. And since there is only one pointer that corresponds to this memory location, my handleOutOfScope() function only decrement it by one when the function exits.

I solved this problem by tracking the exact Ident that we are assigning to in order to avoid duplicates in loops. In order to distinguish the same Ident names across different functions, I also append the function name to it. This does the job, and my modified GC passes the loops tests. However, there is another issue.

Non-SSA allocations (No idea how to solve)

My GC can not handle non-SSA codes within a function. Basically, if I have smth like this:

@main(size: int) {
  loc: ptr<int> = alloc size;
  loc: ptr<int> = alloc size;
  loc: ptr<int> = alloc size;
}

It does not work, as technically, each loc is a different memory location, but it's getting shadowed by the following redefinition of loc. When the function exists, there is only one pointer being processed by my handleOutOfScope() and it still leaves the others hanging.

Recursion (Can be solved with some extra efforts)

My GC does not handle recursion well either. Basically, consider the following:

@foo(site: ptr<int>) {
  nptr: ptr<int> = ptradd site n;
  foo(site);
}

Every iteration of the recursion, we add a new reference nptr that must be released (decrement the counter). But due to my aforementioned loop optimization, the consequent recursive calls to @foo can not increment the counter for site as it nptr has the same name across calls and it looks like a loop indeed. But it's not a loop: every call is a separate function scope that causes handleOutOfScope() calls every time it terminates. Not sure how to solve it, maybe add a recursion counter?

Sidenote: A "Workaround" to release all memories even with the aforementioned issues

One workaround that I tried was just releasing all not-released memories (memories that still have non-zero reference counters) after the main() function terminates. This makes all tests in benchmarks/ to pass, but obviously, this is not making my GC to be correct.

[sampsyo]

Thanks for the clear description of the inner workings and the issues!

Fortunately, I think the resolution to the first two problems ("loops" and "non-SSA assignments") is pretty straightforward: you just need to decrement the reference count for pointer-valued variables that are overwritten. So say we have this instruction:

loc: ptr<int> = alloc size;

and say we run it multiple times (either by copying & pasting it ("non-SSA") or by running it in a loop).

1. The first time it runs, loc is undefined beforehand. So we allocate a new region, initialize its reference count to 1, and we're done.
2. The second time it runs, loc already refers to an old region. So we would again allocate a new region with reference count 1. But then, before setting loc in the environment to point to the new region, we would first decrement the reference count to the old region. In this case, that reference count would be zero and we'd free that one immediately. The new region hangs around with RC=1.

Good point about this:

One workaround that I tried was just releasing all not-released memories (memories that still have non-zero reference counters) after the main() function terminates. This makes all tests in benchmarks/ to pass, but obviously, this is not making my GC to be correct.

That's right; freeing everything at the end of main is "cheating" in the sense that it always works: you don't need to do any garbage collection at all! Everything is going to be implicitly freed when the program finally shuts down anyway. 😃

[andrewb1999]

I implemented a semi-space tracing garbage collector in brilirs. My implementation is available here.

Implementation

The majority of my implementation is based on extending the Heap struct to support garbage collection. A semi-space collector is certainly not the most space-efficient garbage collector for an interpreter like this, but I implemented it in a way that would be more amenable to a compiled language. A large array is pre-allocated to represent the heap and it is logically divided into a top and bottom half.

The actually garbage collection is based on Cheney's Scanning Algorithm and allocation is performed with bump pointer allocation. As this is a semi-space collector, every time garbage collection runs all live objects are copied to the other semi-space and therefore compacted. On every allocation the garbage collector checks whether garbage collection should run, stopping the world to run collection if it decides it should.

Garbage collection is run when the amount already allocated plus the amount to be allocated is greater than some threshold. This threshold starts out as a small power of 2 and is doubled every time garbage collection is run. This limits the number of live objects for programs will small amounts of memory allocated at a time and prevents programs that allocate large amounts of memory from running garbage collection on every allocation. I got this idea from crafting interpreters.

Testing

I tested my implementation on the bril benchmarks that allocated to memory. I deleted all free instructions from each of these benchmarks and then compared the output before and after switching to garbage collection. All benchmarks pass this test, and I added print statements to manually check that garbage collection is actually running (we could trivially get the benchmarks to pass by just leaking memory).

Challenges

This assignment took quite a bit longer than I expected. The most challenging part of this assignment actually had very little to do with garbage collection itself, but with getting brilirs to keep track of the entire stack at any point in the program. The previous implementation only keeps track of variables in the current function scope, but we obviously need to have access to the entire stack to determine which objects are live. We also need to be able to be able to modify the roots on the stack as we are moving some objects. I found this pattern a bit challenging to retrofit into brilirs, especially when having to deal with the borrow checker. I settled on extending the Environment struct to contain all scopes up to that point in the program (essentially renamed the previous Environment to Scope and then kept a list of Scopes in the environment). The implementation of this Environment is below:

#[derive(Debug)]
struct Scope {
    vars: Vec<Value>
}

impl Scope {
  #[inline(always)]
  pub fn new(size: u32) -> Self {
    Self {
      vars: vec![Value::default(); size as usize],
    }
  }
  #[inline(always)]
  pub fn get(&self, ident: &u32) -> &Value {
    // A bril program is well formed when, dynamically, every variable is defined before its use.
    // If this is violated, this will return Value::Uninitialized and the whole interpreter will come crashing down.
    self.vars.get(*ident as usize).unwrap()
  }
  #[inline(always)]
  pub fn set(&mut self, ident: u32, val: Value) {
    self.vars[ident as usize] = val;
  }
}

#[derive(Debug)]
struct Environment {
  env: Vec<Scope>
}

impl Environment {
  #[inline(always)]
  pub fn new(initial_scope: Scope) -> Self {
    Self {
      env: vec![initial_scope],
    }
  }

  #[inline(always)]
  pub fn get_current_scope_mut(&mut self) -> &mut Scope {
    self.env.last_mut().unwrap()
  }

  #[inline(always)]
  pub fn get_current_scope(&self) -> &Scope {
    self.env.last().unwrap()
  }

  #[inline(always)]
  pub fn append(&mut self, scope: Scope) {
    self.env.push(scope);
  }

  #[inline(always)]
  pub fn pop(&mut self) {
    self.env.pop();
  }
}

[sampsyo]

Awesome!! Getting this to work in brilirs is pretty cool, and a semispace collector is a good fit—it's a good balance of simplicity and effectiveness.

Getting access to the entire call stack is certainly pain in this situation. You can imagine the interpreter being structured in a different way, such that the entire stack is just a single big data structure that the interpreter can always access. But the recursive setup makes this harder to do!

[andreyyao]

I implemented a reference counting garbage collector for the Rust interpreter. Sorry for the late post.
My code is here. The relevant files are garbage.rs and interp.rs. Fitting name, I know. To find all modifications to interp.rs that I have done, simply search the variable gc (for garbage collection) with your favorite editor and it should show up at all the places I made changes.

Implementation

Most of the extra information is kept track of in this struct in garbage.rs:

pub struct Collector {
    total: FxHashMap<usize, i32>,
    diff: Vec<FxHashMap<usize, i32>>
}

Where total is just the map from a memory address to its current total reference count in the whole program. diff is a stack of maps to keep track of the changes made to total along the call stack. As expected, the top of the stack diff maps addresses to its count inside the current function. Not unlike a stack frame for executing machine code and stuff.

I also have the following member functions attached to Collector:

• enter() just pushes a new empty map onto diff. This needs to be called right after we start interpreting a function.
• exeunt() -> Vec<usize> pops the top of diff and reverts total back to the state before the callee was called. It also returns a vector of address that became 0 because of this, so we can yeet them from the heap in the interpreter. Also I like the word "exeunt" a lot and use it anywhere I can.
• increment(address : usize) increments count for address in both total and top of diff
• decrement(address : usize) decrements count for address in both total and top of diff. Returns true if address count becomes 0.

The algorithm is roughly this:

When executing function f:

    enter()

    Before everything else, for each pointer argument a of f, increment counter for a.

    for each assignment dst <- val of type ptr<T> do

        If old value of dst was defined, decrement counter for it.
        If decrement() returned true, immediately yeet the old value of dst from the heap.

        Increment the counter for val, or initialize it to 1 if not already present.
    done

    Right before finishing interpreting a function, exeunt() and free all the addresses from the returned vector, EXCEPT for the pointer address that this function is returning, if any.

Note that the returned pointer value from a function call is handled normally just like any other assignment.

Journey

I was ambivalent between reference counting and tracing, but decided that learning Rust was hard enough that reference counting was more doable.
I had a hard time figuring out how the control flow of the interpreter worked. Initially I had the wrong idea of calling exeunt when executing a Return instruction, but that doesn't cover the case for when the function has no return and simply ends, causing some memory to not be freed.
So I just splashed the exeunt part at the end of the execute() function and voila it worked.
Also, I initially only freed memory when a function finishes. However, that caused me to fail a test case test/mem/alloc_large.bril where there is just one long loop in the main function allocating memory. Because of that I free an address as soon as its reference hits 0.

Testing

First I yeeted the content of the Free case in the interpreter, making it do nothing.
I ran my code by running make, which automatically checks against the various test cases in the bril/test folder. I'm pretty sure it passes most if not all the tests, except for the ones involving spectulate and commit, which are not implemented in brilirs.
My code passes the test/mem/alloc_large.bril which shows IT IS COLLECTING SOMETHING at least.

Challenges

Rust.
Also just my being stupid.

[sampsyo]

Extremely nice work! Even if it was somewhat painful to get right within the Rust infrastructure! I really like the name exeunt for "clean up after a stack frame as it is popped on return." 😃

[orkosinha]

My implementation of the brili interpreter with Reference Counting Garbage Collection here.

RCGC

The reference count garbage collector (ReferenceCountGarbargeCollector) is used by brili.ts in the following ways

• On an alloc the count for that object is initialized with a count of 1.
• On a call to a function, increment all argument object's reference counts. After the function returns, decrement all those previously incremented.
• On a function returning a pointer, do the same thing as pointer addition book-keeping.
• On an id of a pointer, do the same thing as pointer addition book-keeping.

As with reference counting, once a reference is decremented to 0, the object is first checked if it points to a reference, which is then decremented. I want to test this more, but as of now it passes the simple test case of ptrrrecurse.bril.

Testing

For testing, I took the benchmarks which explicitly have memory operations, and either removed the free instructions (in benchmarks-mem) or kept them (in benchmarks-gc). This produced the correct results using turnt, so that's pretty good.

One thing I missed when initially implementing my garbage collector was removing references at the end of main. It seems like most of the benchmarks declare references in main, and the only time they can be removed is at the end of main. This led to some initial confusion, but it was pretty easy to debug.

[sampsyo]

OK! Since you didn't include it, here is a link to your code.

I have a few questions about things that could be a little clearer:

On a call to a function, increment all object reference counts. After the function returns, decrement all object reference counts.

What do you mean by "all object reference counts"? Do you really mean all objects in the entire program? It does seem like this is what incEnv does, but I don't exactly understand why… why would the reference count increase for everything (not just the function arguments) when you call a function?

On a function returning a pointer, initialize a new reference counter for a new object.

I'm not quite sure what this does. If a function returns a pointer to something, shouldn't it already have a reference count (created when the thing was allocated)? For example, what happens for this program?

@foo(x: ptr<int>): ptr<int> {
  ret x;
}
@main {
  y: ptr<int> = alloc 1;
  z: ptr<int> = call @foo y;
}

After the call, I think the RC for the sole allocated object in the program should be 2—one for the y reference and one for z. So I'm not sure what it would mean to initialize a new reference count for this object.

[orkosinha]

Sorry, this was mostly the mistake of me rushing my writeup, and I just omitted or said the incorrect things. To amend this, here's a more accurate description of when my GC is called...

RCGC

The reference count garbage collector (ReferenceCountGarbargeCollector) is used by brili.ts in the following ways

• On an alloc the count for that object is initialized with a count of 1.
• On a call to a function, increment all argument object's reference counts. After the function returns, decrement all those previously incremented.
  • For example in evalCall the newEnv only contains arguments when evalFunc is called. For some reason, when I commented it for my own documentation purposes to create my writeup later, I incorrectly commented that it increments all object reference counts.
• On a pointer addition, decrement the destination pointer's previous object reference count. Then increment the new object's reference count.
• On a function returning a pointer, initialize a new reference counter for a new object .
  • I honestly don't know why I wrote this, this is just not what happens. Instead it calls the assign function which I modeled from the Unified Theory of Garbage Collection paper in Figure 4. I meant to say something similar to pointer addition happens where if the dest of the retVal is being overwritten, decrement the previous reference and increment the new reference. This is also the same as what happens with id and pointer addition instructions.
• On an id of a pointer, do something similar to pointer addition book-keeping.

[sampsyo]

Great; thanks for clarifying!

[alaiasolkobreslin]

I modified the bril interpreter to do reference-counting garbage collection. My implementation is here

Implementation

I created a new class called GarbageCollector, and added a field of this type to the state type so that the state of the garbage collector would be carried throughout the program evaluation.

GarbageCollector has the following fields

• referenceCounts- key-to-number map keeping track of reference counts
• heap- heap

and methods

• alloc- adds key to referenceCounts with value 0
• assign- checks if dest is currently assigned to a location. If it is, decrement the reference count at that location. Then increment the reference count for key
• inc- increments the reference count for key
• dec- decrements the reference count for key. If the resulting count is zero, free key from the heap and delete it from referenceCounts
• incCounts- increments reference counts of all locations in env
• decCounts- decrements reference counts of all locations in env

Before evaluating a function, we call incCounts with the current environment (which contains the function arguments). After the function is executed, we call decCounts to restore the original counts.

There are a few cases that need to be modified for evaluating instructions:

• For id instructions, we call assign to update the reference counts of the old location (if it exists) and the new location
• For alloc instructions, we call alloc to add the new location to referenceCounts and cal assign to update the reference counts
• for ptradd instructions, we call assign to update the reference counts of the old and new locations

Also note that for the free case, the old code was removed to make this a nop

Testing

Since free acts as a nop now, testing brili on bril benchmarks that did memory allocation (using turnt) was a pretty good way to test (I caught most of my bugs while testing against these benchmarks). I verified that free acts as a nop by testing bril programs containing alloc but not free instructions, and made sure there weren't any errors. I also wrote some short bril programs here to make sure that the instructions that were changed (id, alloc, ptradd) were working properly.

[sampsyo]

Nice work; this was quite clear! So I can understand a little more detail about this:

for ptradd instructions, we call assign to update the reference counts of the old and new locations

Does mean that counts are maintained for every location within each allocated array? Or does it just mean that, like id, we just need to decrement the perhaps-clobbered destination value's RC and increment argument's RC?

[yy665]

I implemented a simple reference-counting garbage collector here.

##Implementation
I added a new class GarbageCollector which is now a part of the interpreter states as GC must track each piece of heap memory dynamically and globally.

GC maintains two fields which are:

• refcounts : a mapping from key to reference counts
• heap: the original heap, now managed in GC

There are basically just two methods, and associated helper functions to increment/decrement all refcounts.

• inc: increment the reference counter to a key
• dec: decrement the reference counter to a key, if the counter reaches 0, we would then free that memory location.

The above part is not very interesting, and I am assuming that all reference counting GC would have to maintain the same piece of information. The actual tricky part for this assignment is to figure out when and how would we like to use those methods.

Here are some scenerios I have thought about that actually involves any GC tracking:

• Entering/Exiting a function: When we call a function, we would increment the ref count for all memory locations, and after we return from a function, we would decrement the ref count for all memory locations. Actually, what we are trying to copy here is just the argument, but it seems functionally equivalent and also easier to distinguish when we simply just increment/decrement all memory locations.
• Alloc: Increment the ref count for the newly allocated location. Decrement the ref count on the memory location that the destination variable points to (if it already points to a memory location) to avoid duplicate counting.
• Ptradd and Id: These two instructions are somewhat similar in the sense that they both increment the ref count on the destination variable (need checking for duplication as well). I thought Ptradd would be the most difficult scenerio, given the case that we could relocate a pointer from one active heap region to another purely by ptradd. But since we define Key as base + offset, we should probably assume that the pointer always stays in the same heap region, if there's any violation we should add checking in ptradd instead.
• ret: Decrement the ref counts since what's allocated inside a scope should stay inside that scope, except for the case that we return a pointer to the caller. In this case, we need to increment the ref count for the memory location which our returned pointer points to.
• free: I kept free for debugging purpose. I used free to print out the refcounts, and to validate my design when I am implementing the task.

Testing

I wrote 6 simple tests to cover a range of scenerios, including (recursive) function calls, id and ptradd, duplicate allocation (which I
believe represents the problem we would face in loops).

[sampsyo]

Hmm; interesting! About this:

When we call a function, we would increment the ref count for all memory locations, and after we return from a function, we would decrement the ref count for all memory locations. Actually, what we are trying to copy here is just the argument, but it seems functionally equivalent and also easier to distinguish when we simply just increment/decrement all memory locations.

I'm not sure what you mean by "functionally equivalent." There seem to be some differences:

• Some unreachable objects may be kept alive. For example, if I allocate something and then pass a pointer it into a function that overwrites and "forgets" that pointer, then it will stay alive for the rest of the function call despite being unreachable by anyone.
• It requires scanning the entire heap. But I guess you can think of that as a performance problem instead of a correctness problem.

[susan-garry]

For this lesson, I (attempted to) implement a reference-counting garbage collector. My code can be found here.

Implementaton

I introduced a new class, GarbageCollector. It maintains two fields:

• counts - a map from numbers (representing the base of a pointer) to their counts.
• heap - the heap which the garbage collector has task with maintaining
  And five methods:
• 'alloc' - takes a key and assigns its count to 1. Throws an error if the key has already been defined
• inc - which takes a value and, if it is a pointer, increments the number of references to that pointer by 1
• dec - which takes a value and, if it is a pointer, decrements the number of references to that pointer by 1. If the number of references drops to 0, it frees the object
• incAll - takes a list of values and increments their reference counts (if they are pointers)
• decAll - same as incAll but instead decrements their reference counts and frees the pointers if they reach zero

This increments/decrements counts in a few circumstances:

• alloc - increment the reference count for new heap objects
• 'id' - if a variable of type ptr<T> is being assigned, increment the reference counts for the new value and decrement the reference counts for the previous pointer stored by this variable (if the variable is not being initialized)
• ptradd - increment the reference counts to the base value of the pointer we're adding to
• ret- increment the refcount of any value being returned (since bril ensures that if we call a function which returns a value, that value must be assigned to a dest), and decrement the refcounts of all variables in the local environment, since these variables are now out of scope.

I turned free into a nop for testing purposes.

Issues

This garbage collector currently does not consider recursive pointers (pointers to pointers). More importantly, while my implementation passes a few simple test cases that I wrote, it fails miserably on the benchmarks. I found debugging the garbage collector to be quite difficult since it is hard to pinpoint where the excess reference counts are coming from and where they should be getting decremented, and unfortunately I am out of time to debug this.

[sampsyo]

Hmm; I suppose I'd be interested (someday! you should graduate first before responding!!) in hearing one level of detail more about this:

This garbage collector currently does not consider recursive pointers (pointers to pointers).

It seems like there are two dimensions to this:

1. When storing a pointer to memory, it should increment the relevant reference count. (And possibly decrement the old value, if it's overwriting something.)
2. When freeing a buffer full of pointers, we should recursively decrement those reference counts.

I assume neither of these currently work, right? I wonder how difficult they would be to add… I honestly don't have a complete picture of how hard that would be, but it seems like a fairly compact extension.