A New Runtime for the EC Erlang Compiler

Abstract

I start with a very brief overview of the Erlang language, a functional language designed to support robust, reliable, distributed, near real-time applications, with the emphasis on the features the runtime must support. I then briefly list other efforts at developing an Erlang compiler. Next I discuss my work on developing the new runtime to support the EC compiler, and some of the problems and issues that arose in doing this. These include the representation and handling of Erlang terms and its consequences for garbage collection; the use of detached system pthreads to implement Erlang processes (and why we could not use the standard cancellation mechanisms); the use of the dlopen library to implement dynamic module loading; and some issues with external interaction. I conclude with some open issues to be resolved and areas for further research.

Setting the Scene

1. A New Runtime for the EC Erlang Compiler
   • Dr Lawrie Brown
   • UNSW@ADFA, Canberra

   • work started on sabbatical at SERC, RMIT in S2 2002
   • continued during summer visits to School of Network Computing, Monash Uni
2. Introduction
   • Erlang - a functional, distributed language
   • for robust, reliable, distributed, near real-time applications
   • EC - an Erlang compiler to native code
   • for Magnus massively scaleable computing platform
   • as testbed for safe Erlang mobile code extensions
   • ecrt - a runtime for EC
   • using detached system pthreads, dlopen, GC
3. Erlang Is ....
   • is a functional language
   • dynamically typed, symbolic data representation
   • single assignment to variables
   • uses pattern matching for variable binding & function selection
   • minimal side-effects simplifies code analysis & testing
   • has extremely cheap and efficient process spawning
   • and suppport for robust distributed applications
   • developed by Ericsson Computer Science Labs, Stockholm
   • focus is on soft, real-time, distributed systems
   • full system (compilers, app support) released as Open Source Erlang
4. Safe Erlang
   • result of previous research work (SSP97 @ SERC/NTNU/CSL)
   • improve support for safe mobile code execution by providing
     • controlled access to processes and external resources (ports) - capabilities
     • custom world-view - hierarchy of (sub)nodes
     • remote code loading in context
   • successfully trialed in a prototype in Erlang
   • now must be implemented in production system

     See more slides on Erlang

5. Erlang Language Requirements
   • Concurrency
   • Distribution
   • Robustness
   • Soft real-time response
   • Hot code upgrade
   • Incremental code loading
   • External interfaces

     These are some of the key features needed in Erlang to support robust, reliable, distributed, near real-time applications.

6. Some Erlang Code Fragments

       Echo = spawn(echo,loop,[]), 
       Echo ! {self(),"Here is a message"}, 
       ....
       loop() ->
         receive  
           {From,Msg} -> From ! Msg, loop()
         end.
       ....
       Echo = spawn(SomeNode,echo,loop,[]), 
       ....
       Word = string:sub_word(" Hello old boy !",3),
       apply(io,write,[Word]), 
   

   These code fragments illustrate: process spawn, nb return of pid then used to send message to new process; the echo deamon code; remote spawn as easy as local; runtime binding of code refs.

7. Open Source Erlang
   • current main Erlang implementation
   • internally threaded interpreter for BEAM machine
   • robust, excellent development
   • reasonable speed, limited by being an interpreter
   • internal runtime code complex, not well documented
8. Other Erlang Compilers
   • HiPE - High-Performance Erlang
     • native code compiler for X86 & SPARC
     • developed by Uppsala Uni
     • links to existing OSE interpreter/runtime
   • ETOS - Erlang to Scheme
     • converts Erlang to Scheme
     • then use Gambit Scheme Compiler to generate C
     • currently incomplete, has proprietary licence
   • Gerl - Geoff's Erlang
     • compile large subset of Erlang into C++
     • semantic incompatibilities wrt to C++ (esp call conventions)
     • closest to whats desired but has limitations
