Authors: David Mulder, Curtis Welborn

ABSTRACT

This paper describes the implementation of a garbage collector as an undergraduate research project. The garbage collector is a continuation of a project where an Assembler, Virtual Machine and Compiler were implemented as a capstone project. The project required modifying the compiler to allocate memory compatible with a mark and sweep algorithm, and adding the mark and sweep algorithm to the virtual machine. Computer Science faculty should take note that this was all completed by an undergraduate student within a year’s time, and that such challenges can reasonably be accomplished by undergraduate seniors.

INTRODUCTION

Challenges of the nature described in this paper are generally reserved for graduate students, and are considered outside the grasp of undergraduates. Computer Science faculty and students alike will be interested to note that the preceding project was completed entirely by an undergraduate senior. It is also interesting to note that the project was completed by an average student of little academic achievement, and that a Compiler, Assembler and Multi-Processed Virtual Machine with Garbage Collection were written within a year’s time.

As part of an undergraduate capstone, an Assembler, Virtual Machine and Compiler were implemented. The two-pass Compiler performs Lexical and Syntax analysis in the first pass, and Semantic analysis and Intermediate code generation in the second pass. Using Intermediate code as input, the Compiler then generates target code (assembly) that can be fed to the Assembler to generate byte-code. The byte-code can then be loaded into the Virtual Machine for execution [1]. Through independent study, a garbage collector was added to the virtual machine, which included extensive changes to the compiler.

The compiler had to be modified to place by-reference parameters onto the run-time stack first. An additional parameter is also added that counts the number of by-reference parameters. The counter is needed by the Mark and Sweep algorithm to determine the location of the by-reference parameters within an Activation Record.

To support the mark and sweep garbage collection algorithm, the virtual machine had to be modified to allocate memory from a list of available blocks. The mark and sweep algorithm is triggered when a call to allocate memory detects no free blocks. In the mark phase of the algorithm, the run-time stack is traversed searching for points that reference blocks allocated on the heap. Any block of memory reachable from the run-time stack must be marked as in use. During the sweep phase of the algorithm, the heap is searched looking for any blocks not marked as in use during the mark phase.

COMPILER MODIFICATIONS

The compiler was originally written to pass parameters to a function call via an activation record in the order they were written in the source language (a language called KXI, which is similar to java). It was necessary for the compiler to segregate between by-reference and by-value parameters. The mark phase of the algorithm must know the location of every by-reference parameter within a function calls’ activation record. See the ordering of variables in the current Activation Record of Figure 1. Because the variables are segregated, references are easily located based on offsets. For example, the first reference is located by an offset of 4*sizeof(int) from the base of the activation record (the return address, previous activation record pointer and reference counters are all integers), and the second reference is offset 5*sizeof(int) from the base.

The mark phase of the algorithm needed a special field inserted in each activation record that counts the number of by-reference parameters. This field was added in the activation record in such a way that the mark phase could iterate over each by-reference parameter and set the mark bit in the corresponding block for each object allocated on the heap. The field is referred to as the Reference Counter in Figure 1. The reference counter in this activation record tells us that there are 2 references. If we decremented the reference counter to 1, for example, the second reference on the stack would be interpreted as an integer.

VIRTUAL MACHINE MODIFICATIONS

In order to make space allocation more efficient, the heap was separated into large and small blocks. Bit vectors were used to keep track of which blocks are allocated on the heap.

An instruction was added to the virtual machine for allocating memory. Prior to the instruction, memory allocation consisted of just moving a pointer within the heap. The new allocation instruction calls the mark and sweep algorithm. If there is space available on the heap, the instruction returns a pointer to that block and marks the block as unavailable within one of the vectors that tracks all blocks in the heap.

If no available space is found, garbage collection is started. The algorithm must calculate the location of the activation record for the current function call then calculates the offset to the by-reference counter field in the activation record. Now having the number of pass by-references parameters in the current activation record, the algorithm can calculate the offset to each allocated block on the heap and set its mark bit to in use.

The algorithm must recursively follow references allocated inside of each block. This was achieved by organizing objects within a block in a similar manner to how function calls are organized in an activation record. In this way, lists, trees and even recursive data structures allocated on the heap can all be traversed and marked. In Figure 1, the mark phase will follow all references inside of Small Block A, so Small Block B is also marked.

Once all objects (blocks) and descendant objects have been marked, the algorithm calculates the location of the previous activation record. The same process of following references and marking objects proceeds for each activation record until all function calls on the run-time stack have been searched.

The sweep phase of the algorithm now iterates over the entire heap, checking the mark bit. If the mark bit is set (the block is in use), it clears the bit and moves on. This means that the block has a live reference to it which originated in an activation record that is currently on the run-time stack. Blocks A, B and D in Figure 1 have references pointing to them. These blocks will be un-marked and will remain allocated.

If the mark bit is not set, the algorithm clears the relevant marker in the vector of available blocks, freeing the block for reuse (See Small Block C in Figure 1) [2]. This allocated block will be freed during the sweep phase because it has no references pointing to it on the run-time stack.

CONCLUSION

This method of garbage collection is effective, but did prove to be inefficient. Because the algorithm isn’t activated until there is no remaining free space, the algorithm isn’t suitable for real time applications. The algorithm could be modified to operate incrementally, but it would still cause an occasional lag. These are known problems of garbage collection.

