20040112 SPACE04

100 %
0 %
Information about 20040112 SPACE04
Entertainment

Published on January 3, 2008

Author: Talya

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

PowerPoint Presentation - Cornell University

Monadic Regions Matthew Fluet Cornell University Introduction Draw together two lines of research Region-based memory management Regions delimit lifetimes ...
Read more

Matthew Fluet -- Monadic Regions - Cornell University

Monadic Regions. jfp06.pdf (with Greg Morrisett; To appear in the Journal of Functional Programming) ... (Appeared at SPACE'04; 20040112-SPACE04.ppt)
Read more