9. Magnus
   
   Figure courtesy of Maurice Castro (SERC), "The EC Erlang Compiler", Erlang User Conference, Älvsjö, Sweden, Sept 2001.

   Magnus a proposal is to develop a massively scaleable computing platform based on parallel computation using message passing & non-blocking interconnect based on WDM passive optical switch & DMA speed data transfers.

10. EC Erlang Compiler
    • want a full enencumbered portable compiler
    • for use as core compiler for Magnus
    • and as testbed for safe Erlang extensions
    • developed by Maurice Castro, SERC, RMIT
    • compiles most of Erlang language to x86 BSD/Linux targets
    • integrates with runtime to implement BIFs, concurrency, message passing, distribution, garbage collection (nb 1 module, 1500 lines C, 72 entry points)

      Sketch history of EC and links to Magnus proposal.

      See more slides on EC & Magnus

New EC Runtime

1. System Targets
   • EC compiler and runtime built and tested on:
     • FreeBSD
     • Linux
     • MacOSX
     • Solaris
   • with code generation only for x86 BSD/Linux targs
   • ie. guess next backend targets for compiler ;-)
2. ECRT - A New Runtime for EC
   • previous version of EC had minimal runtime
     • support for some core types and basic ops
     • but NOT concurrency, message passing etc
   • ECRT intended to provide full support for language
     • implement all types (incl extended pidportref type)
     • provide concurrency (multiple Erlang processes) & message passing
     • provide dynamic code loading
3. Erlang Data Type Support
   • Erlang is dynamically typed
   • all values are tagged references to heap
   • 8 fundamental types:
     • atom, cons (list item), tuple, integer, float, function, binary, pidportref (capability)
   • needed to add support for function, binary, pidportref
   • remembering to mask tag from address references a key trap for unwary
   • references can be found in other compound data items, in Erlang process (pthread) stacks, in system data structures
4. Capabilities for PidPortRef Types
   • key element in Safe-Erlang design
   • intended to be an unforgeable globally (almost) unique identifier
   • with set of rights permitted for that resource
   • protected by opaque crypto hash or password
   • generalization of existing Erlang pidportref type
   • have a common capability type with subtypes for:
     • reference, user reference, open file, net connection, port (limited), loaded module (future), (sub)-node, process
   • general form in ECRT is:
     [tag|rights, index, nodeid, private]
   • currently use 64-bit crypto hash (TEA-CBC64)
   • implemented as replaceable module

     Capability type key safe erlang component. Id is monotonically increasing integer index within node. Rights a subtype dependent bitmask, mostly map to BIFs for type + generic capability ops. Provides an index into table of resources on some node. Protected from change by hash/pw which only need be checked on originating node, hence no issues with key distribution.

5. Function Types
   • needed to generalise intra-module function refs to inter-module
   • note refs resolved at runtime, cf

         Somefun = fun Name/Arity,
         Res = Somefun(Arg1, Arg2),
     

   • general form on heap:
     [type|addr|mod|fun|arity|initvar]
   • interacts with runtime dynamic code loading (below)
   • unresolved problem with inline anonymous function defs
6. Binary Types
   • added support for "opaque" binary data with form
     [type|len|data...]
   • unresolved issue with best support for concat & split BIFs
   • considering "scatter-gather" implementation with array of [len|add] pairs
7. Garbage Collection
   • a serious issue for this type of functional language
   • terms are created when needed
   • space used must be released when no longer referenced
   • can make code much safer since avoids memory leaks
   • but not main interest of either Maurice or myself
   • must manage references in: heap(s), stacks, system data
   • chose to use existing Boehm-Demers-Weisner mark-sweep GC
   • available for many platforms (good)
   • thread support much less widely ported
     • in 2002 only Linux & Solaris supported
     • current development version does support all our platforms
   • interacts with design on whether use global or thread-local heaps

     A good garbage collector is critical, but must know how to find all potential data references, and be able to suspend executing code whilst sweeping for these - highly non-trivial in a threaded env! The BDW GC was chosen as it had good reviews, is being actively developed, and is the standard GC bundled with GCC (though an older release). EC is currently using a global heap for efficiency in message passing (below). Note that OSE & Gerl both use thread-local heaps and hence copy on message passing. Hence get much better efficiency on the very common message passing operation, at cost of much harder collection since must stall ALL threads.

