Technical reports

ASAP: As Static As Possible memory management

Raphaël L. Proust

July 2017, 147 pages

This technical report is based on a dissertation submitted July 2016 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Magdalene College.

DOI: 10.48456/tr-908

Abstract

Today, there are various ways to manage the memory of computer programs: garbage collectors of all kinds, reference counters, regions, linear types – each with benefits and drawbacks, each fit for specific settings, each appropriate to different problems, each with their own trade-offs.

Despite the plethora of techniques available, system programming (device drivers, networking libraries, cryptography applications, etc.) is still mostly done in C, even though memory management in C is notoriously unsafe. As a result, serious bugs are continuously discovered in system software.

In this dissertation, we study memory management strategies with a view to fitness for system programming.

First, we establish a framework to study memory management strategies. Often perceived as distinct categories, we argue that memory management approaches are actually part of a single design space. To this end, we establish a precise and powerful lexicon to describe memory management strategies of any kind. Using our newly established vocabulary, we further argue that this design space has not been exhaustively explored. We argue that one of the unexplored portion of this space, the static-automatic gap, contributes to the persistence of C in system programming.

Second, we develop ASAP: a new memory management technique that fits in the static-automatic gap. ASAP is fully automatic (not even annotations are required) and makes heavy use of static analysis. At compile time it inserts, in the original program, code that deallocates memory blocks as they becomes useless. We then show how ASAP interacts with various, advanced language features. Specifically, we extend ASAP to support polymorphism and mutability.

Third, we compare ASAP with existing approaches. One of the points of comparison we use is the behavioural suitability to system programming. We also explore how the ideas from ASAP can be combined with other memory management strategies. We then show how ASAP handles programs satisfying the linear or region constraints. Finally, we explore the insights gained whilst developing and studying ASAP.

Full text

PDF (1.0 MB)

BibTeX record

@TechReport{UCAM-CL-TR-908,
  author =	 {Proust, Rapha{\"e}l L.},
  title = 	 {{ASAP: As Static As Possible memory management}},
  year = 	 2017,
  month = 	 jul,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-908},
  number = 	 {UCAM-CL-TR-908}
}