The greatest achievement of this project was the recognition of what can be accomplished by undergraduate seniors. Computer Science faculty should recognize that computing projects of this caliber can reasonably be expected in an undergraduate senior project course.

FUTURE WORK

The primary author has started work on an hp-ux pa-risc virtual machine. The first obstacle will be setting up the correct environment, based on descriptions in the pa-risc specifications. The second will be translating the pseudo code in the specification into C. A compiler/translator will be written to automatically convert the specification pseudo code into C.

A significant part of the project will be writing the loader, since it will need to include things such as run time linking. Ideally, the virtual machine will run at boot time and will include a boot loader. This would allow pa-risc software to run on virtually any hardware.

REFERENCES

[1] Mulder, D., Welborn, C., Lessons in converting from python to c++, Journal of Computing Sciences in Colleges, 29(2), 49-57, December 2013, http://dl.acm.org/citation.cfm?id=253542
[2] Jones, R., Lins, R. D., Garbage collection: Algorithms for automatic dynamic memory management, West Sussex, England

© CCSC, (2014). This is the author’s version of the work. It is posted here by permission of CCSC for your personal use. Not for redistribution. The definitive version was published in The Journal of Computing Sciences in Colleges, {volume 30, number 2, December 2014}, http://dl.acm.org/.

Here’s an alternative to applying Configuration Profiles in OSX without using an MDM client. Profiles are deployed using Group Policy over SMB, so you don’t have to open APN ports to Apple.
QAS is an AD bridge tool for unix/linux systems (including mac) that also provides Group Policy support. You can view more details here.

QAS Group Policy lets you specify Group Policy settings inside the Group Policy Management Editor, the same way you’d apply settings for a Windows host.
It works similar to Apple’s Profile Manager.

You can also create custom profiles by writing preference manifests. The preference manifests are converted to Configuration Profiles before they’re applied on the OSX host.

On the OSX host, settings are retrieved from Group Policy, and installed as Configuration Profiles.

A new version of mdds is out, and this time, we’ve decided to bump up the version to 1.0.0. As always, you can download it from the project’s main page.

Here is the highlight of this release.

First off, C++11 is now a hard requirement starting with this release. It’s been four years since the C++11 standard was finalized. It’s about time we made this a new baseline.

Secondly, we now have an official API documentation. It’s programatically generated from the source code documentation via Doxygen, Sphinx and Breathe. Huge thanks to the contributors of the aforementioned projects. You guys make publishing API documentation such a breathe (no pun intended).

This release has finally dropped mixed_type_matrix which has been deprecated for quite some time now in favor of multi_type_matrix.

The multi_type_vector data structure has received some performance optimization thanks to patches from William Bonnet.

Aside from that, there is one important bug fix in sorted_string_map, to fix false positives due to incorrect key matching.

API versioning

One thing I need to note with this release is the introduction of API versioning. Starting with this release, we’ll use API versions to flag any API-incompatible releases. Going forward, anytime we introduce an API-incompatible change, we’ll use the version of that release as the new API version. The API version will only contain major and minor components i.e. API versions can be 1.0, 1.2, 2.1 etc. but never 1.0.6, for instance. That also implies that we will never introduce API-incompatible changes in the micro releases.

The API version will be a part of the package name. For example, this release will have a package name of mdds-1.0 so that, when using tools like pkg-config to query for compiler/linker flags, you’ll need to query for mdds-1.0 instead of simply mdds. The package name will stay that way until we have another release with an API-incompatible change.

Disclaimer: I am aware that python does not allow easy installation of 2 libraries in parallel. It is just an example.

Let’s say you have an upstream requirement "needs pyfoo >= 1.6.0 but smaller than 2". Sounds easy right? Our naive solution will be:

Requires: python-pyfoo >= 1.6.0
Requires: python-pyfoo < 2

so far … so good. If your repository has only one version of pyfoo available we will probably get the package you want. now lets say we have more than one version available.

In OBS we use source tarballs everywhere to build rpms (and debs) from.

This has at least two major downsides:

1. Storing all old tar files takes up a lot of disk space
2. OBS workflows with .tar files and patches are rather different and somewhat disconnected from the git workflows we usually use everywhere else these days. E.g. for the SUSE OpenStack Cloud team we have a “trackupstream” jenkins job, that pulls the latest git version into a tarball once every day.

Fedora already keeps their metadata in git, but only a hash of the tarball.

So as one first step, I used two rather different projects to see how different the space usage would be. On the slow side I used 20 gtk2 tarballs from the last 5 years and on the fast side, I used 31 openstack-nova tarballs from Cloud:OpenStack:Master project from the last 5 months.
I used scripts that uncompressed each tarball, added it to a git repo and used git gc to trigger git’s compression.

Here are the resulting cumulative size graphs:

The raw numbers after 20 tarballs: for nova the ratio is 89772:7344 = 12.2 and for gtk2 the ratio is 296836:53076 = 5.6

What do you think: would it be worth the effort to use more git in our OBS workflows?

Do we care about being able to reproduce the original tarballs? While this is possible, it has some challenges in differing file-ordering, timestamps, file-ownerships and compression levels.
Or would it be enough if OBS converted a tarball into a signed commit (so it cannot be forged without people being able to notice)?

Do you know of a tool that can uncompress tarballs in a way that allows to track the content as single files, and allows to later re-create the original verbatim tarball, such that upstream signatures would still match?

Click the slide to see the presentation.

Click the slide to see the presentation.

Click the slide to see the presentation.

Table Styles in Writer

Further work