8. Concurrency
   • Erlang inherently concurrent with message passing between processes
   • node implemented as heavy weight Unix type process with address space protection
   • Erlang processes implemented as detached, system scheduled, Posix threads
   • but found not all Posix implementations are "equal"!!!
   • for comparison GERL used Linux processes relying on light-weight forking in recent kernels

     A key feature of Erlang is support for cheap and efficient process spawning. Hence we clearly needed to support some form of light-weight processes. For greatest portability POSIX pthreads were chosen. However hit portability issues with variations between implementations: in Makefile flags & libs, thread ID, concurrency (below). In end have only used a fairly minimal, and hence widely supported, set of pthread primitives.

9. Key System Data Structures
   • needed own "system" data structures to manage Erlang processes
   • chose a hash-table / hash-chain / bucket-hash implementation
   • Erlang processes table to manage aspects like:
     (links, message buffers, flags, registered names)
   • use thread-specific data to hold local info (pid, heap, process dictionary)
   • also have module, node, and registered_name tables
10. Message Passing
    • Erlang inter-process interaction based on message-passing
    • must be fast efficient reliable
    • have a "message-buffer" in each process-table record
    • implemented as a "mutable" list
      • since Erlang data items are immutable care needed!
      • but into a fixed size buffer
      • each process flushes buffer to TSD on every send/receive
11. Fun and Games with Locking
    • must use locks to serialize access to system data structures
    • global mutex protects entire table for all tables
    • process-table also uses condition variable to manage record access
    • with multiple overlapping conditions (not for faint-hearted!)
      eg. write message, handle exit etc
12. Cancellation is a Nightmare
    • cancellation is a nightmare!
    • Erlang processes need to be able to send exit signals to each other
    • originally tried using Posix deferred thread cancellation
    • simply could not make it work reliably
    • problems were variable support of mechanisms, handling of locks & amount of work on cleanup
      • cancellation signal can be taken whilst Erlang process holds lock, which must be tracked & released (became very hard)
      • exiting processes must signal their exit status to other linked processes, but this involves interactions requiring locks etc (hence recursively cleanup calls!)
    • finally discarded any use of cancellation
    • now set flag in our process data structure
    • rely on Erlang processes (threads) to check regularly (must do on message passing, other process interaction)
    • and the lesson is: don't use cancellation!!!

      Having chosen to use pthreads, it seemed an obvious choice to use the thread cancellation mechanisms provided, despite warnings that "cancellation was extremely problematic and fraught with danger". They were right (took 2 months to admit defeat!). In end effectively implemented user-space deferred cancellation.

13. Function Calling Conventions
    • adopted C calling conventions for ease of interoperability
    • all function parameters and return value are EC terms (eptr)
    • adopted naming convention for functions of: M_F_A
    • but may only know actual values at runtime (see below)
    • which leaves issue of implementing:
      apply(io,write,Args)
    • have varying number of args on every call
    • requires inline assembler to do well (or very nasty hack)

      In EC the decision was made early to use standard C calling conventions, to maximise interoperability with code compiled in other languages. All function parameters and its return value had to be Erlang terms. Key issue was handling varying length arg lists at runtime.

