.TLThe Inferno Operating System.AUSean DorwardRob PikeDavid Leo PresottoDennis M. RitchieHoward TrickeyPhil Winterbottom.AIComputing Science Research CenterLucent Technologies, Bell LabsMurray Hill, New JerseyUSA.FS.FAOriginally appeared in the.I "Bell Labs Technical Journal" ,Vol. 2, No. 1, Winter 1997, pp. 5-18..brMinor revisions have been made by Vita Nuova to reflect subsequent changes to Inferno..brCopyright © 1997 Lucent Technologies Inc. All rights reserved..FE.ABInferno is an operating system for creating and supporting distributed services.It was originally developed by the Computing Science Research Center of Bell Labs, the R&D arm of Lucent Technologies, andfurther developed by other groups in Lucent..LPInferno was designed specifically as a commercial product, both for licensingin the marketplace and for use within new Lucent offerings.It encapsulates many years of Bell Labs research in operating systems, languages, on-the-fly compilers, graphics, security, networking and portability..AE.SHIntroduction.LPInferno is intended to be used in a variety of network environments, for example those supportingadvanced telephones, hand-held devices, TV set-top boxes attached to cable or satellite systems, and inexpensive Internet computers, but also in conjunction with traditional computing systems..LPThe most visible new environments involve cable television, direct satellite broadcast, the Internet, and other networks. As the entertainment, telecommunications, and computing industries converge and interconnect, a variety of public data networks are emerging, each potentially as useful and profitable as the telephone system. Unlike the telephone system, which started with standard terminals and signaling, these networks are developing in a world of diverse terminals, network hardware, and protocols. Only a well-designed, economical operating system can insulate the various providers of content and services from the equally varied transport and presentationplatforms. Inferno is a network operating system for this new world..LPInferno's definitive strength lies in its portability and versatility across several dimensions:.IP •Portability across processors: it currently runs on Intel, Sparc, MIPS, ARM, HP-PA, and PowerPC architectures and is readily portable to others..IP •Portability across environments: it runs as a stand-alone operating system on small terminals, and also as a user application under Windows NT, Windows 95, Unix (Irix, Solaris, FreeBSD, Linux, AIX, HP/UX) and Plan 9. In all of these environments, Inferno applications see an identical interface..IP •Distributed design: the identical environment is established at the user's terminal and at the server, and each may import the resources (for example, the attached I/O devices or networks) of the other. Aided by the communications facilities of the run-time system, applications may be split easily (and even dynamically) between client and server..IP •Minimal hardware requirements: it runs useful applications stand-alone on machines with as little as 1 MB of memory, and does not require memory-mapping hardware..IP •Portable applications: Inferno applications are written in the type-safe language Limbo, whose binary representation is identical over all platforms..IP •Dynamic adaptability: applications may, depending on the hardware or other resources available, load different program modules to perform a specific function. For example, a video player application might use any of several different decoder modules..LPUnderlying the design of Inferno is a model of the diversity of application areas it intends to stimulate. Many providers are interested in purveying media and services: telephone network service providers, WWW servers, cable companies, merchants, various information providers.There are many connection technologies: ordinary telephone modems, ISDN, ATM, the Internet, analog broadcast or cable TV, cable modems, digital video on demand, and other interactive TV systems..LPApplications more clearly related to Lucent's current and planned product offerings includecontrol of switches and routers, and the associated operations system facilities needed to support them.For example, Inferno software controls an IP switch/router for voice and data beingdeveloped by Lucent's Bell Labs research and Network Systems organizations.An Inferno-based firewall (Signet) is being used to secure outside access to the ResearchInternet connection..LPFinally, there are existing or potential hardware endpoints. Some are in consumers' homes: PCs,game consoles, newer set-top boxes. Some are inside the networks themselves: nodes for billing, network monitoring or provisioning. The higher ends of these spectra, epitomized by fully interactive TV with video on demand, may be fascinating, but have developed more slowly than expected. One reason is the cost of the set-top box, especially its memory requirements. Portable terminals, because of weight and cost considerations, are similarly constrained..LPInferno is parsimonious enough in its resource requirements to support interesting applications on today's hardware, while being versatile enough to grow into the future. In particular, it enables developers to create applications that will work across a range of facilities. An example: an interactive shopping catalog that works in text mode over a POTS modem, shows still pictures (perhaps with audio) of the merchandise over ISDN, and includes video clips over digital cable..LPClearly not everyone who deploys an Inferno-based solution will want to span the whole range of possibilities, but the system architecture should be constrained only by the desired markets and the available interconnection and server technologies, not by the software..SHInferno interfaces.LPThe role of the Inferno system is to.I "create"several standard interfaces for its applications:.IP •Applications use various resources internal to the system, such as a consistent virtual machine that runs the application programs, together with library modules that perform services as simple as string manipulation through more sophisticated graphics services for dealing with text, pictures,higher-level toolkits, and video..IP •Applications exist in an external environment containing resources such as data files that can be read and manipulated, together with objects that are named and manipulated like files but are more active. Devices (for example a hand-held remote control, an MPEG decoder or a network interface) present themselves to the application as files..IP •Standard protocols exist for communication within and between separate machines running Inferno, so that applications can cooperate..LPAt the same time, Inferno.I usesinterfaces supplied by an existing environment, either bare hardware or standard operating systems and protocols..LPMost typically, an Inferno-based service would consist of many relatively cheap terminals running Inferno as a native system, and a smaller number of large machines running Inferno as a hosted system. On these server machines Inferno might interface to databases, transaction systems, existing OA&M facilities, and other resources provided under the native operating system. The Inferno applications themselves would run either on the client or server machines, or both..SHExternal Environment of Inferno Applications.LPThe purpose of most Inferno applications is to present information or media to the user; thus applications must locate the information sources in the network and construct a local representation of them. The information flow is not one-way: the user's terminal (whether a network computer, TV set-top, PC, or videophone) is also an information source and its devices represent resources to applications. Inferno draws heavily on the design of the Plan 9 operating system [1] in the way it presents resources to these applications..LPThe design has three principles..IP •All resources are named and accessed like files in a forest of hierarchical file systems..IP •The disjoint resource hierarchies provided by different services are joined together into a single private hierarchical.I "name space" ..IP •A communication protocol, called.I "Styx" ,is applied uniformly to access these resources, whether local or remote..LPIn practice, most applications see a fixed set of files organized as a directory tree. Some of the files contain ordinary data, but others represent more active resources. Devices are represented as files, and device drivers (such as a modem, an MPEG decoder, a network interface, or the TV screen) attached to a particular hardware box present themselves as small directories. These directories typically containing two files,.CW "data"and.CW "ctl" ,which respectively perform actual device input/output and control operations. System services also live behind file names. For example, an Internet domain name server might be attached to an agreed-upon name (say.CW "/net/dns" ); after writing to this file a string representing a symbolic Internet domain name, a subsequent read from the file would return the corresponding numeric Internet address..LPThe glue that connects the separate parts of the resource name space together is the Styx protocol.Within an instance of Inferno, all the device drivers and other internal resources respond to the procedural version of Styx. The Inferno kernel implements a.I "mount driver"that transforms file system operations into remote procedure calls for transport over a network. On the other side of the connection, a server unwraps the Styx messages and implements them using resources local to it. Thus, it is possible to import parts of the name space (and thus resources) from other machines..LPTo extend the example above, it is unlikely that a set-top box would store the code needed for an Internet domain name-server within itself. Instead, an Internet browser would import the.CW "/net/dns"resource into its own name space from a server machine across a network..LPThe Styx protocol lies above and is independent of the communications transport layer; it is readily carried over TCP/IP, PPP, ATM or various modem transport protocols..SHInternal Environment of Inferno Applications.LPInferno applications are written in a new language called Limbo [2], which was designed specifically for the Inferno environment. Its syntax is influenced by C and Pascal, and it supports the standard data types common to them, together with several higher-level data types such as lists, tuples, strings, dynamic arrays, and simple abstract data types..LPIn addition, Limbo supplies several advanced constructs carefully integrated into the Inferno virtual machine. In particular, a communication mechanism called a.I "channel"is used to connect different Limbo tasks on the same machine or across the network.A channel transports typed data in a machine-independent fashion, so that complex data structures (including channels themselves) may be passed between Limbo tasks or attached to files in the name space for language-level communication between machines..LPMulti-tasking is supported directly by the Limbo language: independently scheduled threads of control may be spawned, and an.CW "alt"statement is used to coordinate the channel communicationbetween tasks (that is,.CW "alt"is used to select one of several channels that are ready to communicate).By building channels and tasks into the language and its virtual machine, Inferno encourages a communication style that is easy to use and safe..LPLimbo programs are built of.I "modules" ,which are self-contained units with a well-defined interfacecontaining functions (methods), abstract data types, and constants defined by the module and visible outside it. Modules are accessed dynamically; that is, when one module wishes to make use of another, it dynamically executes a.CW "load"statement naming the desired module, and uses a returned handle to access the new module.When the module is no longer in use, its storage and code will be released.The flexibility of the modular structure contributes to the smallness of typical Inferno applications, and also to their adaptability.For example, in the shopping catalog described above,the application's main module checks dynamically for the existence of the video resource.If it is unavailable, the video-decoder module is never loaded..LPLimbo is fully type-checked at compile- and run-time; for example, pointers, besides being morerestricted than in C, are checked before being dereferenced, and the type-consistency of a dynamically loaded module is checked when it is loaded. Limbo programs run safely on a machinewithout memory-protection hardware.Moreover, all Limbo data and program objects are subject toa garbage collector, built deeply into the Limbo run-time system. All system data objects are tracked by the virtual machine and freed as soon as they become unused. For example, if an application task creates a graphics window and then terminates, the window automatically disappears the instant the last reference to it has gone away..LPLimbo programs are compiled into byte-codes representing instructions for a virtual machine calledDis. The architecture of the arithmetic part of Dis is a simple 3-address machine, supplemented with a few specialized operations for handling some of the higher-level data types like arrays and strings. Garbage collection is handled below the level of the machine language; the scheduling of tasks is similarly hidden. When loaded into memory for execution, the byte-codes are expandedinto a format more efficient for execution; there is also an optional on-the-fly compiler that turns a Dis instruction stream into native machine instructions for the appropriate real hardware. This can be done efficiently because Dis instructions match well with the instruction-set architecture of today's machines. The resulting code executes at a speed approaching that of compiled C..LPUnderlying Dis is the Inferno kernel, which contains the interpreter and on-the-fly compiler as well as memory management, scheduling, device drivers, protocol stacks, and the like.The kernel also contains the core of the file system (the name evaluator and the code that turns file system operations into remote procedure calls over communications links) as well as the small file systems implemented internally..LPFinally, the Inferno virtual machine implements several standard modules internally. These include.CW "Sys" ,which provides system calls and a small library of useful routines (e.g. creation of network connections, string manipulations). Module.CW "Draw"is a basic graphics library that handles raster graphics, fonts, and windows. Module.CW "Prefab"builds on.CW "Draw"to provide structured complexes containing images and text inside of windows; these elements may be scrolled, selected, and changed by the methods of.CW "Prefab" .Module.CW "Tk"is an all-new implementation of the Tk graphics toolkit [18], with a Limbo interface. A.CW "Math"module encapsulates the procedures for numerical programming..SHThe Environment of the Inferno System.LPInferno creates a standard environment for applications. Identical application programs can rununder any instance of this environment, even in distributed fashion, and see the same resources.Depending on the environment in which Inferno itself is implemented, there are several versions of the Inferno kernel, Dis/Limbo interpreter, and device driver set..LPWhen running as the native operating system, the kernel includes all the low-level glue (interrupt handlers, graphics and other device drivers) needed to implement the abstractions presented to applications.For a hosted system, for example under Unix, Windows NT or Windows 95, Inferno runs as a set of ordinary processes.Instead of mapping its device-control functionality to real hardware,it adapts to the resources provided by the operating system under which it runs.For example, under Unix, the graphics library might be implemented using the X window system and the networking using the socket interface; under Windows, it uses the native Windows graphics and Winsock calls..LPInferno is, to the extent possible, written in standard C and most of its components are independent of the many operating systems that can host it..SHSecurity in Inferno.LPInferno provides security of communication, resource control, andsystem integrity..LPEach external communication channel may be transmitted in the clear,accompanied by message digests to prevent corruption, or encrypted toprevent corruption and interception. Once communication is set up,the encryption is transparent to the application. Key exchange isprovided through standard public-key mechanisms; after key exchange,message digesting and line encryption likewise use standard symmetricmechanisms..LPInferno is secure against erroneous or malicious applications, andencourages safe collaboration between mutually suspicious serviceproviders and clients. The resources available to applications appearexclusively in the name space of the application, and standardprotection modes are available. This applies to data, tocommunication resources, and to the executable modules that constitutethe applications. Security-sensitive resources of the system areaccessible only by calling the modules that provide them; inparticular, adding new files and servers to the name space iscontrolled and is an authenticated operation. For example, if thenetwork resources are removed from an application's name space, thenit is impossible for it to establish new network connections..LPObject modules may be signed by trusted authorities who guaranteetheir validity and behavior, and these signatures may be checked bythe system the modules are accessed..LPAlthough Inferno provides a rich variety of authentication and securitymechanisms, as detailed below, few application programs need tobe aware of them or explicitly include coding to make use of them.Most often, access to resources across a secure communications linkis arranged in advance by the larger system in which the application operates.For example, when a client system uses a server systemand connection authentication or link encryption is appropriate,the server resources will most naturally be suppliedas a part of the application's name space.The communications channel that carries the Styx protocolcan be set to authenticate or encrypt; thereafter,all use of the resource is automatically protected..SHSecurity mechanisms.LPAuthentication and digital signatures are performed usingpublic key cryptography. Public keys are certified byInferno-based or other certifying authorities that sign the public keys with theirown private key..LPInferno uses encryption for:.IP •mutual authentication of communicating parties;.IP •authentication of messages between these parties; and.IP •encryption of messages between these parties..LPThe encryption algorithms provided by Infernoinclude the SHA, MD4, and MD5 secure hashes;Elgamal public key signatures and signature verification [4];RC4 encryption;DES encryption;and public key exchange based on the Diffie-Hellman scheme.The public key signatures use keys with moduli up to 4096 bits,512 bits by default..LPThere is no generally accepted national or international authorityfor storing or generating public or private encryption keys.Thus Inferno includes tools for using or implementing a trusted authority,but it does not itself provide the authority,which is an administrative function.Thus an organization using Inferno (or any other securityand key-distribution scheme) must design its system to suit itsown needs, and in particular decide whom to trust as a CertifyingAuthority (CA). However, the Inferno design is sufficiently flexibleand modular to accommodate the protocols likely to be attractive in practice..LPThe certifying authority that signs a user'spublic key determines the size of the key and the public keyalgorithm used. Tools provided withInferno use these signatures for authentication. Libraryinterfaces are provided for Limbo programs to sign and verifysignatures..LPGenerally authentication is performed using public key cryptography. Partiesregister by having their public keys signed by the certifying authority (CA).The signature covers a secure hash (SHA, MD4, or MD5) ofthe name of the party, his public key, and an expiration time. The signature,which contains the name of the signer, along with the signed information,is termed a.I "certificate" ..LPWhen parties communicate, they use the Station to Station protocol[5] toestablish the identities of the two parties and to create a mutually known secret.This STS protocol uses the Diffie-Hellman algorithm [6] to create this sharedsecret.The protocol is protected against replay attacks by choosing new randomparameters for each conversation. It is secured against `man inthe middle' attacks by having the parties exchange certificates and thendigitally signing key parts of the protocol. To masquerade as anotherparty an attacker would have to be able to forge that party's signature..SHLine Security.LPA network conversation can be secured against modification aloneor against both modification and snooping. To secure againstmodification, Inferno can append a secure MD5 or SHA hash (called a digest),.P1hash(secret, message, messageid).P2to each message..I "Messageid"is a 32 bit number that starts at 0 and is incremented byone for each message sent. Thus messages can be neitherchanged, removed, reordered or inserted into the stream without knowingthe secret or breaking the secure hash algorithm..LPTo secure against snooping, Inferno supports encryption of the complete conversationusing either RC4 or DES with either DES chain block coding (DESCBC)and electronic code book (DESECB)..LPInferno uses the same encapsulation format as Netscape's Secure Sockets Layer [7].It is possible to encapsulatea message stream in multiple encapsulations to provide varying degrees ofsecurity..SHRandom Numbers.LPThe strength of cryptographic algorithms depends in part on strengthof the random numbersused for choosing keys, Diffie-Hellman parameters, initialization vectors, etc.Inferno achieves this in two steps: a slow (100 to 200 bitper second) random bit stream comes from sampling the low order bits of afree running counter whenever a clock ticks. The clock must be unsynchronized,or at least poorly synchronized, with the counter. This generator is then used toalter the state of a faster pseudo-random number generator.Both the slow and fast generators were tested on a number of architecturesusing self correlation, random walk, and repeatability tests..SHIntroduction to Limbo.LPLimbo is the application programming language for the Inferno operating system. Although Limbo looks syntactically like C, it has a number of features that make it easier to use, safer, and more suited to the heterogeneous, networked Inferno environment: a rich set of basic types, strong typing, garbage collection, concurrency, communications, and modules. Limbo may be interpreted or compiled `just in time' for efficient, portable execution..LPThis paper introduces the language by studying an example of a complete, useful Limbo program. The program illustrates general programming as well as aspects of concurrency, graphics, module loading, and other features of Limbo and Inferno..SHThe problem.LPOur example program is a stripped-down version of the Inferno[14] program.CW "view" ,which displays graphical image files on the screen, one per window. This version sacrifices some functionality, generality, and error-checking but performs the basic job. The files may be in either GIF[12, 13] or JPEG[19] format and must be converted before display, or they may already be in the Inferno standard format that needs no conversion..CW "View"`sniffs' each file to determine what processing it requires, maps the colors if necessary, creates a new window, and copies the converted image to it. Each window is given a title bar across the top to identify it and hold the buttons to move and delete the window..SHThe Source.LPHere is the complete Limbo source for our version of.CW "view" ,annotated with line numbers for easy reference (Limbo, of course, does not use line numbers). Subsequent sections explain the workings of the program. Although the program is too large to absorb as a first example without some assistance, it's worth skimming before moving to the next section, to get an idea of the style of the language. Control syntax derives from C[11], while declaration syntax comes from the Pascal family of languages[17]. Limbo borrows features from a number of languages (e.g., tuples on lines 45 and 48) and introduces a few new ones (e.g. explicit module loading on lines 90 and 92)..P1 1 implement View;.P3 2 include "sys.m"; 3 sys: Sys;.P3 4 include "draw.m"; 5 draw: Draw; 6 Rect, Display, Image: import draw;.P3 7 include "bufio.m";.P3 8 include "imagefile.m";.P3 9 include "tk.m";10 tk: Tk;.P311 include "wmlib.m";12 wmlib: Wmlib;.P313 include "string.m";14 str: String;.P315 View: module16 {17 init: fn(ctxt: ref Draw->Context, argv: list of string);18 };.P319 init(ctxt: ref Draw->Context, argv: list of string)20 {21 sys = load Sys Sys->PATH;22 draw = load Draw Draw->PATH;23 tk = load Tk Tk->PATH;24 wmlib = load Wmlib Wmlib->PATH;25 str = load String String->PATH;26 wmlib->init();.P327 imageremap := load Imageremap Imageremap->PATH;28 bufio := load Bufio Bufio->PATH;.P329 argv = tl argv;30 if(argv != nil && str->prefix("-x ", hd argv))31 argv = tl argv;.P332 viewer := 0;33 while(argv != nil){34 file := hd argv;35 argv = tl argv;.P336 im := ctxt.display.open(file);37 if(im == nil){38 idec := filetype(file);39 if(idec == nil)40 continue;.P341 fd := bufio->open(file, Bufio->OREAD);42 if(fd == nil)43 continue;.P344 idec->init(bufio);45 (ri, err) := idec->read(fd);46 if(ri == nil)47 continue;.P348 (im, err) = imageremap->remap( ri, ctxt.display, 1);49 if(im == nil)50 continue;51 }.P352 spawn view(ctxt, im, file, viewer++);53 }54 }.P355 view(ctxt: ref Draw->Context, im: ref Image, file: string, viewer: int)56 {57 corner := string(25+20*(viewer%5));.P358 (nil, file) = str->splitr(file, "/");59 (t, menubut) := wmlib->titlebar(ctxt.screen, " -x "+corner+" -y "+corner+ " -bd 2 -relief raised", "View: "+file, Wmlib->Hide);.P360 event := chan of string;61 tk->namechan(t, event, "event");.P362 tk->cmd(t, "frame .im -height " + string im.r.dy() + " -width " + string im.r.dx());63 tk->cmd(t, "bind . <Configure> "+ "{send event resize}");64 tk->cmd(t, "bind . <Map> "+ "{send event resize}");65 tk->cmd(t, "pack .im -side bottom"+ " -fill both -expand 1");66 tk->cmd(t, "update");.P367 t.image.draw(posn(t), im, ctxt.display.ones, im.r.min);68 for(;;) alt{69 menu := <-menubut =>70 if(menu == "exit")71 return;72 wmlib->titlectl(t, menu);73 <-event =>74 t.image.draw(posn(t), im, ctxt.display.ones, im.r.min);75 }76 }.P377 posn(t: ref Tk->Toplevel): Rect78 {79 minx := int tk->cmd(t, ".im cget -actx");80 miny := int tk->cmd(t, ".im cget -acty");81 maxx := minx + int tk->cmd(t, ".im cget -actwidth");82 maxy := miny + int tk->cmd(t, ".im cget -actheight");.P383 return ((minx, miny), (maxx, maxy));84 }.P385 filetype(file: string): RImagefile86 {87 if(len file>4 && file[len file-4:]==".gif")88 r := load RImagefile RImagefile->READGIFPATH;89 if(len file>4 && file[len file-4:]==".jpg")90 r = load RImagefile RImagefile->READJPGPATH;Lines 1–500 of 1073. Load more
.TL The Inferno Operating System .AU Sean Dorward Rob Pike David Leo Presotto Dennis M. Ritchie Howard Trickey Phil Winterbottom .AI Computing Science Research Center Lucent Technologies, Bell Labs Murray Hill, New Jersey USA .FS .FA Originally appeared in the .I "Bell Labs Technical Journal" , Vol. 2, No. 1, Winter 1997, pp. 5-18. .br Minor revisions have been made by Vita Nuova to reflect subsequent changes to Inferno. .br Copyright © 1997 Lucent Technologies Inc. All rights reserved. .FE .AB Inferno is an operating system for creating and supporting distributed services. It was originally developed by the Computing Science Research Center of Bell Labs, the R&D arm of Lucent Technologies, and further developed by other groups in Lucent. .LP Inferno was designed specifically as a commercial product, both for licensing in the marketplace and for use within new Lucent offerings. It encapsulates many years of Bell Labs research in operating systems, languages, on-the-fly compilers, graphics, security, networking and portability. .AE .SH Introduction .LP Inferno is intended to be used in a variety of network environments, for example those supporting advanced telephones, hand-held devices, TV set-top boxes attached to cable or satellite systems, and inexpensive Internet computers, but also in conjunction with traditional computing systems. .LP The most visible new environments involve cable television, direct satellite broadcast, the Internet, and other networks. As the entertainment, telecommunications, and computing industries converge and interconnect, a variety of public data networks are emerging, each potentially as useful and profitable as the telephone system. Unlike the telephone system, which started with standard terminals and signaling, these networks are developing in a world of diverse terminals, network hardware, and protocols. Only a well-designed, economical operating system can insulate the various providers of content and services from the equally varied transport and presentation platforms. Inferno is a network operating system for this new world. .LP Inferno's definitive strength lies in its portability and versatility across several dimensions: .IP • Portability across processors: it currently runs on Intel, Sparc, MIPS, ARM, HP-PA, and PowerPC architectures and is readily portable to others. .IP • Portability across environments: it runs as a stand-alone operating system on small terminals, and also as a user application under Windows NT, Windows 95, Unix (Irix, Solaris, FreeBSD, Linux, AIX, HP/UX) and Plan 9. In all of these environments, Inferno applications see an identical interface. .IP • Distributed design: the identical environment is established at the user's terminal and at the server, and each may import the resources (for example, the attached I/O devices or networks) of the other. Aided by the communications facilities of the run-time system, applications may be split easily (and even dynamically) between client and server. .IP • Minimal hardware requirements: it runs useful applications stand-alone on machines with as little as 1 MB of memory, and does not require memory-mapping hardware. .IP • Portable applications: Inferno applications are written in the type-safe language Limbo, whose binary representation is identical over all platforms. .IP • Dynamic adaptability: applications may, depending on the hardware or other resources available, load different program modules to perform a specific function. For example, a video player application might use any of several different decoder modules. .LP Underlying the design of Inferno is a model of the diversity of application areas it intends to stimulate. Many providers are interested in purveying media and services: telephone network service providers, WWW servers, cable companies, merchants, various information providers. There are many connection technologies: ordinary telephone modems, ISDN, ATM, the Internet, analog broadcast or cable TV, cable modems, digital video on demand, and other interactive TV systems. .LP Applications more clearly related to Lucent's current and planned product offerings include control of switches and routers, and the associated operations system facilities needed to support them. For example, Inferno software controls an IP switch/router for voice and data being developed by Lucent's Bell Labs research and Network Systems organizations. An Inferno-based firewall (Signet) is being used to secure outside access to the Research Internet connection. .LP Finally, there are existing or potential hardware endpoints. Some are in consumers' homes: PCs, game consoles, newer set-top boxes. Some are inside the networks themselves: nodes for billing, network monitoring or provisioning. The higher ends of these spectra, epitomized by fully interactive TV with video on demand, may be fascinating, but have developed more slowly than expected. One reason is the cost of the set-top box, especially its memory requirements. Portable terminals, because of weight and cost considerations, are similarly constrained. .LP Inferno is parsimonious enough in its resource requirements to support interesting applications on today's hardware, while being versatile enough to grow into the future. In particular, it enables developers to create applications that will work across a range of facilities. An example: an interactive shopping catalog that works in text mode over a POTS modem, shows still pictures (perhaps with audio) of the merchandise over ISDN, and includes video clips over digital cable. .LP Clearly not everyone who deploys an Inferno-based solution will want to span the whole range of possibilities, but the system architecture should be constrained only by the desired markets and the available interconnection and server technologies, not by the software. .SH Inferno interfaces .LP The role of the Inferno system is to .I "create" several standard interfaces for its applications: .IP • Applications use various resources internal to the system, such as a consistent virtual machine that runs the application programs, together with library modules that perform services as simple as string manipulation through more sophisticated graphics services for dealing with text, pictures, higher-level toolkits, and video. .IP • Applications exist in an external environment containing resources such as data files that can be read and manipulated, together with objects that are named and manipulated like files but are more active. Devices (for example a hand-held remote control, an MPEG decoder or a network interface) present themselves to the application as files. .IP • Standard protocols exist for communication within and between separate machines running Inferno, so that applications can cooperate. .LP At the same time, Inferno .I uses interfaces supplied by an existing environment, either bare hardware or standard operating systems and protocols. .LP Most typically, an Inferno-based service would consist of many relatively cheap terminals running Inferno as a native system, and a smaller number of large machines running Inferno as a hosted system. On these server machines Inferno might interface to databases, transaction systems, existing OA&M facilities, and other resources provided under the native operating system. The Inferno applications themselves would run either on the client or server machines, or both. .SH External Environment of Inferno Applications .LP The purpose of most Inferno applications is to present information or media to the user; thus applications must locate the information sources in the network and construct a local representation of them. The information flow is not one-way: the user's terminal (whether a network computer, TV set-top, PC, or videophone) is also an information source and its devices represent resources to applications. Inferno draws heavily on the design of the Plan 9 operating system [1] in the way it presents resources to these applications. .LP The design has three principles. .IP • All resources are named and accessed like files in a forest of hierarchical file systems. .IP • The disjoint resource hierarchies provided by different services are joined together into a single private hierarchical .I "name space" . .IP • A communication protocol, called .I "Styx" , is applied uniformly to access these resources, whether local or remote. .LP In practice, most applications see a fixed set of files organized as a directory tree. Some of the files contain ordinary data, but others represent more active resources. Devices are represented as files, and device drivers (such as a modem, an MPEG decoder, a network interface, or the TV screen) attached to a particular hardware box present themselves as small directories. These directories typically containing two files, .CW "data" and .CW "ctl" , which respectively perform actual device input/output and control operations. System services also live behind file names. For example, an Internet domain name server might be attached to an agreed-upon name (say .CW "/net/dns" ); after writing to this file a string representing a symbolic Internet domain name, a subsequent read from the file would return the corresponding numeric Internet address. .LP The glue that connects the separate parts of the resource name space together is the Styx protocol. Within an instance of Inferno, all the device drivers and other internal resources respond to the procedural version of Styx. The Inferno kernel implements a .I "mount driver" that transforms file system operations into remote procedure calls for transport over a network. On the other side of the connection, a server unwraps the Styx messages and implements them using resources local to it. Thus, it is possible to import parts of the name space (and thus resources) from other machines. .LP To extend the example above, it is unlikely that a set-top box would store the code needed for an Internet domain name-server within itself. Instead, an Internet browser would import the .CW "/net/dns" resource into its own name space from a server machine across a network. .LP The Styx protocol lies above and is independent of the communications transport layer; it is readily carried over TCP/IP, PPP, ATM or various modem transport protocols. .SH Internal Environment of Inferno Applications .LP Inferno applications are written in a new language called Limbo [2], which was designed specifically for the Inferno environment. Its syntax is influenced by C and Pascal, and it supports the standard data types common to them, together with several higher-level data types such as lists, tuples, strings, dynamic arrays, and simple abstract data types. .LP In addition, Limbo supplies several advanced constructs carefully integrated into the Inferno virtual machine. In particular, a communication mechanism called a .I "channel" is used to connect different Limbo tasks on the same machine or across the network. A channel transports typed data in a machine-independent fashion, so that complex data structures (including channels themselves) may be passed between Limbo tasks or attached to files in the name space for language-level communication between machines. .LP Multi-tasking is supported directly by the Limbo language: independently scheduled threads of control may be spawned, and an .CW "alt" statement is used to coordinate the channel communication between tasks (that is, .CW "alt" is used to select one of several channels that are ready to communicate). By building channels and tasks into the language and its virtual machine, Inferno encourages a communication style that is easy to use and safe. .LP Limbo programs are built of .I "modules" , which are self-contained units with a well-defined interface containing functions (methods), abstract data types, and constants defined by the module and visible outside it. Modules are accessed dynamically; that is, when one module wishes to make use of another, it dynamically executes a .CW "load" statement naming the desired module, and uses a returned handle to access the new module. When the module is no longer in use, its storage and code will be released. The flexibility of the modular structure contributes to the smallness of typical Inferno applications, and also to their adaptability. For example, in the shopping catalog described above, the application's main module checks dynamically for the existence of the video resource. If it is unavailable, the video-decoder module is never loaded. .LP Limbo is fully type-checked at compile- and run-time; for example, pointers, besides being more restricted than in C, are checked before being dereferenced, and the type-consistency of a dynamically loaded module is checked when it is loaded. Limbo programs run safely on a machine without memory-protection hardware. Moreover, all Limbo data and program objects are subject to a garbage collector, built deeply into the Limbo run-time system. All system data objects are tracked by the virtual machine and freed as soon as they become unused. For example, if an application task creates a graphics window and then terminates, the window automatically disappears the instant the last reference to it has gone away. .LP Limbo programs are compiled into byte-codes representing instructions for a virtual machine called Dis. The architecture of the arithmetic part of Dis is a simple 3-address machine, supplemented with a few specialized operations for handling some of the higher-level data types like arrays and strings. Garbage collection is handled below the level of the machine language; the scheduling of tasks is similarly hidden. When loaded into memory for execution, the byte-codes are expanded into a format more efficient for execution; there is also an optional on-the-fly compiler that turns a Dis instruction stream into native machine instructions for the appropriate real hardware. This can be done efficiently because Dis instructions match well with the instruction-set architecture of today's machines. The resulting code executes at a speed approaching that of compiled C. .LP Underlying Dis is the Inferno kernel, which contains the interpreter and on-the-fly compiler as well as memory management, scheduling, device drivers, protocol stacks, and the like. The kernel also contains the core of the file system (the name evaluator and the code that turns file system operations into remote procedure calls over communications links) as well as the small file systems implemented internally. .LP Finally, the Inferno virtual machine implements several standard modules internally. These include .CW "Sys" , which provides system calls and a small library of useful routines (e.g. creation of network connections, string manipulations). Module .CW "Draw" is a basic graphics library that handles raster graphics, fonts, and windows. Module .CW "Prefab" builds on .CW "Draw" to provide structured complexes containing images and text inside of windows; these elements may be scrolled, selected, and changed by the methods of .CW "Prefab" . Module .CW "Tk" is an all-new implementation of the Tk graphics toolkit [18], with a Limbo interface. A .CW "Math" module encapsulates the procedures for numerical programming. .SH The Environment of the Inferno System .LP Inferno creates a standard environment for applications. Identical application programs can run under any instance of this environment, even in distributed fashion, and see the same resources. Depending on the environment in which Inferno itself is implemented, there are several versions of the Inferno kernel, Dis/Limbo interpreter, and device driver set. .LP When running as the native operating system, the kernel includes all the low-level glue (interrupt handlers, graphics and other device drivers) needed to implement the abstractions presented to applications. For a hosted system, for example under Unix, Windows NT or Windows 95, Inferno runs as a set of ordinary processes. Instead of mapping its device-control functionality to real hardware, it adapts to the resources provided by the operating system under which it runs. For example, under Unix, the graphics library might be implemented using the X window system and the networking using the socket interface; under Windows, it uses the native Windows graphics and Winsock calls. .LP Inferno is, to the extent possible, written in standard C and most of its components are independent of the many operating systems that can host it. .SH Security in Inferno .LP Inferno provides security of communication, resource control, and system integrity. .LP Each external communication channel may be transmitted in the clear, accompanied by message digests to prevent corruption, or encrypted to prevent corruption and interception. Once communication is set up, the encryption is transparent to the application. Key exchange is provided through standard public-key mechanisms; after key exchange, message digesting and line encryption likewise use standard symmetric mechanisms. .LP Inferno is secure against erroneous or malicious applications, and encourages safe collaboration between mutually suspicious service providers and clients. The resources available to applications appear exclusively in the name space of the application, and standard protection modes are available. This applies to data, to communication resources, and to the executable modules that constitute the applications. Security-sensitive resources of the system are accessible only by calling the modules that provide them; in particular, adding new files and servers to the name space is controlled and is an authenticated operation. For example, if the network resources are removed from an application's name space, then it is impossible for it to establish new network connections. .LP Object modules may be signed by trusted authorities who guarantee their validity and behavior, and these signatures may be checked by the system the modules are accessed. .LP Although Inferno provides a rich variety of authentication and security mechanisms, as detailed below, few application programs need to be aware of them or explicitly include coding to make use of them. Most often, access to resources across a secure communications link is arranged in advance by the larger system in which the application operates. For example, when a client system uses a server system and connection authentication or link encryption is appropriate, the server resources will most naturally be supplied as a part of the application's name space. The communications channel that carries the Styx protocol can be set to authenticate or encrypt; thereafter, all use of the resource is automatically protected. .SH Security mechanisms .LP Authentication and digital signatures are performed using public key cryptography. Public keys are certified by Inferno-based or other certifying authorities that sign the public keys with their own private key. .LP Inferno uses encryption for: .IP • mutual authentication of communicating parties; .IP • authentication of messages between these parties; and .IP • encryption of messages between these parties. .LP The encryption algorithms provided by Inferno include the SHA, MD4, and MD5 secure hashes; Elgamal public key signatures and signature verification [4]; RC4 encryption; DES encryption; and public key exchange based on the Diffie-Hellman scheme. The public key signatures use keys with moduli up to 4096 bits, 512 bits by default. .LP There is no generally accepted national or international authority for storing or generating public or private encryption keys. Thus Inferno includes tools for using or implementing a trusted authority, but it does not itself provide the authority, which is an administrative function. Thus an organization using Inferno (or any other security and key-distribution scheme) must design its system to suit its own needs, and in particular decide whom to trust as a Certifying Authority (CA). However, the Inferno design is sufficiently flexible and modular to accommodate the protocols likely to be attractive in practice. .LP The certifying authority that signs a user's public key determines the size of the key and the public key algorithm used. Tools provided with Inferno use these signatures for authentication. Library interfaces are provided for Limbo programs to sign and verify signatures. .LP Generally authentication is performed using public key cryptography. Parties register by having their public keys signed by the certifying authority (CA). The signature covers a secure hash (SHA, MD4, or MD5) of the name of the party, his public key, and an expiration time. The signature, which contains the name of the signer, along with the signed information, is termed a .I "certificate" . .LP When parties communicate, they use the Station to Station protocol[5] to establish the identities of the two parties and to create a mutually known secret. This STS protocol uses the Diffie-Hellman algorithm [6] to create this shared secret. The protocol is protected against replay attacks by choosing new random parameters for each conversation. It is secured against `man in the middle' attacks by having the parties exchange certificates and then digitally signing key parts of the protocol. To masquerade as another party an attacker would have to be able to forge that party's signature. .SH Line Security .LP A network conversation can be secured against modification alone or against both modification and snooping. To secure against modification, Inferno can append a secure MD5 or SHA hash (called a digest), .P1 hash(secret, message, messageid) .P2 to each message. .I "Messageid" is a 32 bit number that starts at 0 and is incremented by one for each message sent. Thus messages can be neither changed, removed, reordered or inserted into the stream without knowing the secret or breaking the secure hash algorithm. .LP To secure against snooping, Inferno supports encryption of the complete conversation using either RC4 or DES with either DES chain block coding (DESCBC) and electronic code book (DESECB). .LP Inferno uses the same encapsulation format as Netscape's Secure Sockets Layer [7]. It is possible to encapsulate a message stream in multiple encapsulations to provide varying degrees of security. .SH Random Numbers .LP The strength of cryptographic algorithms depends in part on strength of the random numbers used for choosing keys, Diffie-Hellman parameters, initialization vectors, etc. Inferno achieves this in two steps: a slow (100 to 200 bit per second) random bit stream comes from sampling the low order bits of a free running counter whenever a clock ticks. The clock must be unsynchronized, or at least poorly synchronized, with the counter. This generator is then used to alter the state of a faster pseudo-random number generator. Both the slow and fast generators were tested on a number of architectures using self correlation, random walk, and repeatability tests. .SH Introduction to Limbo .LP Limbo is the application programming language for the Inferno operating system. Although Limbo looks syntactically like C, it has a number of features that make it easier to use, safer, and more suited to the heterogeneous, networked Inferno environment: a rich set of basic types, strong typing, garbage collection, concurrency, communications, and modules. Limbo may be interpreted or compiled `just in time' for efficient, portable execution. .LP This paper introduces the language by studying an example of a complete, useful Limbo program. The program illustrates general programming as well as aspects of concurrency, graphics, module loading, and other features of Limbo and Inferno. .SH The problem .LP Our example program is a stripped-down version of the Inferno[14] program .CW "view" , which displays graphical image files on the screen, one per window. This version sacrifices some functionality, generality, and error-checking but performs the basic job. The files may be in either GIF[12, 13] or JPEG[19] format and must be converted before display, or they may already be in the Inferno standard format that needs no conversion. .CW "View" `sniffs' each file to determine what processing it requires, maps the colors if necessary, creates a new window, and copies the converted image to it. Each window is given a title bar across the top to identify it and hold the buttons to move and delete the window. .SH The Source .LP Here is the complete Limbo source for our version of .CW "view" , annotated with line numbers for easy reference (Limbo, of course, does not use line numbers). Subsequent sections explain the workings of the program. Although the program is too large to absorb as a first example without some assistance, it's worth skimming before moving to the next section, to get an idea of the style of the language. Control syntax derives from C[11], while declaration syntax comes from the Pascal family of languages[17]. Limbo borrows features from a number of languages (e.g., tuples on lines 45 and 48) and introduces a few new ones (e.g. explicit module loading on lines 90 and 92). .P1 1 implement View; .P3 2 include "sys.m"; 3 sys: Sys; .P3 4 include "draw.m"; 5 draw: Draw; 6 Rect, Display, Image: import draw; .P3 7 include "bufio.m"; .P3 8 include "imagefile.m"; .P3 9 include "tk.m"; 10 tk: Tk; .P3 11 include "wmlib.m"; 12 wmlib: Wmlib; .P3 13 include "string.m"; 14 str: String; .P3 15 View: module 16 { 17 init: fn(ctxt: ref Draw->Context, argv: list of string); 18 }; .P3 19 init(ctxt: ref Draw->Context, argv: list of string) 20 { 21 sys = load Sys Sys->PATH; 22 draw = load Draw Draw->PATH; 23 tk = load Tk Tk->PATH; 24 wmlib = load Wmlib Wmlib->PATH; 25 str = load String String->PATH; 26 wmlib->init(); .P3 27 imageremap := load Imageremap Imageremap->PATH; 28 bufio := load Bufio Bufio->PATH; .P3 29 argv = tl argv; 30 if(argv != nil && str->prefix("-x ", hd argv)) 31 argv = tl argv; .P3 32 viewer := 0; 33 while(argv != nil){ 34 file := hd argv; 35 argv = tl argv; .P3 36 im := ctxt.display.open(file); 37 if(im == nil){ 38 idec := filetype(file); 39 if(idec == nil) 40 continue; .P3 41 fd := bufio->open(file, Bufio->OREAD); 42 if(fd == nil) 43 continue; .P3 44 idec->init(bufio); 45 (ri, err) := idec->read(fd); 46 if(ri == nil) 47 continue; .P3 48 (im, err) = imageremap->remap( ri, ctxt.display, 1); 49 if(im == nil) 50 continue; 51 } .P3 52 spawn view(ctxt, im, file, viewer++); 53 } 54 } .P3 55 view(ctxt: ref Draw->Context, im: ref Image, file: string, viewer: int) 56 { 57 corner := string(25+20*(viewer%5)); .P3 58 (nil, file) = str->splitr(file, "/"); 59 (t, menubut) := wmlib->titlebar(ctxt.screen, " -x "+corner+" -y "+corner+ " -bd 2 -relief raised", "View: "+file, Wmlib->Hide); .P3 60 event := chan of string; 61 tk->namechan(t, event, "event"); .P3 62 tk->cmd(t, "frame .im -height " + string im.r.dy() + " -width " + string im.r.dx()); 63 tk->cmd(t, "bind . <Configure> "+ "{send event resize}"); 64 tk->cmd(t, "bind . <Map> "+ "{send event resize}"); 65 tk->cmd(t, "pack .im -side bottom"+ " -fill both -expand 1"); 66 tk->cmd(t, "update"); .P3 67 t.image.draw(posn(t), im, ctxt.display.ones, im.r.min); 68 for(;;) alt{ 69 menu := <-menubut => 70 if(menu == "exit") 71 return; 72 wmlib->titlectl(t, menu); 73 <-event => 74 t.image.draw(posn(t), im, ctxt.display.ones, im.r.min); 75 } 76 } .P3 77 posn(t: ref Tk->Toplevel): Rect 78 { 79 minx := int tk->cmd(t, ".im cget -actx"); 80 miny := int tk->cmd(t, ".im cget -acty"); 81 maxx := minx + int tk->cmd(t, ".im cget -actwidth"); 82 maxy := miny + int tk->cmd(t, ".im cget -actheight"); .P3 83 return ((minx, miny), (maxx, maxy)); 84 } .P3 85 filetype(file: string): RImagefile 86 { 87 if(len file>4 && file[len file-4:]==".gif") 88 r := load RImagefile RImagefile->READGIFPATH; 89 if(len file>4 && file[len file-4:]==".jpg") 90 r = load RImagefile RImagefile->READJPGPATH;