Projects

One of the goals of the Network is to support collaboration between its members and, in particular, to help initiate new research. Members have initiated the projects listed below since the start of the Network in October 2001.

1. Survey of Users' Experiences with Garbage Collection
2. Visualising Rotor
3. Securing C
4. Exploring object lifetimes
5. Space and Time Complexity of Lazy Functional Programs
6. Memory management for Hume
7. Memory management for space-constrained embedded systems
8. Escape Analysis for Object-Oriented Languages
9. Removing thread synchronisation for garbage collection
10. Distributed Garbage Collection with DMOS
11. Reformulation and Proof of Properties of an Acyclic DGC algorithm
12. GCspy Heap Visualisation Framework

Heap Visualisation Framework

GCspy is the product of an mm-net collaboration between the universities of Glasgow (Tony Printezis) and Kent (Richard Jones). GGspy provides an architectural framework for the collection, transmission, storage and replay of memory management behaviour, as well as a novel visualisation tool to present this information. It has been used to analyse production Java virtual machines running applications of realistic size, where it has revealed interesting insights into the interaction between application programs and JVMs. GCspy's architecture allows easy incorporation into any memory management system: it is not limited to Java. Its solution scales to very large heaps; it allows already-running remote systems to be visualised, and those systems to run at full speed outside the points at which data is gathered; it requires only a small change to the memory system in which it is incorporated, and it provides a simple data gathering API.
GCspy is distributed by Sun Microsystems [report] [screenshots] [dowmload].
 

Reformulation and Proof of Properties of an Acyclic DGC algorithm

Distributed garbage collection for both Modula-3's Network Objects and Java's RMI is based on Birrell et al's well-known algorithm. Peter Dickman, Richard Jones, and Luc Moreau have reformulated the algorithm into a form which both elucidates key subtleties of the algorithm and its implementation and, simultaneously, supports a proof of crucial properties. The project also provides an intuitive yet precise graphical notation for such algorithms.
 

Distributed Garbage Collection with DMOS

Ron Morrison's group at St Andrews is investigating how the formulation of the DMOS distributed garbage collection algorithm can be improved to ease verification of its correctness and to aid implementation. This work is in collaboration with Drs Dave Munro and Henry Detmold from the University of Adelaide who visited as EPSRC Visiting Fellows in the summer under EPSRC grant GR/R84881.
 

Removing thread synchronisation for garbage collection

Synchronisation, both at the language and virtual machine level, is a key aspect of GC performance in Java. In the latter case, synchronisation is necessary between mutator (application) and garbage collector threads. Performing a collection typically requires that all mutator threads be stopped in a consistent state, i.e. that the location of all references be guaranteed, thus enabling the collector to accurately discover and safely manipulate them. The process of stopping threads consistently can be especially costly where thousands of threads are involved.
This project (Andy C. King and Richard Jones) seeks to use escape analysis techniques to allow threads to allocate objects that are not reachable outside the thread in thread-local 'heaplets' and to design new garbage collectors that can collect heaplets independently without synchronisation with other threads.
 

Escape Analysis for Object-Oriented Languages (EPSRC GR/R35401/01)

The aim of the project is to approximate the control flow of an object-oriented program so as to determine the static scopes of selected variables. The main objective is to design a new compositional and focussed escape analysis that has a precision greater than achieved using current techniques. A prototype escape analyser will be built and the precision of its results will be experimentally evaluated. Although the prototype will not have been built for performance, it will provide a check that the techniques are indeed practical and whether they are worth developing further.
The final report and our recent publications for research done in this project are on-line.
 

Memory management for space-constrained embedded systems

Memory management subsystems tend to be either fast (able to hit hard or soft real time deadlines) or small (making the optimum use of available memory) but are rarely both. This is a problem for the manufacturers of smartphones, which couple small physical size with complex consumer applications (web browsers, organisers, image editors) that use dynamic memory management. At UCL, Chris Clack's new memory manager provides the memory parsimony of best-fit allocation and coalescing with impressive performance. Initial analytic results indicated that best-case response times should be equivalent to dlmalloc and worst-case response times could be an order of magnitude better than existing algorithms. Further experimental results indicated a consistent 50% improvement on memory requirements when compared with a popular gmalloc allocator.
Following a patent application and a market study of the mobile phone sector, UCL has received enthusiastic support from many key players. In particular, UCL is currently collaborating with Symbian to run comprehensive tests of the new allocator on the Symbian OS, and ARM are donating a development kit for similar low-level tests to be run on the ARM architecture. Our research directions include modifications to move towards hard real-time applications (currently, the new allocator is only suitable for soft real-time applications), improving the intelligence of the allocator so that memory allocation patterns may be predicted and used to further improve memory utilisation, and proving useful properties of the algorithm.
 