14. Dynamic Code Loading and Execution
    • Erlang modules are dynamically loaded and can be replaced at runtime
    • have implemented this using dlopen() et al
    • indeed can load not just Erlang (EC modules) but any compiled code which conforms to naming/layout conventions
      • module M in file M.so
      • function F arity A has entry point M_F_A
      • have module_info table ["F", A, *M_F_A]
    • runtime manages a table (hash-chain) of loaded modules used to identify externally accessible functions in each module
    • must consult this table on every apply call and external function call
    • externally compiled code must also supply module data structures

      For dynamic code loading in interest of maximum portability, used the standard dlopen library. Although nonstd on MacOSX the 3rd party dlcompat library was used (now part of OS). Also issue of different Makefile flags on every platform! The module table is initialised with a module_info record for the erlang module, a placeholder for all BIFs implemented as part of the runtime - this is automatically generated from the master BIF list used by the compiler - sed is wonderful!

15. Dynamic Code Replacement
    • loading a new module is easy, will be inserted before old in hash-chain, hence all new calls will use latest version
    • real issue is determining when no further Erlang processes are using old code
    • current thinking is to leverage GC mechanisms
      • specifically a finalizer on the module_info record which needs to be on heap
      • this approach has been debated and has detractors
      • to be resolved
16. External Interaction
    • in OSE use compiled in drivers for external system interaction
    • with "handle" being a "port"
    • in EC have native support for files & net sockets as capabilities
    • and can simply link to external code where needed
    • keep "port" capability subtype as stub for interaction with OSE nodes
17. Distributed Erlang Nodes - Representation
    • Erlang is distributed
    • need support for interaction with distributed nodes
    • both EC and OSE
    • key components are:
    • external representation
      • serialization of Erlang terms into a binary blob
      • issue with standard OSE external form being unable to completely represent our capability and function terms
      • hence need to manage dual representations (EC and OSE)

      The last critical element of the runtime was providing support for interaction with other Erlang nodes, thus implementing the distribution features of Erlang which make the language so powerful. Need to implement suitable external representations (done as part of binary support, but two variants to handle EC extensions or keep compatibility).

18. Distributed Erlang Nodes - External Interaction
    • need mechanism to locate other Erlang nodes
      • OSE relies on EPMD (erlang port mapper daemon)
      • all nodes register with local EPMD on port 4369
      • other nodes query EPMD on target host to locate node
      • we support EPMD interaction, but also explicit specification of port
    • then implement connection protocol with remote node
      • this negotiates flags & validates each party based on shared "cookie"
      • and leaves open connection over which messages/signals flow
    • using erl_interface (C node) code as base
    • now operational

      External interaction consists of locating remote nodes, which usually requires interaction with EPMD ont he target system; and then implementing the distribution protocol, which negotiates flags and performs authentication (based on known shared secret "cookie"), and then leaves a connection open over which messages & signals flow. Based our code on Tobbe's erl_interface C_node code (part of OSE distro, suitably adapted for EC term representations and system interaction.

19. Other Issues and Further Work
    • now need to compare and contrast EC & OSE code
    • need to stress-test EC code, esp garbage-collection with large long-running systems
    • still have a number of compiler optimisations flagged
    • alternate backends also desirable (PPC & SPARC most likely)
    • and look at further implementation of safe erlang features (esp subnodes, resource limits, remote code loading)

Conclusion

1. Conclusion
   • have documented some design decisions & lessons from ECRT development
   • esp use of pthreads, cancellation and dlopen especially
   • have made much progress into making EC usable
   • have explored some interesting issues in implementing a fully compiled version of a concurrent, functional language
   • ECRT is 17 modules, ~ 17000 lines C, 241 entry points
   • still have more to do!
   • thanks to Dr Maurice Castro & Prof Fergus O'Brien @ SERC, RMIT
2. Questions
   • ?????
