20040112 SPACE04

Information about 20040112 SPACE04

Published on January 3, 2008

Author: Talya

Source: authorstream.com

Content

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

Related presentations


Other presentations created by Talya

Chapter 19
06. 11. 2007
0 views

Chapter 19

MDR TB Aaron
07. 01. 2008
0 views

MDR TB Aaron

Ourplanetearth
03. 10. 2007
0 views

Ourplanetearth

Serway CP poll ch05
09. 10. 2007
0 views

Serway CP poll ch05

ELISA powerpoint Agrow knowledge
24. 10. 2007
0 views

ELISA powerpoint Agrow knowledge

Presentation Jean Pierre Allain
24. 10. 2007
0 views

Presentation Jean Pierre Allain

H114m
26. 11. 2007
0 views

H114m

svd
03. 12. 2007
0 views

svd

Invasive Species ID Powerpoint
11. 12. 2007
0 views

Invasive Species ID Powerpoint

Fallacies vs Facts
12. 12. 2007
0 views

Fallacies vs Facts

upload c beatles64 4n27
29. 10. 2007
0 views

upload c beatles64 4n27

2 relational model
30. 10. 2007
0 views

2 relational model

POSTMODERN MANAGEMENT
30. 10. 2007
0 views

POSTMODERN MANAGEMENT

Introduction Overview
02. 11. 2007
0 views

Introduction Overview

Ocean platforms prince
05. 11. 2007
0 views

Ocean platforms prince

AST PRESENTATION TO PCA
06. 11. 2007
0 views

AST PRESENTATION TO PCA

ANI
06. 11. 2007
0 views

ANI

rebecca 3rd
06. 11. 2007
0 views

rebecca 3rd

The Slave Diary Assessment
07. 11. 2007
0 views

The Slave Diary Assessment

Sugarcane presentation
23. 11. 2007
0 views

Sugarcane presentation

l 3
26. 11. 2007
0 views

l 3

Perth
04. 01. 2008
0 views

Perth

birds total
22. 11. 2007
0 views

birds total

TECNICASDE ESTUDIOA DISTANCIA
05. 01. 2008
0 views

TECNICASDE ESTUDIOA DISTANCIA

Sue Gries LC
07. 01. 2008
0 views

Sue Gries LC

morrill
03. 10. 2007
0 views

morrill

Naveen Kumar October 24 2006
12. 11. 2007
0 views

Naveen Kumar October 24 2006

nhs fellowship
25. 10. 2007
0 views

nhs fellowship

icml kdd2003
27. 09. 2007
0 views

icml kdd2003

FOSOntoWeb
30. 10. 2007
0 views

FOSOntoWeb

f ad 06112006
26. 10. 2007
0 views

f ad 06112006

bobkov
03. 01. 2008
0 views

bobkov

AGM 2005
20. 02. 2008
0 views

AGM 2005

FL Unit 1 pgs 16 18
24. 02. 2008
0 views

FL Unit 1 pgs 16 18

Lecture15 2003 10 14 FINAL
27. 02. 2008
0 views

Lecture15 2003 10 14 FINAL

art1945 60
19. 12. 2007
0 views

art1945 60

lail
05. 03. 2008
0 views

lail

ISAE 7giu05def
31. 10. 2007
0 views

ISAE 7giu05def

acg
14. 03. 2008
0 views

acg

CentralDogma
27. 03. 2008
0 views

CentralDogma

Gorini Sidlaw Mon
30. 10. 2007
0 views

Gorini Sidlaw Mon

X Internet Q2 2002
13. 04. 2008
0 views

X Internet Q2 2002

AGM Mar 06 Final frm Kim e
07. 12. 2007
0 views

AGM Mar 06 Final frm Kim e

Ballroom Dance Lessons
23. 11. 2007
0 views

Ballroom Dance Lessons

Hosea HHFW 6 28 07
21. 11. 2007
0 views

Hosea HHFW 6 28 07

radiacevesmir
15. 11. 2007
0 views

radiacevesmir

Iyer
16. 11. 2007
0 views

Iyer

proebsting
05. 11. 2007
0 views

proebsting

200753051013737
28. 12. 2007
0 views

200753051013737

Schatzmann Nett
25. 10. 2007
0 views

Schatzmann Nett

ukio bankas
14. 11. 2007
0 views

ukio bankas

E145 WorkshopB Mktg
16. 11. 2007
0 views

E145 WorkshopB Mktg

StarMotion
13. 11. 2007
0 views

StarMotion

BEL Valves
20. 11. 2007
0 views

BEL Valves

herrera Parallel 4 1
28. 11. 2007
0 views

herrera Parallel 4 1

job search bootcamp
17. 12. 2007
0 views

job search bootcamp