Experience With Safe Manual Memory-Management in CycloneMichael Hicks Greg Morrisett Dan Grossman Trevor JimUniversity of Maryland Harvard University University of Washington AT&T Labs ResearchAbstractThe goal of the Cyclone project is to investigate typesafety for low-level languages such as C. Our hard-est challenge has been providing programmers con-trol over memory management while retaining typesafety. This paper reports on our experience try-ing to integrate and effectively use two previouslyproposed, type-safe memory management mecha-nisms: statically-scoped regions and unique point-ers. We found that these typing mechanisms can becombined to build alternative memory-managementabstractions, such as reference counted objects andarenas with dynamic lifetimes, and thus provide aflexible basis. Our experience—porting C code andbuilding new applications for resource-constrainedsystems—confirms that experts can use these fea-tures to improve memory footprint and sometimesto improve throughput when used instead of, or incombination with, a conservative garbage collector.1 IntroductionLow-level languages such as C provide a degree ofcontrol over space, time, and predictability that high-level languages such as Java do not. But the lack oftype-safety for C has led to many failures and secu-rity problems. The goal of our research is try to bringthe “Mohammad of type safety” to the “mountain ofexisting C code.”To that end, we have been developing Cyclone, atype-safe dialect of C [21]. Cyclone uses a combi-nation of programmer-supplied annotations, an ad-vanced type system, a flow analysis, and run-timechecks to ensure that programs are type safe. Whenwe started the project, we relied solely on heap allo-cation and the Boehm-Demers-Weiser (BDW) con-servative garbage collector (GC) to recycle memorysafely. BDW provides convenient interoperabilitywith legacy libraries and makes it easy to supportpolymorphism without needing run-time type tags.While the BDW collector provides convenience, itdoes not always provide the performance or controlneeded by low-level systems applications. In previ-ous work, we described an integration of BDW withtype-safe stack allocation and LIFO arena allocation.A region-based, type-and-effect system based uponthe work of Tofte and Talpin [29] ensured safetywhile providing enough polymorphism for reusablecode to operate over data allocated anywhere.In practice, we found that supporting stack allo-cation was crucial for good performance, and oursystem was able to infer most region annotations forporting legacy C code that used stack allocation [13].We found that LIFO arenas were useful when callersknow object lifetimes but only callees can determineobject sizes. Unfortunately, LIFO arenas suffer fromseveral well-known limitations that we encounteredrepeatedly. In particular, they are not suited to com-putations such as server and event loops.Since then, we have explored the integrationof unique pointers into our memory managementframework. Our unique pointers are closely re-lated to typing mechanisms suggested by other re-searchers, including linear types [30], ownershiptypes [8], alias types [27], and capability types [31].The critical idea with all of these proposals is tomake it easy to track locally the state of an objectby forbidding uncontrolled aliasing. In Cyclone, avalue with a unique-pointer type is guaranteed to bethe only (usable) reference to an object. Such ob-jects can be deallocated by the programmer at anytime, and a modular flow analysis is used to ensurethat the dangling pointer cannot be dereferenced inthe rest of the computation.Unique pointers are not a novel idea, but we found1many challenges to implementing them in a full-scale safe language, as they interact poorly with otherfeatures such as exceptions, garbage collection, typeabstraction, the address-of operator, undefined eval-uation order, etc. To our knowledge, no one has at-tempted to address all of these features in a full-scalelanguage implementation.On the other hand, we found great synergies in thecombination of uniqueness and regions. In particu-lar, we were able to use the LIFO region machineryto support a form of “borrowed” pointers [7], whichgoes a long way in relaxing the burdens of unique-ness. We were also able to use unique pointers as ca-pabilities for building further memory-managementabstractions. In particular, we used unique pointersto control access to a form of dynamically-scopedarenas [16], and for building reference-counted ob-jects and arenas.In this paper, we briefly describe our support forunique pointers and the extensions they enable; ourtechnical report describes this support in greater de-tail [19]. We then discuss our experience usingthese facilities to build or port a few target appli-cations, including a multimedia overlay network, asmall web server, a Scheme interpreter, an ftp server,and an image-manipulation program. Most of the ap-plications were chosen because they are structuredas (infinite) loops with loop-carried state and arethus not well-suited for LIFO arenas. Furthermore,we feel that these applications are representative forresource-limited platforms, such as cell-phones orembedded systems, where space is at a premium. Inmost of these applications, we were able to reduceif not eliminate the need for garbage collection. Wealso saw dramatic improvements in working-set size,and for at least one application an improvement inthroughput.Thus, the contributions of this paper are two-fold:1. We show that the addition of unique pointers toa region-based language provides a flexible ba-sis for building type-safe, manual memory man-agement, which can complement or replace GC.2. We confirm that the resource requirementsof some important applications can be sig-nificantly improved through type-safe, manualmemory management.2 Regions in CycloneAll of the memory management facilities in Cyclonerevolve around regions. A region is a logical con-tainer for objects that obey some memory manage-ment discipline. For instance, a stack frame is a re-gion that holds the values of the variables declaredin a lexical block, and the frame is deallocated whencontrol-flow exits the block. As another example, thegarbage-collected heap is another region, whose ob-jects are individually deallocated by the collector.Each region in a program is given a compile-timename, either explicitly by the programmer or implic-itly by the compiler. For example, the