20040112 SPACE04

Implementation and Evaluation of a Safe Runtime in Cyclone: 

Implementation and Evaluation of a Safe Runtime in Cyclone Matthew Fluet Cornell University Daniel Wang Princeton University

Introduction: 

Introduction Web-based applications Written in high-level, safe languages C#, Java, Perl, PHP, Python, Tcl Automatic memory management Application servers Written in unsafe languages Host applications via interpreters (written in C)

Introduction: 

Introduction Long-term goal: a complete web-application server written in a safe language Short-term goal: a complete interpreter written in a safe language Implementing the core of an interpreter is not in itself a significant challenge Implementing the runtime system is a challenge

Outline: 

Outline A Scheme interpreter in Cyclone Why Scheme Key Features of Cyclone Core Scheme Interpreter Garbage Collector Performance Evaluation Conclusion

Why Scheme?: 

Why Scheme? Ease of implementation Core interpreter loop is only ~500 lines Rely on an external Scheme front-end to expand the full Scheme language into a core Scheme subset Features desirable for web programming

Key Features of Cyclone: 

Key Features of Cyclone Safe, C-like language Static type- and control-flow analysis Intended for systems programming Data representation Resource management Region-based memory management Static, lexical, dynamic, heap, unique, …

Simple Copying Collector: 

Simple Copying Collector From-space and To-space Forwarding pointers

Simple Copying Collector: 

Simple Copying Collector From-space and To-space Natural correspondence with regions LIFO discipline of lexical regions insufficient Dynamic regions appear to be sufficient Forwarding pointers

Dynamic Regions: 

Dynamic Regions Non-nested lifetimes Manual creation and deallocation Represented by unique pointer (key) Unique pointer ≡ Capability Access the region

Dynamic Regions: 

Dynamic Regions Operations new: create a fresh dynamic region Produces unique key open: open a dynamic region for allocation Temporarily consumes key free: deallocate a dynamic region Permanently consumes key

GC and Dynamic Regions: 

GC and Dynamic Regions . . . // create the to-space’s key let NewDynamicRegion {<`to> to_key} = new_ukey(); state_t<`to> = to_state; // open the from-space’s key { region from_r = open_ukey(from_key); // open the to-space’s key { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } } // free the from-space free_ukey(from_key); . . .

GC and Dynamic Regions: 

GC and Dynamic Regions . . . // create the to-space’s key let NewDynamicRegion {<`to> to_key} = new_ukey(); state_t<`to> = to_state; // open the from-space’s key { region from_r = open_ukey(from_key); // open the to-space’s key { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } } // free the from-space free_ukey(from_key); . . .

GC and Dynamic Regions: 

GC and Dynamic Regions . . . // create the to-space’s key let NewDynamicRegion {<`to> to_key} = new_ukey(); state_t<`to> = to_state; // open the from-space’s key { region from_r = open_ukey(from_key); // open the to-space’s key { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } } // free the from-space free_ukey(from_key); . . .

GC and Dynamic Regions: 

GC and Dynamic Regions . . . // create the to-space’s key let NewDynamicRegion {<`to> to_key} = new_ukey(); state_t<`to> = to_state; // open the from-space’s key { region from_r = open_ukey(from_key); // open the to-space’s key { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } } // free the from-space free_ukey(from_key); . . .

GC and Dynamic Regions: 

GC and Dynamic Regions . . . // create the to-space’s key let NewDynamicRegion {<`to> to_key} = new_ukey(); state_t<`to> = to_state; // open the from-space’s key { region from_r = open_ukey(from_key); // open the to-space’s key { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } } // free the from-space free_ukey(from_key); . . .

Forwarding Pointers: 

Forwarding Pointers What is the type of a forwarding pointer?

Forwarding Pointers: 

Forwarding Pointers What is the type of a forwarding pointer? A pointer to a Value in To-space

Forwarding Pointers: 

Forwarding Pointers What is the type of a forwarding pointer? A pointer to a Value in To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space

Forwarding Pointers: 

Forwarding Pointers What is the type of a forwarding pointer? A pointer to a Value in To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space, whose forwarding pointer is a pointer to a Value in To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space’s To-space, …

Dynamic Region Sequences: 

Dynamic Region Sequences Introduce a new type constructor mapping region names to region names typedef _::R next_rgn<ρ::R> Although the region names ρ and next_rgn<ρ> are related, the lifetimes of their corresponding regions are not

Dynamic Region Sequences: 

Dynamic Region Sequences Operations new, open, free: as for dynamic regions next: create next_rgn<ρ> from ρ