3. References

   Talk Outline:

   http://lpb.canb.auug.org.au/adfa/seminars/auug03/

   Associated AUUG paper:

   http://lpb.canb.auug.org.au/adfa/papers/auug03.html

   AVWW96

   J. Armstrong, R. Virding, C. Wikstrom, M. Williams, "Concurrent Programming in Erlang", 2nd edn, Prentice Hall, 1996. http://www.erlang.org/download/erlang_book_toc.html.

   Arms97

   Joe Armstrong, "The Development of Erlang", in Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ACM, pp 196-203, 1997.

   BDWGC

   "A garbage collector for C and C++", H. Boehm, HP, http://www.hpl.hp.com/personal/Hans_Boehm/gc/.

   BaVi99

   "Erlang 4.7.3 Reference Manual: Draft 0.7", Jonas Barklund and Robert Virding, Bluetail, 1999. http://www.bluetail.com/~rv/Erlang-spec/Drafts/es_4.7_0.7.ps.gz.

   Boeh93

   H. Boehm, "Space Efficient Conservative Garbage Collection", SIGPLAN Notices, Vol 28, ACM, No 6, pp 197-206, June 1993. http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi93.ps.Z.

   BrSa99

   Lawrie Brown, Dan Sahlin, "Extending Erlang for Safe Mobile Code Execution", V. Varadharajan, Y. Mu (ed), in Information and Communication Security, Lecture Notes in Computer Science, Vol 1726, Springer-Verlag, pp 39-53, Nov 1999. http://lpb.canb.auug.org.au/adfa/research/sserl/icics99.html.

   Bro97d

   Lawrie Brown, "SSErl - Prototype of a Safer Erlang", School of Computer Science, Australian Defence Force Academy, Canberra, Australia, Technical Report, No CS04/97, Nov 1997. http://lpb.canb.auug.org.au/adfa/papers/tr9704.html.

   Cast01

   Maurice Castro, "EC: an Erlang Compiler", Software Engineering Research Centre, RMIT, Melbourne, Australia, Technical Report, No SERC-0128, Jul 2001. http://www.serc.rmit.edu.au/~ec/docs/SERC-0128.pdf.

   Cast01b

   Maurice Castro, "EC: an Erlang Compiler", in Seventh International Erlang/OTP User Conference, Erlang Systems, Stockholm, Sweden, Sep 2001. http://www.erlang.se/euc/01/castro2001.ps.

   EC

   Maurice Castro, Lawrie Brown, "EC: an Erlang Compiler", SECR RMIT and CS ADFA, 2003. http://www.cs.adfa.edu.au/~ec/.

   Erlang

   Erlang Systems, "Open Source Erlang Distribution", Ericsson Software Technology AB, Erlang Systems, 1999. http://www.erlang.org/.

   LeBe97

   Bil Lewis, Daniel J. Berg, "Multithreaded Programming With PThreads", Sun Microsystems Press, 1997. 0136807291.

Additional Material

Erlang

Some additional slides on Erlang and my proposed Safe-Erlang extensions.

1. Erlang - Functional
   • Erlang is a functional language
   • dynamically typed, symbolic data representation
   • single assignment to variables
   • uses pattern matching for variable binding & function selection
   • applications comprise many functions with multiple clauses
   • minimal side-effects simplifies code analysis & testing

     fac(N) when N>0 -> N * fac(N-1);
     fac(0) -> 1.
     

2. Erlang - Concurrent
   • focus is on soft, real-time, systems
   • have extremely cheap and efficient process spawning
   • use returned process identifier (pid) for all interactions

         Echo = spawn(echo,loop,[]), 
         Echo ! {self(),"Here is a message"}, 
         ....
         loop() ->
           receive  
             {From,Msg} -> From ! Msg, loop()
           end.
     

3. Erlang - Distributed
   • remote spawn almost identical
   • given pid, all use is independent of locality
   • eases implementation of robust distributed applications

         Echo = spawn(SomeNode,echo,loop,[]), 
         ....
     

4. Erlang Language Features
   • Concurrency - extremely light-weight processes with message passing
   • Distribution - easy process creation & interaction on many nodes
   • Robustness - error and exception handlers for fault-tolerance
   • Soft real-time response - handles events in millisecs
   • Hot code upgrade - on running system
   • Incremental code loading - at boot time or as needed
   • External interfaces - to devices, files, network, other processes
