Skip to main content


Relaxing safely: verified on-the-fly garbage collection for x86-TSO


Peter Gammie, Tony Hosking and Kai Engelhardt


Purdue University



We report the machine-checked verification of safety for an on-the-fly, concurrent, mark-sweep garbage collector in Isabelle/HOL. The collector is state-of-the-art in that it is designed for multi-core architectures with weak memory consistency. The proof explicitly accounts for both of these features, incorporating the x86-TSO model for relaxed memory semantics on x86 multiprocessors. To our knowledge, this is the first fully machine-checked proof of such a garbage collector. We couch the proof in a framework that system implementers will find appealing, with the fundamental components of the system specified in a simple and intuitive programming language. The framework is sufficiently detailed that correspondence between abstract model and assembly coded implementation is straightforward so as to allow formal refinement from model to implementation.

BibTeX Entry

    publisher        = {ACM},
    doi              = {10.1145/2737924.2738006},
    author           = {Gammie, Peter and Hosking, Tony (Antony) and Engelhardt, Kai},
    month            = {jun},
    editor           = {{Steve Blackburn}},
    year             = {2015},
    keywords         = {formal verification, machine-checked proof, relaxed memory, tso},
    title            = {Relaxing Safely: Verified On-the-Fly Garbage Collection for x86-{TSO}},
    booktitle        = {PLDI 2015: the 36th annual ACM SIGPLAN conference on Programming Language Design and Implementation.},
    pages            = {11},
    address          = {Portland, Oregon, United States}