Dynamic Region Sequences: 

Dynamic Region Sequences Operations next: create next_rgn<ρ> from ρ Have an infinite supply of region names next will create a fresh dynamic region key Need a linear supply of keys Use Cyclone’s unique pointers

Dynamic Region Sequences: 

Dynamic Region Sequences Operations next: create next_rgn<ρ> from ρ A dynamic region sequence is a pair key: a dynamic region key gen: a unique pointer Unique pointer ≡ Capability Produce the next_rgn<ρ> key and gen Consumed by next

Dynamic Region Sequences: 

Dynamic Region Sequences Operations new: create a fresh dynamic region sequence Produces unique key and gen next: creates next dynamic region sequence Produces unique key and gen Permanently consumes gen

GC and Dynamic Region Sequences: 

GC and Dynamic Region Sequences gcstate_t doGC(gcstate_t gcs) { // unpack the gc state let GCState{<`r> DRSeq {from_key, from_gen}, from_state} = gcs; // generate the to-space let DRSeq{to_key, to_gen} = next_drseq(from_gen); state_t<next_rgn<`r>> to_state; // open the from-space { region from_r = open_ukey(from_key); // open the to-space { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } // pack the new gc state gcs = GCState{DRSeq{to_key, to_gen}, to_state}; } // free the from space free_ukey(from_key); return gcs; }

GC and Dynamic Region Sequences: 

GC and Dynamic Region Sequences gcstate_t doGC(gcstate_t gcs) { // unpack the gc state let GCState{<`r> DRSeq {from_key, from_gen}, from_state} = gcs; // generate the to-space let DRSeq{to_key, to_gen} = next_drseq(from_gen); state_t<next_rgn<`r>> to_state; // open the from-space { region from_r = open_ukey(from_key); // open the to-space { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } // pack the new gc state gcs = GCState{DRSeq{to_key, to_gen}, to_state}; } // free the from space free_ukey(from_key); return gcs; }

GC and Dynamic Region Sequences: 

GC and Dynamic Region Sequences gcstate_t doGC(gcstate_t gcs) { // unpack the gc state let GCState{<`r> DRSeq {from_key, from_gen}, from_state} = gcs; // generate the to-space let DRSeq{to_key, to_gen} = next_drseq(from_gen); state_t<next_rgn<`r>> to_state; // open the from-space { region from_r = open_ukey(from_key); // open the to-space { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } // pack the new gc state gcs = GCState{DRSeq{to_key, to_gen}, to_state}; } // free the from space free_ukey(from_key); return gcs; }

GC and Dynamic Region Sequences: 

GC and Dynamic Region Sequences gcstate_t doGC(gcstate_t gcs) { // unpack the gc state let GCState{<`r> DRSeq {from_key, from_gen}, from_state} = gcs; // generate the to-space let DRSeq{to_key, to_gen} = next_drseq(from_gen); state_t<next_rgn<`r>> to_state; // open the from-space { region from_r = open_ukey(from_key); // open the to-space { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } // pack the new gc state gcs = GCState{DRSeq{to_key, to_gen}, to_state}; } // free the from space free_ukey(from_key); return gcs; }

GC and Dynamic Region Sequences: 

GC and Dynamic Region Sequences gcstate_t doGC(gcstate_t gcs) { // unpack the gc state let GCState{<`r> DRSeq {from_key, from_gen}, from_state} = gcs; // generate the to-space let DRSeq{to_key, to_gen} = next_drseq(from_gen); state_t<next_rgn<`r>> to_state; // open the from-space { region from_r = open_ukey(from_key); // open the to-space { region to_r = open_ukey(to_key); // copy the state and reachable data to_state = copy_state(to_r, from_state); } // pack the new gc state gcs = GCState{DRSeq{to_key, to_gen}, to_state}; } // free the from space free_ukey(from_key); return gcs; }

GC and Dynamic Region Sequences: 

GC and Dynamic Region Sequences Comparison with type-preserving GCs Interpreter can be written in a trampoline style, rather than continuation passing style Intuitive typing of forwarding pointers

Performance Evaluation: 

Performance Evaluation

Performance Evaluation: 

Performance Evaluation

Performance Evaluation: 

Performance Evaluation

Size of Unsafe Code: 

Size of Unsafe Code

Conclusion: 

Conclusion Significantly reduce amount of unsafe code needed to implement an interpreter May incur a performance penalty for extra degree of safety Future Work Reduce performance penalty Per thread regions providing customization