5. Why Erlang?
   • a production grade language
   • impressive time to market
     • shorter time, better quality
   • good performance
     • sufficiently good for real telecomms
     • in large systems loss of speed wrt C more than compensated for by ease of development and maintenance
   • real-time garbage collection works
6. Limitations in Erlang now
   • pure functional use safe
   • only dangerous with side-effects
   • pids/ports too powerful
     • forgeable
     • unrestricted control over resource
       • eg can kill any process on system
   • processes have same "world-view"
     • modules, names, resources, servers
   • no remote code loading in context
7. Safer Execution in Erlang
   • need controlled access to processes and external resources (ports)
     • make these data types capabilities
   • want custom world-view
     • implement a hierarchy of (sub)nodes
       • registered names
       • modules available
       • resource limits
   • need remote code loading in context
8. Safe Erlang - Capabilities
   • unique, unforgeable resource name with associated rights to use

      <Type,Rights,Value,Node,Private>
     

   • for nodes/pids/ports/user capas
     • nb. not files, databases etc, just access to
   • possible implementations considered
     • crypto hash check, validated by node
     • password (sparse) key to table on node
   • created/checked only by owner node
9. Safe Erlang - Nodes
   • provide hierarchy of (sub)nodes
   • each with a custom context
     • registered names
       • control which servers are accessible
     • modules available
       • module name aliasing
         • support remote loading, safety renaming
     • resource limits on processes
       • partition & constrain use of system resources
       • child nodes must partition parents share
10. Safe Erlang - Remote Code Execution
    • support "remote" code loading and execution in context
      • to support mobile agents, applets
    • module refs in "remote" modules
      • load requested module from remote system, not from local system
      • each module has a "context"
    • considering code mobility

EC and Magnus

1. EC - A Compiler for Erlang
   • generates fast native machine code
   • for a large subset of Erlang
   • independent of existing runtime
   • to be widely available, portable, royalty free
   • for use as core compiler for Magnus
   • and as testbed for safe Erlang extensions
2. Open Source Erlang
   • current main Erlang implementation
   • internally threaded interpreter for BEAM machine
   • robust, excellent development
   • reasonable speed, limited by interpreter
3. Other Erlang Implementations
   • HiPE - High-Performance Erlang
     • native code compiler for X86 & SPARC
     • links to existing OSE interpreter/runtime
   • ETOS - Erlang to Scheme
     • converts Erlang to Scheme
     • then use Gambit Scheme Compiler to generate C
     • currently incomplete, has proprietary licence
   • Gerl - Geoff's Erlang
     • compile large subset of Erlang into C++
     • semantic incompatibilities wrt to C++ (esp call conventions)
     • closest to whats desired but has limitations
4. EC Structure
   
   Figure courtesy of Maurice Castro (SERC), "The EC Erlang Compiler", Erlang User Conference, Älvsjö, Sweden, Sept 2001.
5. EC Status
   • currently compiles most of the language
     • as specified in Erlang book, and Erlang Ref Man 4.4 (1999)
     • external format binaries, distribution, GC to come
     • ports not needed (file/net now full types, can link to C etc)
     • preprocessor TBD
   • to x86 assembler for BSD/Linux
   • integrates with runtime to implement BIFs, concurrency, message passing, distribution, garbage collection
6. Magnus
   • a massively scaleable computing platform
     • separate parallel activities
     • message-passing
     • non-blocking interconnect
   • implementation to use
     • DMA @ bus speed across switch
     • WDM passive optical switch
     • Erlang
7. Magnus Architecture
   
   Figure courtesy of Maurice Castro (SERC), "The EC Erlang Compiler", Erlang User Conference, Älvsjö, Sweden, Sept 2001.
8. Magnus WDM Switch
   
   Figure courtesy of Maurice Castro (SERC), "The EC Erlang Compiler", Erlang User Conference, Älvsjö, Sweden, Sept 2001.