1.TL 2The Inferno Operating System 3.AU 4Sean Dorward 5Rob Pike 6David Leo Presotto 7Dennis M. Ritchie 8Howard Trickey 9Phil Winterbottom 10.AI 11Computing Science Research Center 12Lucent Technologies, Bell Labs 13Murray Hill, New Jersey 14USA 15.FS 16.FA 17Originally appeared in the 18.I "Bell Labs Technical Journal" , 19Vol. 2, No. 1, Winter 1997, pp. 5-18. 20.br 21Minor revisions have been made by Vita Nuova to reflect subsequent changes to Inferno. 22.br 23Copyright © 1997 Lucent Technologies Inc. All rights reserved. 24.FE 25.AB 26Inferno is an operating system for creating and supporting distributed services. 27It was originally developed by the Computing Science Research Center of Bell Labs, the R&D arm of Lucent Technologies, and 28further developed by other groups in Lucent. 29.LP 30Inferno was designed specifically as a commercial product, both for licensing 31in the marketplace and for use within new Lucent offerings. 32It encapsulates many years of Bell Labs research in operating systems, languages, on-the-fly compilers, graphics, security, networking and portability. 33.AE 34.SH 35Introduction 36.LP 37Inferno is intended to be used in a variety of network environments, for example those supporting 38advanced 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. 39.LP 40The 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 41platforms. Inferno is a network operating system for this new world. 42.LP 43Inferno's definitive strength lies in its portability and versatility across several dimensions: 44.IP • 45Portability across processors: it currently runs on Intel, Sparc, MIPS, ARM, HP-PA, and PowerPC architectures and is readily portable to others. 46.IP • 47Portability 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. 48.IP • 49Distributed 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. 50.IP • 51Minimal 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. 52.IP • 53Portable applications: Inferno applications are written in the type-safe language Limbo, whose binary representation is identical over all platforms. 54.IP • 55Dynamic 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. 56.LP 57Underlying 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. 58There 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. 59.LP 60Applications more clearly related to Lucent's current and planned product offerings include 61control of switches and routers, and the associated operations system facilities needed to support them. 62For example, Inferno software controls an IP switch/router for voice and data being 63developed by Lucent's Bell Labs research and Network Systems organizations. 64An Inferno-based firewall (Signet) is being used to secure outside access to the Research 65Internet connection. 66.LP 67Finally, there are existing or potential hardware endpoints. Some are in consumers' homes: PCs, 68game 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. 69.LP 70Inferno 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. 71.LP 72Clearly 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. 73.SH 74Inferno interfaces 75.LP 76The role of the Inferno system is to 77.I "create" 78several standard interfaces for its applications: 79.IP • 80Applications 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, 81higher-level toolkits, and video. 82.IP • 83Applications 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. 84.IP • 85Standard protocols exist for communication within and between separate machines running Inferno, so that applications can cooperate. 86.LP 87At the same time, Inferno 88.I uses 89interfaces supplied by an existing environment, either bare hardware or standard operating systems and protocols. 90.LP 91Most 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. 92.SH 93External Environment of Inferno Applications 94.LP 95The 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. 96.LP 97The design has three principles. 98.IP • 99All resources are named and accessed like files in a forest of hierarchical file systems. 100.IP • 101The disjoint resource hierarchies provided by different services are joined together into a single private hierarchical 102.I "name space" . 103.IP • 104A communication protocol, called 105.I "Styx" , 106is applied uniformly to access these resources, whether local or remote. 107.LP 108In 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, 109.CW "data" 110and 111.CW "ctl" , 112which 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 113.CW "/net/dns" ); 114after 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. 115.LP 116The glue that connects the separate parts of the resource name space together is the Styx protocol. 117Within an instance of Inferno, all the device drivers and other internal resources respond to the procedural version of Styx. The Inferno kernel implements a 118.I "mount driver" 119that 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. 120.LP 121To 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 122.CW "/net/dns" 123resource into its own name space from a server machine across a network. 124.LP 125The 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. 126.SH 127Internal Environment of Inferno Applications 128.LP 129Inferno 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. 130.LP 131In addition, Limbo supplies several advanced constructs carefully integrated into the Inferno virtual machine. In particular, a communication mechanism called a 132.I "channel" 133is used to connect different Limbo tasks on the same machine or across the network. 134A 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. 135.LP 136Multi-tasking is supported directly by the Limbo language: independently scheduled threads of control may be spawned, and an 137.CW "alt" 138statement is used to coordinate the channel communication 139between tasks (that is, 140.CW "alt" 141is used to select one of several channels that are ready to communicate). 142By building channels and tasks into the language and its virtual machine, Inferno encourages a communication style that is easy to use and safe. 143.LP 144Limbo programs are built of 145.I "modules" , 146which are self-contained units with a well-defined interface 147containing 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 148.CW "load" 149statement naming the desired module, and uses a returned handle to access the new module. 150When the module is no longer in use, its storage and code will be released. 151The flexibility of the modular structure contributes to the smallness of typical Inferno applications, and also to their adaptability. 152For example, in the shopping catalog described above, 153the application's main module checks dynamically for the existence of the video resource. 154If it is unavailable, the video-decoder module is never loaded. 155.LP 156Limbo is fully type-checked at compile- and run-time; for example, pointers, besides being more 157restricted 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 158without memory-protection hardware. 159Moreover, all Limbo data and program objects are subject to 160a 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. 161.LP 162Limbo programs are compiled into byte-codes representing instructions for a virtual machine called 163Dis. 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 164into 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. 165.LP 166Underlying 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. 167The 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. 168.LP 169Finally, the Inferno virtual machine implements several standard modules internally. These include 170.CW "Sys" , 171which provides system calls and a small library of useful routines (e.g. creation of network connections, string manipulations). Module 172.CW "Draw" 173is a basic graphics library that handles raster graphics, fonts, and windows. Module 174.CW "Prefab" 175builds on 176.CW "Draw" 177to provide structured complexes containing images and text inside of windows; these elements may be scrolled, selected, and changed by the methods of 178.CW "Prefab" . 179Module 180.CW "Tk" 181is an all-new implementation of the Tk graphics toolkit [18], with a Limbo interface. A 182.CW "Math" 183module encapsulates the procedures for numerical programming. 184.SH 185The Environment of the Inferno System 186.LP 187Inferno creates a standard environment for applications. Identical application programs can run 188under any instance of this environment, even in distributed fashion, and see the same resources. 189Depending on the environment in which Inferno itself is implemented, there are several versions of the Inferno kernel, Dis/Limbo interpreter, and device driver set. 190.LP 191When 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. 192For a hosted system, for example under Unix, Windows NT or Windows 95, Inferno runs as a set of ordinary processes. 193Instead of mapping its device-control functionality to real hardware, 194it adapts to the resources provided by the operating system under which it runs. 195For 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. 196.LP 197Inferno 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. 198.SH 199Security in Inferno 200.LP 201Inferno provides security of communication, resource control, and 202system integrity. 203.LP 204Each external communication channel may be transmitted in the clear, 205accompanied by message digests to prevent corruption, or encrypted to 206prevent corruption and interception. Once communication is set up, 207the encryption is transparent to the application. Key exchange is 208provided through standard public-key mechanisms; after key exchange, 209message digesting and line encryption likewise use standard symmetric 210mechanisms. 211.LP 212Inferno is secure against erroneous or malicious applications, and 213encourages safe collaboration between mutually suspicious service 214providers and clients. The resources available to applications appear 215exclusively in the name space of the application, and standard 216protection modes are available. This applies to data, to 217communication resources, and to the executable modules that constitute 218the applications. Security-sensitive resources of the system are 219accessible only by calling the modules that provide them; in 220particular, adding new files and servers to the name space is 221controlled and is an authenticated operation. For example, if the 222network resources are removed from an application's name space, then 223it is impossible for it to establish new network connections. 224.LP 225Object modules may be signed by trusted authorities who guarantee 226their validity and behavior, and these signatures may be checked by 227the system the modules are accessed. 228.LP 229Although Inferno provides a rich variety of authentication and security 230mechanisms, as detailed below, few application programs need to 231be aware of them or explicitly include coding to make use of them. 232Most often, access to resources across a secure communications link 233is arranged in advance by the larger system in which the application operates. 234For example, when a client system uses a server system 235and connection authentication or link encryption is appropriate, 236the server resources will most naturally be supplied 237as a part of the application's name space. 238The communications channel that carries the Styx protocol 239can be set to authenticate or encrypt; thereafter, 240all use of the resource is automatically protected. 241.SH 242Security mechanisms 243.LP 244Authentication and digital signatures are performed using 245public key cryptography. Public keys are certified by 246Inferno-based or other certifying authorities that sign the public keys with their 247own private key. 248.LP 249Inferno uses encryption for: 250.IP • 251mutual authentication of communicating parties; 252.IP • 253authentication of messages between these parties; and 254.IP • 255encryption of messages between these parties. 256.LP 257The encryption algorithms provided by Inferno 258include the SHA, MD4, and MD5 secure hashes; 259Elgamal public key signatures and signature verification [4]; 260RC4 encryption; 261DES encryption; 262and public key exchange based on the Diffie-Hellman scheme. 263The public key signatures use keys with moduli up to 4096 bits, 264512 bits by default. 265.LP 266There is no generally accepted national or international authority 267for storing or generating public or private encryption keys. 268Thus Inferno includes tools for using or implementing a trusted authority, 269but it does not itself provide the authority, 270which is an administrative function. 271Thus an organization using Inferno (or any other security 272and key-distribution scheme) must design its system to suit its 273own needs, and in particular decide whom to trust as a Certifying 274Authority (CA). However, the Inferno design is sufficiently flexible 275and modular to accommodate the protocols likely to be attractive in practice. 276.LP 277The certifying authority that signs a user's 278public key determines the size of the key and the public key 279algorithm used. Tools provided with 280Inferno use these signatures for authentication. Library 281interfaces are provided for Limbo programs to sign and verify 282signatures. 283.LP 284Generally authentication is performed using public key cryptography. Parties 285register by having their public keys signed by the certifying authority (CA). 286The signature covers a secure hash (SHA, MD4, or MD5) of 287the name of the party, his public key, and an expiration time. The signature, 288which contains the name of the signer, along with the signed information, 289is termed a 290.I "certificate" . 291.LP 292When parties communicate, they use the Station to Station protocol[5] to 293establish the identities of the two parties and to create a mutually known secret. 294This STS protocol uses the Diffie-Hellman algorithm [6] to create this shared 295secret. 296The protocol is protected against replay attacks by choosing new random 297parameters for each conversation. It is secured against `man in 298the middle' attacks by having the parties exchange certificates and then 299digitally signing key parts of the protocol. To masquerade as another 300party an attacker would have to be able to forge that party's signature. 301.SH 302Line Security 303.LP 304A network conversation can be secured against modification alone 305or against both modification and snooping. To secure against 306modification, Inferno can append a secure MD5 or SHA hash (called a digest), 307.P1 308hash(secret, message, messageid) 309.P2 310to each message. 311.I "Messageid" 312is a 32 bit number that starts at 0 and is incremented by 313one for each message sent. Thus messages can be neither 314changed, removed, reordered or inserted into the stream without knowing 315the secret or breaking the secure hash algorithm. 316.LP 317To secure against snooping, Inferno supports encryption of the complete conversation 318using either RC4 or DES with either DES chain block coding (DESCBC) 319and electronic code book (DESECB). 320.LP 321Inferno uses the same encapsulation format as Netscape's Secure Sockets Layer [7]. 322It is possible to encapsulate 323a message stream in multiple encapsulations to provide varying degrees of 324security. 325.SH 326Random Numbers 327.LP 328The strength of cryptographic algorithms depends in part on strength 329of the random numbers 330used for choosing keys, Diffie-Hellman parameters, initialization vectors, etc. 331Inferno achieves this in two steps: a slow (100 to 200 bit 332per second) random bit stream comes from sampling the low order bits of a 333free running counter whenever a clock ticks. The clock must be unsynchronized, 334or at least poorly synchronized, with the counter. This generator is then used to 335alter the state of a faster pseudo-random number generator. 336Both the slow and fast generators were tested on a number of architectures 337using self correlation, random walk, and repeatability tests. 338.SH 339Introduction to Limbo 340.LP 341Limbo 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. 342.LP 343This 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. 344.SH 345The problem 346.LP 347Our example program is a stripped-down version of the Inferno[14] program 348.CW "view" , 349which 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. 350.CW "View" 351`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. 352.SH 353The Source 354.LP 355Here is the complete Limbo source for our version of 356.CW "view" , 357annotated 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). 358.P1 359 1 implement View; 360.P3 361 2 include "sys.m"; 362 3 sys: Sys; 363.P3 364 4 include "draw.m"; 365 5 draw: Draw; 366 6 Rect, Display, Image: import draw; 367.P3 368 7 include "bufio.m"; 369.P3 370 8 include "imagefile.m"; 371.P3 372 9 include "tk.m"; 37310 tk: Tk; 374.P3 37511 include "wmlib.m"; 37612 wmlib: Wmlib; 377.P3 37813 include "string.m"; 37914 str: String; 380.P3 38115 View: module 38216 { 38317 init: fn(ctxt: ref Draw->Context, 384 argv: list of string); 38518 }; 386.P3 38719 init(ctxt: ref Draw->Context, 388 argv: list of string) 38920 { 39021 sys = load Sys Sys->PATH; 39122 draw = load Draw Draw->PATH; 39223 tk = load Tk Tk->PATH; 39324 wmlib = load Wmlib Wmlib->PATH; 39425 str = load String String->PATH; 39526 wmlib->init(); 396.P3 39727 imageremap := load Imageremap 398 Imageremap->PATH; 39928 bufio := load Bufio Bufio->PATH; 400.P3 40129 argv = tl argv; 40230 if(argv != nil 403 && str->prefix("-x ", hd argv)) 40431 argv = tl argv; 405.P3 40632 viewer := 0; 40733 while(argv != nil){ 40834 file := hd argv; 40935 argv = tl argv; 410.P3 41136 im := ctxt.display.open(file); 41237 if(im == nil){ 41338 idec := filetype(file); 41439 if(idec == nil) 41540 continue; 416.P3 41741 fd := bufio->open(file, 418 Bufio->OREAD); 41942 if(fd == nil) 42043 continue; 421.P3 42244 idec->init(bufio); 42345 (ri, err) := idec->read(fd); 42446 if(ri == nil) 42547 continue; 426.P3 42748 (im, err) = imageremap->remap( 428 ri, ctxt.display, 1); 42949 if(im == nil) 43050 continue; 43151 } 432.P3 43352 spawn view(ctxt, im, file, 434 viewer++); 43553 } 43654 } 437.P3 43855 view(ctxt: ref Draw->Context, 439 im: ref Image, file: string, 440 viewer: int) 44156 { 44257 corner := string(25+20*(viewer%5)); 443.P3 44458 (nil, file) = str->splitr(file, "/"); 44559 (t, menubut) := wmlib->titlebar(ctxt.screen, 446 " -x "+corner+" -y "+corner+ 447 " -bd 2 -relief raised", 448 "View: "+file, Wmlib->Hide); 449.P3 45060 event := chan of string; 45161 tk->namechan(t, event, "event"); 452.P3 45362 tk->cmd(t, "frame .im -height " + 454 string im.r.dy() + 455 " -width " + 456 string im.r.dx()); 45763 tk->cmd(t, "bind . <Configure> "+ 458 "{send event resize}"); 45964 tk->cmd(t, "bind . <Map> "+ 460 "{send event resize}"); 46165 tk->cmd(t, "pack .im -side bottom"+ 462 " -fill both -expand 1"); 46366 tk->cmd(t, "update"); 464.P3 46567 t.image.draw(posn(t), im, ctxt.display.ones, im.r.min); 46668 for(;;) alt{ 46769 menu := <-menubut => 46870 if(menu == "exit") 46971 return; 47072 wmlib->titlectl(t, menu); 47173 <-event => 47274 t.image.draw(posn(t), im, 473 ctxt.display.ones, im.r.min); 47475 } 47576 } 476.P3 47777 posn(t: ref Tk->Toplevel): Rect 47878 { 47979 minx := int tk->cmd(t, 480 ".im cget -actx"); 48180 miny := int tk->cmd(t, 482 ".im cget -acty"); 48381 maxx := minx + int tk->cmd(t, 484 ".im cget -actwidth"); 48582 maxy := miny + int tk->cmd(t, 486 ".im cget -actheight"); 487.P3 48883 return ((minx, miny), (maxx, maxy)); 48984 } 490.P3 49185 filetype(file: string): RImagefile 49286 { 49387 if(len file>4 494 && file[len file-4:]==".gif") 49588 r := load RImagefile 496 RImagefile->READGIFPATH; 49789 if(len file>4 498 && file[len file-4:]==".jpg") 49990 r = load RImagefile 500 RImagefile->READJPGPATH; 50191 return r; 50292 } 503.P2 504.SH 505Modules 506.LP 507Limbo programs are composed of modules that are loaded and linked at run-time. Each Limbo source file is the implementation of a single module; here line 1 states this file implements a module called 508.CW "View" , 509whose declaration appears in the 510.CW "module" 511declaration on lines 15-18. The declaration states that the module has one publicly visible element, the function 512.CW "init" . 513Other functions and variables defined in the file will be compiled into the module but only accessible internally. 514.LP 515The function 516.CW "init" 517has a type signature (argument and return types) that makes it callable from the Inferno shell, a convention not made explicit here. The type of 518.CW "init" 519allows 520.CW "View" 521to be invoked by typing, for example, 522.P1 523view *.jpg 524.P2 525at the Inferno command prompt to view all the JPEG files in a directory. This interface is all that is required for the module to be callable from the shell; all programs are constructed from modules, and some modules are directly callable by the shell because of their type. In fact the shell invokes 526.CW "View" 527by loading it and calling 528.CW "init" , 529not for example through the services of a system 530.CW "exec" 531function as in a traditional operating system. 532.LP 533Not all modules, of course, implement shell commands; modules are also used to construct libraries, services, and other program components. The module 534.CW "View" 535uses the services of other modules for I/O, graphics, file format conversion, and string processing. These modules are identified on lines 2-14. Each module's interface is stored in a public `include file' that holds a definition of a module much like lines 15-18 of the 536.CW "View" 537program. For example, here is an excerpt from the include file 538.CW "sys.m" : 539.P1 540Sys: module 541{ 542 PATH: con "$Sys"; 543 544 FD: adt # File descriptor 545 { 546 fd: int; 547 }; 548 549 OREAD: con 0; 550 OWRITE: con 1; 551 ORDWR: con 2; 552 553 open: fn(s: string, mode: int): ref FD; 554 print: fn(s: string, *): int; 555 read: fn(fd: ref FD, buf: array of byte, n: int): int; 556 write: fn(fd: ref FD, buf: array of byte, n: int): int; 557}; 558.P2 559This defines a module type, called 560.CW "Sys" , 561that has functions with familiar names like 562.CW "open" 563and 564.CW "print" , 565constants like 566.CW "OREAD" 567to specify the mode for opening a file, an aggregate type 568.CW "adt" ) ( 569called 570.CW "FD" , 571returned by 572.CW "open" , 573and a constant string called 574.CW "PATH" . 575.LP 576After including the definition of each module, 577.CW "View" 578declares variables to access the module. Line 3, for example, declares the variable 579.CW "sys" 580to have type 581.CW "Sys" ; 582it will be used to hold a reference to the implementation of the module. Line 6 imports a number of types from the 583.CW "draw" 584(graphics) module to simplify their use; this line states that the implementation of these types is by default to be that provided by the module referenced by the variable 585.CW "draw" . 586Without such an 587.CW "import" 588statement, calls to methods of these types would require explicit mention of the module providing the implementation. 589.LP 590Unlike most module languages, which resolve unbound references to modules automatically, Limbo requires explicit `loading' of module implementations. 591Although this requires more bookkeeping, it allows a program to have fine control over the loading (and unloading) of modules, an important property in the small-memory systems in which Inferno is intended to run. 592Also, it allows easy garbage collection of unused modules and allows multiple implementations to serve a single interface, a style of programming we will exploit in 593.CW "View" . 594.LP 595Declaring a module variable such as 596.CW "sys" 597is not sufficient to access a module; an implementation must also be loaded and bound to the variable. Lines 21-25 load the implementations of the standard modules used by 598.CW "View" . 599The 600.CW "load" 601operator, for example 602.P1 603sys = load Sys Sys->PATH; 604.P2 605takes a type 606.CW "Sys" ), ( 607the file name of the implementation 608.CW "Sys->PATH" ), ( 609and loads it into memory. If the implementation matches the specified type, a reference to the implementation is returned and stored in the variable 610.CW "sys" ). ( 611If not, the constant 612.CW "nil" 613will be returned to indicate an error. Conventionally, the 614.CW "PATH" 615constant defined by a module names the default implementation. Because 616.CW "Sys" 617is a built-in module provided by the system, it has a special form of name; other modules' 618.CW "PATH" 619variables name files containing actual code. For example, 620.CW "Wmlib->PATH" 621is \f5"/dis/lib/wmlib.dis"\fP. 622Note, though, that the name of the implementation of the module in a 623.CW "load" 624statement can be any string. 625.LP 626Line 26 initializes the 627.CW "wmlib" 628module by invoking its 629.CW "init" 630function (unrelated to the 631.CW "init" 632of 633.CW "View" ). 634Note the use of the 635.CW "->" 636operator to access the member function of the module. The next two lines load modules, but add a new wrinkle: they also 637.I "declare" 638and 639.I "initialize" 640the module variables storing the reference. Limbo declarations have the general form 641.P1 642\fIvar\fP: \fItype\fP = \fIvalue\fP; 643.P2 644If the type is missing, it is taken to be the type of the value, so for example, 645.P1 646bufio := load Bufio Bufio->PATH; 647.P2 648on line 28 declares a variable of type 649.CW "Bufio" 650and initializes it to the result of the 651.CW "load" 652expression. 653.SH 654The main loop 655.LP 656The 657.CW "init" 658function takes two parameters, a graphics context, 659.CW "ctxt" , 660for the program and a list of command-line argument strings, 661.CW "argv" . 662.CW "Argv" 663is a 664.CW "list" 665.CW "of" 666.CW "string" ; 667strings are a built-in type in Limbo and lists are a built-in form of constructor. Lists have several operations defined: 668.CW "hd" 669(head) returns the first element in the list, 670.CW "tl" 671(tail) the remainder after the head, and 672.CW "len" 673(length) the number of elements in the list. 674.LP 675Line 29 throws away the first element of 676.CW "argv" , 677which is conventionally the name of the program being invoked by the shell, and lines 30-31 ignore a geometry argument passed by the window system. The loop from lines 33 to 53 processes each file named in the remaining arguments; when 678.CW "argv" 679is a 680.CW "nil" 681list, the loop is complete. Line 34 picks off the next file name and line 35 updates the list. 682.LP 683Line 36 is the first method call we have seen: 684.P1 685im := ctxt.display.open(file); 686.P2 687The parameter 688.CW "ctxt" 689is an 690.CW "adt" 691that contains all the relevant information for the program to access its graphics environment. One of its elements, called 692.CW "display" , 693represents the connection to the frame buffer on which the program may write. The 694.CW "adt" 695.CW "display" 696(whose type is imported on line 6) has a member function 697.CW "open" 698that reads a named image file into the memory associated with the frame buffer, returning a reference to the new image. (In X[20] terminology, 699.CW "display" 700represents a connection to the server and 701.CW "open" 702reads a pixmap from a file and instantiates it on that server.) 703.LP 704The 705.CW "display.open" 706method succeeds only if the file exists and is in the standard Inferno image format. If it fails, it will return 707.CW "nil" 708and lines 38-50 will attempt to convert the file into the right form. 709.SH 710Decoding the file 711.LP 712Line 38 calls 713.CW "filetype" 714to determine what format the file has. The simple version here, on lines 85-92, just looks at the file suffix to determine the type. A realistic implementation would work harder, but even this version illustrates the utility of program-controlled loading of modules. 715.LP 716The decoding interface for an image file format is specified by the module type 717.CW "RImagefile" . 718However, unlike the other modules we have looked at, 719.CW "RImagefile" 720has a number of implementations. If the file is a GIF file, 721.CW "filetype" 722returns the implementation of 723.CW "RImagefile" 724that decodes GIFs; if it is a JPEG file, 725.CW "filetype" 726returns an implementation that decodes JPEGs. In either case, the 727.CW "read" 728method has the same interface. Since reference variables like 729.CW "r" 730are implicitly initialized to 731.CW "nil" , 732that is what 733.CW "filetype" 734will return if it does not recognize the image format. 735.LP 736Thus, 737.CW "filetype" 738accepts a file name and returns the implementation of a module to decode it. 739.LP 740A couple of other points about 741.CW "filetype" . 742First, the expression 743.CW "file[len file-4:]" 744is a 745.I "slice" 746of the string 747.CW "file" ; 748it creates a string holding the last four characters of the file name. The colon separates the starting and ending indices of the slice; the missing second index defaults to the end of the string. As with lists, 749.CW "len" 750returns the number of characters (not bytes; Limbo uses Unicode[21] throughout) in the string. 751.LP 752Second, and more important, this version of 753.CW "filetype" 754loads the decoder module anew every time it is called, which is clearly inefficient. It's easy to do better, though: just store the module in a global, as in this fragment: 755.P1 756readjpg: RImagefile; 757filetype(...)... 758{ 759 if(isjpg()){ 760 if(readjpg == nil) 761 readjpg = load RImagefile 762 RImagefile->READJPGPATH; 763 return readjpg; 764 } 765} 766.P2 767The program can form its own policies on loading and unloading modules based on time/space or other tradeoffs; the system does not impose its own. 768.LP 769Returning to the main loop, after the type of the file has been discovered, line 41 opens the file for I/O using the buffered I/O package. Line 44 calls the 770.CW "init" 771function of the decoder module, passing it the instance of the buffered I/O module being used (if we were caching decoder modules, this call to 772.CW "init" 773would be done only when the decoder is first loaded.) Finally, the Limbo-characteristic line 45 reads in the file: 774.P1 775(ri, err) := idec->read(fd); 776.P2 777The 778.CW "read" 779method of the decoder does the hard job of cracking the image format, which is beyond the scope of this paper. The result is a 780.I "tuple" : 781a pair of values. The first element of the pair is the image, while the second is an error string. If all goes well, the 782.CW "err" 783will be 784.CW "nil" ; 785if there is a problem, however, 786.CW "err" 787may be printed by the application to report what went wrong. The interesting property of this style of error reporting, common to Limbo programs, is that an error can be returned even if the decoding was successful (that is, even if 788.CW "ri" 789is non- 790.CW "nil" ). 791For example, the error may be recoverable, in which case it is worth returning the result but also worth reporting that an error did occur, leaving the application to decide whether to display the error or ignore it. 792.CW "View" "\ " ( 793ignores it, for brevity.) 794.LP 795In a similar manner, line 48 remaps the colors from the incoming colormap associated with the file to the standard Inferno color map. The result is an image ready to be displayed. 796.SH 797Creating a process 798.LP 799By line 52 in the main loop, we have an image ready in the variable 800.CW "im" 801and use the Limbo primitive 802.CW "spawn" 803to create a new process to display that image on the screen. 804.CW "Spawn" 805operates on a function call, creating a new process to execute that function. The process doing the spawning, here the main loop, continues immediately, while the new process begins execution in the specified function with the specified parameters. Thus line 52 begins a new process in the function 806.CW "view" 807with arguments the graphics context, the image to display, the file name, and a unique identification number used in placing the windows. 808.LP 809The new process shares with the calling process all variables except the stack. Shared memory can therefore be used to communicate between them; for synchronization, a more sophisticated mechanism is needed, a subject we will cover in the section on communications. 810.SH 811Starting Tk 812.LP 813The function 814.CW "view" 815uses the Inferno Tk graphics toolkit (a re-implementation for Limbo of Ousterhout's Tcl/Tk toolkit [18]) to place the image on the screen in a new window. Line 57 computes the position of the corner of the window, using the viewer number to stagger the positions of successive windows. The 816.CW "string" 817keyword is a conversion; in this example the conversion does an automatic translation from an integer expression into a decimal representation of the number. Thus 818.CW "corner" 819is a string variable, a form more useful in the calls to the Tk library. 820.LP 821The Inferno Tk implementation uses Limbo as its controlling language. 822Rather than building a rich procedural interface, the interface passes strings to a generic Tk command processor, which returns strings as results. 823This is similar to the use Tk within Tcl, but with most of the control flow, arithmetic, and so on written in Limbo. 824.LP 825A good introduction to the style is the function 826.CW "posn" 827on lines 77-84. The calls to 828.CW "tk->cmd" 829evaluate the textual command in the context defined by the 830.CW "Tk->Toplevel" 831variable 832.CW "t" 833(created on line 57 and passed to 834.CW "posn" ); 835the result is a decimal integer, converted to binary by the explicit 836.CW "int" 837conversion. On line 83, all the coordinates of the rectangle are known, and the function returns a nested tuple defining the rectangular position of the 838.CW ".im" 839component of the Toplevel. This tuple is automatically promoted to the 840.CW "Rect" 841type by the return statement. 842.LP 843Back in function 844.CW "view" , 845line 58 uses a function from the higher-level 846.CW "String" 847module to strip off the basename of the file name, for use in the banner of the window. Note that one component of the tuple is nil; the value of this component is discarded. 848Line 58 calls the window manager function 849.CW "wmlib->titlebar" 850to establish a title bar on the window 851The arguments are 852.CW "ctxt.screen" , 853a data structure representing the window stack on the frame buffer, 854a string specifying the size and properties of the new window, the window's 855label, and the set of control buttons required. 856The 857.CW "+" 858operator on strings performs concatenation. 859The window is labelled \f5"View"\fP 860and the file basename, with a control button to hide the window. 861Titlebars always include a control button to dismiss the window. 862(The size and properties argument is more commonly nil or the empty string, 863leaving the choice of position and style to the window manager.) 864The first value 865in the tuple returned by 866.CW "wmlib->titlebar" 867is a reference to a `top-level' widget\-a window\-upon which the program will assemble its display. 868.SH 869Communications 870.LP 871The second value in the tuple 872returned from 873.CW "wmlib->titlebar" 874is a built-in Limbo type called a channel 875.CW "chan" "" ( 876is the keyword). A channel is a communications mechanism in the manner of Hoare's CSP[15]. Two processes that wish to communicate do so using a shared channel; data sent on the channel by one process may be received by another process. The communication is 877.I "synchronous" : 878both processes must be ready to communicate before the data changes hands, and if one is not ready the other blocks until it is. Channels are a feature of the Limbo language: they have a declared type 879.CW "chan" "" ( 880.CW "of" 881.CW "int" , 882.CW "chan" 883.CW "of" 884.CW "list" 885.CW "of" 886.CW "string" , 887etc.) and only data of the correct type may be sent. There is no restriction on what may be sent; one may even send a channel on a channel. Channels therefore serve both to communicate and to synchronize. 888.LP 889Channels are used throughout Inferno to provide interfaces to system functions. The threading and communications primitives in Limbo are not designed to implement efficient multicomputer algorithms, but rather to provide an elegant way to build active interfaces to devices and other programs. 890.LP 891One example is the 892.CW "menubut" 893channel returned by 894.CW "wmlib->titlebar" , 895a channel of textual commands sent by the window manager. The expression on line 69, 896.P1 897menu := <-menubut 898.P2 899receives the next message on the channel and assigns it to the variable menu. The communications operator, 900.CW "<-" , 901receives a datum when prefixed to channel and transmits a datum when combined with an assignment operator (e.g. 902.CW "channel<-=2" ). 903This use of menubut appears inside an 904.CW "alt" 905(alternation) statement, a construct we'll discuss later. 906.LP 907Lines 60 and 61 create and register a new channel, 908.CW "event" , 909to be used by the Tk module to report user interface events. Lines 62-66 use simple Tk operations to make the window in which the image may be drawn. Lines 63 and 64 bind events within this window to messages to be sent on the channel 910.CW "event" . 911For example, line 63 defines that when the configuration of the window is changed, presumably by actions of the window manager, the string 912\f5"resize"\fP 913is to be transmitted on 914.CW "event" 915for interpretation by the application. This translation of events into messages on explicit channels is fundamental to the Limbo style of programming. 916.SH 917Displaying the image 918.LP 919The payoff occurs on line 67, which steps outside the Tk model to draw the image 920.CW "im" 921directly on the window: 922.P1 923t.image.draw(posn(t), im, ctxt.display.ones, im.r.min); 924.P2 925.CW "Posn" 926calculates where on the screen the image is to go. The 927.CW "draw" 928method is the fundamental graphics operation in Inferno, whose design is outside our scope here. In this statement, it just copies the pixels from 929.CW "im" 930to the window's own image, 931.CW "t.image" ; 932the argument 933.CW "ctxt.display.ones" 934is a mask that selects every pixel. 935.SH 936Multi-way communications 937.LP 938Once the image is on the screen, 939.CW "view" 940waits for any changes in the status of the window. Two things may happen: either the buttons on the title bar may be used, in which case a message will appear on 941.CW "menubut" , 942or a configuration or mapping operation will apply to the window, in which case a message will appear on 943.CW "event" . 944.LP 945The Limbo 946.CW "alt" 947statement provides control when more than one communication may proceed. Analogous to a 948.CW "case" 949statement, the 950.CW "alt" 951evaluates a set of expressions and executes the statements associated with the correct expression. Unlike a 952.CW "case" , 953though, the expressions in an 954.CW "alt" 955must each be a communication, and the 956.CW "alt" 957will execute the statements associated with the communication that can first proceed. If none can proceed, the 958.CW "alt" 959waits until one can; if more than one can proceed, it chooses one randomly. 960.LP 961Thus the loop on lines 68-75 processes messages received by the two classes of actions. When the window is moved or resized, line 73 will receive a \f5"resize"\fP 962message due to the bindings on lines 63 and 64. The message is discarded but the action of receiving it triggers the repainting of the newly placed window on line 74. Similarly, messages triggered by buttons on the title bar send a message on 963.CW "menubut" , 964and the value of that is examined to see if it is 965\f5"exit"\fP, 966which should be handled locally, or anything else, which can be passed on to the underlying library. 967.SH 968Cleanup 969.LP 970If the exit button is pushed, line 71 will return from 971.CW "view" . 972Since 973.CW "view" 974was the top-level function in this process, the process will exit, freeing all its resources. All memory, open file descriptors, windows, and other resources held by the process will be garbage collected when the return executes. 975.LP 976The Limbo garbage collector [16] uses a hybrid scheme that combines reference counting to reclaim memory the instant its last reference disappears with a real-time sweeping algorithm that runs as an idle-time process to reclaim unreferenced circular structures. 977The instant-free property means that system resources like file descriptors and windows can be tied to the collector for recovery as soon as they become unused; there is no pause until a sweeper discovers it. 978This property allows Inferno to run in smaller memory arenas than are required for efficient mark-and-sweep algorithms, as well as providing an extra level of programmer convenience. 979.SH 980Summary 981.LP 982Inferno supplies a rich environment for constructing distributed applications that are portable\-in fact identical\-even when running on widely divergent underlying hardware. Its unique advantage over other solutions is that it encompasses not only a virtual machine, but also a complete virtual operating system including network facilities. 983.SH 984Acknowledgment 985.LP 986The cryptographic elements of Inferno owe much 987to the cryptographic library of Lacy et al. [22]. 988.SH 989References 990.LP 991.nr PS -1 992.nr VS -1 993.IP 1. 994R. Pike, D. Presotto, S. Dorward, B. Flandrena, K. Thompson, H. Trickey, and P. Winterbottom. ``Plan 9 from Bell Labs'', 995.I "J. Computing Systems" 9968:3, Summer 1995, pp. 221-254. 997.IP 2. 998S. Dorward, R. Pike, and P. Winterbottom. ``Programming in Limbo'', 999.I "IEEE Compcon 97 Proceedings" , 10001997. 1001.IP 3. 1002J. K. Ousterhout. 1003.I "Tcl and the Tk Toolkit" , 1004Addison-Wesley, 1994. 1005.IP 4. 1006T. Elgamal, ``A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms'', 1007.I "Advances in Cryptography: Proceedings of CRYPTO 84, " 1008Springer Verlag, 1985, pp. 10-18 1009.IP 5. 1010B. Schneier, ``Applied Cryptography'', Wiley, 1996, p. 516 1011.IP 6. 1012D. Stinson, ``Cryptography, Theory and Practice'', 1013.I "CRC Press" , 10141996, p. 271 1015.IP 7. 1016K. Hickman and T. Elgamal, ``The SSL Protocol (V3.0)'', 1017.I "IETF Internet-draft" 1018.IP 8. 1019S. M. Bellovin and M. Merritt, ``Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attack'', Proceedings of the 1992 IEEE Computer Society Conference on Research in Security and Privacy, 1992, pp. 72-84 1020.IP 9. 1021M. Blaze, J. Feigenbaum, J. Lacy, ``Decentralized Trust Management'', 1022.I "Proceedings 1996 IEEE Symposium on Security and Privacy" , 1023May 1996 1024.IP 10. 1025R. Rivest and B. Lampson, ``SDSI - A Simple Distributed Security Architecture'', unpublished, 1026.I "http://theory.lcs.mit.edu/~rivest/sdsi10.ps" 1027.IP 11. 1028.I "American National Standard for Information Systems Programming Language C" , 1029American National Standards Institute, X3.159-1989. 1030.IP 12. 1031.I "GIF Graphics Interchange Format: A standard defining a mechanism for the storage and transmission of bitmap-based graphics information" , 1032CompuServe Incorporated, Columbus, OH, 1987. 1033.IP 13. 1034.I "GIF Graphics Interchange Format: Version 89a" , 1035CompuServe Incorporated, Columbus, OH, 1990. 1036.IP 14. 1037S. Dorward et al., ``Inferno'', 1038.I "IEEE Compcon 97 Proceedings" , 10391997. 1040.IP 15. 1041C. A. R. Hoare, ``Communicating Sequential Processes''. 1042.I "Comm. ACM" 104321:8, pp. 666-677, 1978. 1044.IP 16. 1045L. Huelsbergen, and P. Winterbottom, ``Very Concurrent Mark & Sweep Garbage Collection without Fine-Grain Synchronization'', Submitted 1046.I "International Conference of Functional Programming" , 1047Amsterdam, 1997. 1048.IP 17. 1049K. Jensen, and N. Wirth, 1050.I "PascalUser Manual and Report" . 1051Springer-Verlag, 1974. 1052.IP 18. 1053John K. Ousterhout, 1054.I "Tcl and the Tk Toolkit" , 1055Addison-Wesley, 1994. 1056.IP 19. 1057W. B. Pennebaker. and J. L. Mitchell, 1058.I "JPEG Still Image Data Compression" , 1059Van Nostrand Reinhold, New York, 1992. 1060.IP 20. 1061R. W. Scheifler, J. Gettys, and R. Newman, 1062.I "X Window System" , 1063Digital Press, 1988. 1064.IP 21. 1065The Unicode Consortium, 1066.I "The Unicode Standard, Version 2.0, " 1067Addison Wesley, 1996. 1068.IP 22. 1069J. B. Lacy, D. P. Mitchell, and W. M. Schell, ``CryptoLib: Cryptography in Software,'' 1070.I "UNIX Security Symposium IV Proceedings" , 1071USENIX Association, 1993 pp. 1-17. 1072.nr PS +1 1073.nr VS +1 1074