Home

Cyclone

1. Unique Pointers f object is known to have no aliases it can be freed manually Qualifier aqual U or U for short An intraprocedural dataflow analysis ensures that a unique pointer is not used after it is consumed i e freed treats copies as destructive one usable copy of a pointer to the same memory Temporary Aliasing e Problem Non aliasing too restrictive e Partial solution Allow temporary lexically scoped aliasing under acceptable conditions Makes tracked pointers easier to use Increases code reuse With inference extern void f int x void foo int U x malloc sizeof Lib f x alias inserted here automatically free x Reference counted Pointers e Aliasing qualifier RC pointed to data have hidden count field Aliasing tracked as with unique pointers Explicit aliasing freeing via a RC r alias refptr a WMRC r void drop refptr a RC r Summary Allocati Deallocation Aliasing what when Es whole exit of dynamic region scope manual pem Some Application Experience Boa web server Prime factorization BetaFTPD ftp server Epic image compression Kiss FFT portable fourier transform MediaNet streaming overlay network Linux Drivers net video sound CycWeb web server CycScheme scheme interpreter Interesting Combinations e Tracked pointers can be freed manu
2. 40KL total Typically differ from original C by 5 15 15 Growable Regions typedef struct List lt r gt int head struct List lt r gt r tl F Ag Met bC void foo unsigned int region lt d gt h list_t lt d gt x NULL temp for i 0 i temp rmalloc h sizeof struct List temp gt head i temp gt tl x x temp u process h x Growable Regions typedef struct List lt r gt int head struct List lt r gt r tl M gt f The region d hf introduces a new dynamic region d with handle h void foo unsigned int i list t d x NU for i 0 itt temp rmalloc h sizeof struct List temp gt head i temp gt tl x x temp u process h x Growable Regions typedef struct List lt r gt int head struct List lt r gt r tl r list t zr void foo unsigned int i region d h list t d x NULL temp for i 0 i temp rmalloc d sizeof struct List temp gt head i temp gt tl x x temp u Since this function is given the handle for d it can allocate objects in there too or return results in that region Growable Regions typedef struct List int head x The list structure is list t parameterized by a region void foo unsigned int i region d h list t d x NULL temp for i 0 i temp rmalloc h sizeof
3. gcc 3 2 2 Cyclone code cyclone 0 9 GC BDW conservative collector 6 204 malloc free Lea allocator 2 7 2 Throughput Webservers 4000 4 BoaC 0 Boa Boa Cyc unique gt CycWeb T T 1000 2000 Memory Usage Web reserved heap unique Boa Cyc GC Boa unique GC Bottom Line CPU time O bound applications have comparable performance All applications at most 60 slowdown GC has little impact on elapsed time MediaNet is the exception Memory usage Using GC requires far more memory than manual Cyclone manual techniques approach footprint of C original Throughput MediaNet e GC free u GC only throughput Mb s 1000 10000 packet size bvtes Memory Usage Il Web reserved heap unique Boa unique GC Boa Cyc unique 11 Memory Usage III Web Boa Cyc unique Other Apps C vs Cyc GC Test C Cyclone GC Time Mem Time Mem Epic 0 70 12 5M 1 11 1 61 22 3M 1 78 KissFFT 38 394K 1 40 1 05 708K 1 80 Betaftpd 4 6 2K 4 00 1 0 192K 30 1 Cfrac 284K 15 23 1 74 1 44M 5 19 8139too 27 7K Memory Usage MediaNet 840 KB heap refent other unique reserved 131 KB 15 5 KB MediaNet GC only MediaNet GC free Other Apps Cyc GC vs no GC Things didn t talk ab Modern language features too Tagged unions and data types Pattern matching Exceptio
4. Often too conservative Prevent dereferencing with dynamic checks May be able to eliminate some or all of these with static analysis or programmer provided type annotations Safety first then tune performance Thin Pointers Thin Pointers pointer one v Only permitted no bounds check needed Thin Pointers Thin Pointers EX Thin Pointers Thin Pointers P P atte Types and qualifiers for more flexibility and or fewer checks Shorthand char p char p char notnull p1 illegal p1 NULL p1 p char pl char notnull numelts 6 p2 illegal p2 p1 char 6 p2 Fat Pointers Fat Pointers Fat Pointers Fat Pointers Fat Pointers Fat Pointers Fat Pointers Types and qualifiers char fat q Thin Pointer Dynamic Bounds void foo int len char numelts len p for int i 0 i lt len i Pla Interfacing with libC FILE fopen char notnull zeroterm name char notnull zeroterm mode int putc char FILE notnull fgets char zeroterm numelts len int len FILE notnull Our buildlib tool easily generates platform dependent headers with signatures like these programmer helps Fat Pointers Shorthand char Pointer Qualifier Summary fat rep as a triple base upper curr supports all C pointer ops but any dereference may be checked notnull Obviates null check compiler must prove numelts n Ob
5. Cyclone A Safe Dialect of C CMSC 631 Fall 2006 1988 2006 In order to start copies of itself running on other machines the worm took advantage of a buffer overrun it is estimated that it infected and crippled 5 to 10 percent of the machines on the Internet More than 15 years later nearly half of CERT advisories involve buffer overruns format string attacks and similar low level attacks Low level but unsafe Must bypass the type system to do even simple things e g allocate and initialize an object Libraries put the onus on the programmer to do the right thing e g check return codes pass in large enough buffer For efficiency programmers stack allocate arrays of size K is K big enough does the array escape downwards Programmers assume objects can be safely recycled when they cannot and fail to recycle memory when they should It s not fail stop errors don t manifest themselves until well after they happen e g buffer overruns Credit where credit is due Cyclone is a research language the product of many collaborators Greg Morrisett Yanling Wang Harvard Dan Grossman Washington Nikhil Swamy Maryland Trevor Jim AT amp T The C Programming Language e Critical software is often coded in C device drivers kernels file systems web servers email systems switches routers firewalls most arguably because it is low level Control ove
6. PENARCH 02 MediaNet Hicks et al OPENARCH 03 RBClick Patel Lepreau OPENARCH 03 STP Patel et al SOSP 03 FPGA synthesis Teifel Manohar ISACS 04 O S class at Maryland 2004 2005 Calling scanf Stack grows 32 bits downward 4 int login sr char user 100 24 printf login scanf s amp user Buffer indexes proceed upward s User types login int login char user 100 24 printf login scanf s amp user Stack smashed int login char user 100 printf login scanf s amp user Can make the return address point anywhere including into the buffer Two kinds of Pointer Errors e Spatial Dereferencing outside of a legal memory buffer possibly at the wrong type Abstraction violating attacks in this category Temporal Dereferencing a pointer after the pointed to buffer has been freed 101st character int login char user 100 24 printf login scanf s amp user Abstraction violating Attack Language and library abstractions may not be enforced Array accesses pointer dereferences type casts format strings trusted by the compiler e Other attacks exploit this fact Heap based buffer overruns Format string attacks Preventing Spatial Errors Don t allow dereferencing a pointer unless compiler can prove it s safe
7. ally with ree Or drop refptr automatically Pointers into the heap freed by GC Pointers into LIFO arenas freed at end of scope Called a reap by Berger et al e Can use tracked pointers to keys to permit arenas to have non lexical lifetimes Lifetime of arena corresponds to the lifetime of the key Called dynamic arena Ensuring Uniformity and Reuse Many different idioms could be hard to use Duplicated library functions Hard to change application code We have solved this problem by Using region types as a unifying theme Region and aliasing polymorphism E g functions independent of arguments regions aliasing All regions can be treated as if lexical Temporarily under correct circumstances Using alias and open for dynamic arenas Application Characteristics Program Non comment Lines of Code Manual Cyc Cyc manual mechs Boa 5217 286 5 98 1 U Cfrac 3143 183 5 UD Betaftpd 219 18 23 i UR Epic 3 218 10 4 UL KissFFT 74 16 25 5 U 8139too 2 971 49 UD i810_audio 1500 57 318 10 RD pwe 1373 36 1024 26 RD MediaNet 8715 URLD CycWeb U CycScheme ULD U unique pointers ref counted pointers L LIFO regions D dynamic arenas 10 Experimental Measurements e Platform Dual 1 6 GHz AMD Athlon MP 2000 1 GB RAM e Switched Myrinet Linux 2 4 20 RedHat e Software C code
8. cRegion lt r R gt Pointer to a container in region k for a dynamic region r Called a key new ukey Returns a key where r is fresh wraps in an existential and k is the unique region new rckey Similar but k is the ref counted region Disadvantages Programmers have to make the lifetimes of objects explicit must put regions on return types must allocate objects within regions must pass region handles around Regions lifetimes must be LIFO No easy way to handle objects with overlapping non nested lifetimes Constructing a region expensive if only allocates a small number of objects void f struct DynamicRegion r5 U k int r x region r open k x 42 bar r x pot free_ukey region r open k Given k points to a DynamicRegion lt gt makes r live in the ensuing scope with handle r temporarily consuming k free ukey ukey Frees the key and the region it contains new_rckey rckey Decrements the reference count on the key freeing it and the region if it goes to zero Cyclone where we stand Cyclone compiler 100KL of Cyclone code Bulk is the type checker and dataflow analyses Straightforward translation to C Available for many architectures Linux BSD Irix Cygwin Sparc etc Ports Libc and other libs sockets XML lists and more bison flex web server cfrac grobner NT device driver
9. er doesn t have to write them So this would go through pt add pt pt a pt r malloc sizeof pt r x p gt x q gt x r y p gt y q gt y return r pt 1 2 void foo pt b 3 4 pt c add pt d add c gt x 10 On the other hand pt H add pt p pt a Racy gt 2 return p H pt a 1 2 void foo pt b 3 4 pt 1 pt d add c gt x 10 So we must be explicit pt 1 add pt x1 p pt t gt gt psoyst dgosyn return p iy pt a 1 2 void foo pt b 3 4 pt c add pt d add c gt x 10 The types say it all pt add pt p pt q pt rl add pt ri p pt pt r2 add pt p pt r2 char zeroterm fgets char len zeroterm r int len FILE Safe Manual Techniques Approach generalize regions track pointers New region kind Arenas Dynamic allocation but all objects freed at once And or impose aliasing restrictions Can free individual objects using malloc free or reference counting if aliasing is tracked When writing apps use GC first tune as necessary Can result in significantly improved memory footprint and throughput What has to be written is thus pt rl add pt ri p pt gt q x Paty tcogooyr return p pt a 1 2 void foo pt b 3 4 pt c add amp a a
10. es that aliased pointers will not escape the scope int g NULL void init int v int x malloc sizeof int x v iG f x free Only ever one unique path by which to access a unique object at any program point void f int U x int U y free x y 1 have unique pointers in unique containers Options Dont allow them norm in linear type systems Track sharable containers E g guarded types in Vault restricts container aliasing and may not be thread safe Swap out unique pointers Goal avoid writing slightly different versions of the same functions One for unique pointers one for lexically scoped region pointers etc e Approach parametric polymorphism differentiated by kinds Need to differentiate between generic functions that operate on alias restricted pointers and freely aliasable ones e Unique and reference counted objects can be freed at any time Also want to be able to free an entire arena at any time Not just at the conclusion of a scope l e want separate region allocation and deallocation functions 14 Define key as a unique or reference counted pointer to a region handle Key lifetime corresponds with region lifetime Freeing the key frees the entire region Open a region to use it within a lexical scope makes region live within scope consumes the key until done struct Dynami
11. ly linked lists etc e Concurrency More Information Cyclone homepage http cyclone thelanguage org e Has papers benchmarks distribution Related work higher and lower Adapted extended ideas polymorphism ML Haskell regions Tofte Talpin Walker et al safety via dataflow Java existential types Mitchell Plotkin controlling data representation Ada Modula 3 Safe lower level languages TAL PCC engineered for machine generated code e Vault stronger properties via restricted aliasing Conclusions e High degree of control safely e Sound mechanisms for low level control Checked pointers for spatial errors Variety of techniques for temporal errors e Region based vs object based deallocation e Manual vs automatic reclamation e Region and alias annotated pointers within a coherent framework Scoped regions unifying theme alias open Polymorphism for code reuse MediaNet Data structures gt refcounted gt unique databuff A streambuff streambuff streambuff databuff 13 e Can store unique pointers in non unique containers Must use swap operator to extract them to ensure soundness of analysis e Alias construct Like Walker Watkins and Wadler 1et Fresh region is crucial to soundness normal typing machinery ensur
12. mp b pt d add amp b amp b c x 10 Dynamic Allocation How can we be sure data is live e Can use a GC or safe manual techniques GC based Data allocated in heap is given region H Region is always live dereferences are always safe Conservative collector reclaims dead objects Simple but little control over performance Potentially significant memory overheads Pause times May not be feasible in some environments e g Linux LIFO Arenas Dynamic allocation mechanism e Lifetime of entire arena is scoped At conclusion of scope all data allocated in the arena is freed Like a stack frame but permits dynamic allocation Useful when caller doesn t know how much memory needed by callee but controls lifetime LIFO Arena Example FILE infile Image i if tag infile HUFFMAN region h region r created struct hnode huff tree huff tree read tree h infile dynamically allocates with h i decode image infile huff tree region r deallocated upon exit of scope 1 Example void foo int U x malloc sizeof int int U y x consumes x disallowed free consumes y disallowed Alias Construct extern void f int r x r any region void foo int U x malloc sizeof int Li 3 alias r int r y x r fresh f y y aliasable but x consumed x unconsumed
13. n f gt sock 1 f gt state 1 return C 17
14. ns Allocation with new Porting tool Lots of libraries Cyclone GC Cyclone Manual Time Mem Time Mem 111 1 61 22 3 1 78 1 11 1 61 12 5M 1 0 1 40 1 05 708K 1 80 1 41 1 06 392K 0 99 4 00 1 0 192K 30 1 4 00 1 0 8 2K 1 32 15 23 1 74 1 44M 5 19 14 53 1 66 706K 2 49 333 0 99 31 8K 1 14 Related Work making C safer Compile to make dynamic checks possible Safe C Austin et al RTC Yong Horwitz Purify Stackguard Electric Fence CCured Necula et al performance via whole program analysis less user burden less memory management single threaded e Control C Adve et al weaker guarantee less burden SFI Wahbe Small sandboxing via binary rewriting 12 Related Work Chec e Model checking C code SLAM BLAST Leverages scalability of MC Key is automatic building and refining of model Assumes weak memory safety e Lint like tools Splint Metal PreFIX Good at reducing false positives Cannot ensure absence of bugs Metal particularly good for user defined checks Cqual user defined qualifiers lots of inference Better for unchangeable code or user defined checks i e they re complementary Future Work Tracked pointers can be painful want Better inference e g for alias Richer API restrict autorelease e Prevent leaks unique and reference counted pointers Specified aliasing for doub
15. r data structure representations Control over memory management Manifest cost good performance What about Java Java provides safety in part via hidden data fields and run time checks automatic memory management Data representation and resource management are essential aspects of low level systems Cyclone A safe convenient and modern language at the C level of abstraction Safe memory safety abstract types fail stop C level user controlled data representation and resource management easy interoperability manifest cost Convenient may need more type annotations but work hard to avoid it Modern add features to capture common idioms New code for legacy or inherently low level systems Status gt 110K lines of Cyclone code 80K compiler libraries 30K various servers applications device drivers gcc back end Linux Cygwin OSX LEGO User s manual mailing lists Still a research vehicle though winding down What is a C buffer overflow include lt stdio gt int login What happens if the user types char user 100 In something that s more than printf login 100 characters scanf s amp user get password etc Outline e Status How Cyclone handles pointer errors Spatial Errors Temporal Errors e Programming Experience e Performance Analysis Projects using Cyclone Open Kernel Environment Bos Samwel O
16. struct List temp gt head i temp gt tl x x temp E process h x Growable Regions typedef struct List r5 int head struct List lt r gt r tl REM m e Objects can be allocated into region d using void foo unsigned int i alioi hi SEA HOUR rmalloc h where h is list t d x NULL temp a handle for the region for 4 itt temp temp gt head temp tl x temp n process h x Unlike the stack any number of objects can be placed in the region Growable Regions typedef struct List lt r gt int head struct List lt r gt r tl liet ec ro void foo unsigned int i list t d x NULL temp for 7 4 0 i temp rmalloc h sizeof struct List temp gt head i temp gt t1 x x temp process h x The entire region is deallocated at the end of its scope 16 So Far Advantages Type system makes sure that can t dereference a pointer to a freed object can t forget to free a region supports some dangling pointers Runtime system ensures that region and object allocation are constant time region deallocation is constant time and faster than individually free ing the objects So the approach is quite attractive for real time systems when compared to GC Example struct conn cmd pasv struct conn j struct ftran int sock socket f alloc new ftran sock c gt transfer liste
17. viates bounds check compiler must prove Can refer to dynamic lengths zeroterm Pointer is zero terminated Temporal Errors pt add pt p pt q pt r r x p x q gt x r y gt q gt y r s lifetime ends here return amp r void foo so dereferencing c here pt 1 2 can cause problems pt b 3 4 pt c add amp a c gt x 10 typedef struct int x int y pt Preventing Temporal Errors Tracks object lifetimes by associating a region with each pointer int pointer can only dereferenced while the region is still live int r for short Two basic kinds of regions A lexical block l e an activation record The heap H has a global lifetime Region Polymorphism void addTo pt pt a p gt x q gt x gt gt This is standard parametric polymorphism addTo V rl V r2 pt rl x pt r2 void And this would be caught pt H add pt p pt a pt r p gt x q x gt gt return amp r pt a 1 2 foo b 3 4 e Simple Region Example pt a 1 2 a lives in the heap region so amp a has type pt H void foo pt b 3 4 pt aptr amp a pt bptr b lives in the activation record of foo so amp b has amp b type pt foo ence can figure out the so the programm

Cyclone

Contents

Download Pdf Manuals

Related Search

Related Contents