Memory management for Hume

UCL (Chris Clack) and St.Andrews (Kevin Hammond) are collaborating on the applicability of UCL's new memory allocator to St.Andrew's Hume language. Hume is a functional language aimed at small   embedded systems, where predictability of heap size and response times are critical. The UCL allocator is aimed at size-constrained soft real-time embedded systems. In terms of smartphones (the current target of the UCL allocator) this moves the focus of attention from the applications processor to the base-band processor, where programs are smaller and have much stricter real-time constraints; the aim is to move the programmer of base-band code away from hand-crafted assembler so that time-to-market is reduced and fast-moving standards and protocols can be supported.
 

Space and Time Complexity of Lazy Functional Programs

In lazy functional languages such as Haskell, reasoning about static properties of programs such as their meaning and correctness is comparatively simple. In contrast, it is notoriously difficult to reason about dynamic properties of lazy programs such as their space and time complexity. The aim of this project (Graham Hutton and Catherine hope, Nottingham) is to develop a simple but practically useful theory of space and time for lazy functional programs, based upon the use of structured forms of recursion in preference to unrestricted recursion.
 

Exploring object lifetimes

The aim of this project (Richard Jones and Chris Ryder, Kent) is to explore in depth the lifetimes of objects allocated by Java programs. We seek to understand whether object lifetime patterns exist, whether there are predictors for these patterns and how such patterns can be exploited to improve garbage collection performance. This project is generously supported by IBM through a Faculty Partnership Award.
 

Securing C

The building blocks of today's Internet are server programs written in the programming language C. The complexity of coding these systems is compounded by the low-level nature of C. Programming errors not detected during development often manifest themselves as security vulnerabilities that can be exploited by malicious hackers. The damage inflicted by Internet worms such as the W32 Blaster Worm and MS-SQL Worm has heightened the need for securing C programs. Moreover, the US National Academies have recommended that companies should be liable for the losses incurred by security breaches in their software. If this becomes law, then verifying that a C program cannot enter an unsafe state will become an enterprise critical activity. A C program enters an unsafe, possibly insecure, state if it accesses memory beyond its assigned memory regions. Guaranteeing the correctness of memory accesses amounts to proving that the values of program variables do not exceed a certain range. Consider the problem of proving that a memory access is correct at a given point in the program. This problem is equivalent to showing that the variable that determines which memory cell is accessed contains a value that lies within a certain range. Andy King and Axel Simon at Kent have been developing polyhedral abstract domains for detecting out-of-bounds memory accesses. Thus far a new tractable (weakly-relational) polyhedral domain as been constucted specifically for this purpose, see Two Variables per Linear Inequality as an Abstract Domain by Simon, King, and Howe, LOPSTR, volume 2664 of LNCS, pages 71-89. Springer, 2002 and Convex Hull of Planar H-Polyhedra by Simon and King. International J. of Computer Mathematics, 81(4), 2004. This domain is currently being integrated into an abstract interpreter for C with the aim of verifying the correctness of the memory accesses within qmail.
 

Visualising Rotor

The aim of this project (Richard Jones and Sebastien Marion, Kent) is to incorporate GCspy into Microsoft's Shared Source CLI virtual machine (aka Rotor). GCspy has a number of advantages over the CLRProfiler, not least its platform independence and its ability to connect to and disconnect from running VMs; when disconnected, GCspy places no load on the VM. The project plans to produce case studies of the behaviour of Rotor running `interesting' applications and to explore new GCspy abstractions and views. This project is generously supported by Microsoft Research through a Rotor grant.
 

Survey of Users' Experiences with Garbage Collection

We are interested in programmers' experiences of programming languages supported by managed runtimes (including but not limited to Java, C#, etc). In particular, we are interested in bugs and performance limitations that can be ascribed to the garbage collector, or scenarios in which collector simply got in the way (for example, when objects are collected too late or not at all).
If you can help, please complete this short form

Problems with this page?
Contact the mm-net webmaster
Last modified Tue Jun 28 16:47:48 BST 2005