Legion 1.2
Developer Manual

Core Objects
13.0 About the Legion core object model

The power of the Legion core object model comes from the important role of the Legion classes: much of what is usually considered system-level responsibility such as creating and locating their instances and subclasses and for selecting appropriate security and object placement policies is delegated to class objects. The core Legion objects provide mechanisms for the user-level classes to implement appropriate policies and algorithms. Assuming that core object operations are correctly defined (that they are the right set of primitive operations to enable a wide enough range of policies to be implemented) this philosophy effectively eliminates the danger of imposing inappropriate policy decisions and opens up a much wider range of possibilities for the applications developer.

In this model each Legion object belongs to a class and each class is itself a Legion object. All Legion objects export a common set of object-mandatory member functions, such as deactivate(), getInterface(), and ping(). Class objects also export a set of class-mandatory member functions, such as createInstance(), activateInstance(), and deactivateInstance().

Legion class interfaces can be described in an Interface Description Language (IDL). Initially, two different IDLs will be supported by Legion: the CORBA IDL [See Digital Equipment Corporation], and the Mentat Programming Language (MPL) [See The Mentat Research Group]. Method calls are non-blocking and may be accepted in any order by the called object. Each method has a signature that describes the parameters and return value, if any, of the method. The complete set of method signatures for an object fully describes that object's interface, which is determined by its class.

The Legion core objects cooperate to create, locate, manage, and remove objects from the Legion system. The core object model reflects the underlying philosophy and objectives of the Legion project. In particular, the object model facilitates a flexible and extensible implementation, provides a single global name space, grants site autonomy to participating organizations, and scales to millions of sites and trillions of objects. Its framework also supports mechanisms for high performance, security, fault tolerance, and commerce.

Legion specifies the functionality but not the implementation of its core objects. The Legion project provides implementations of the objects that comprise the core but users are not compelled to use them but are instead encouraged to select or construct objects that will implement specific necessary mechanisms and policies.

To facilitate the development of multi-site applications a single global name space unites the objects in the Legion system. Legion provides site autonomy by distributing control of Legion resources among an extensible set of core user-level Legion objects. This includes decisions about which Legion objects have access to each resource and to what degree. Users are free to build or alter the objects that handle these decisions, so that each site can maintain autonomous control over its own resources.

13.1 About core objects

Legion defines the interface and functionality of several core class objects, including LegionClass, LegionHost, LegionVault, and LegionBindingAgent. LegionClass provides the full set of class-mandatory member functions. All Legion classes are eventually derived from LegionClass, and they inherit all of the member functions defined in LegionClass. Classes may alter the functionality of object- or class-mandatory member functions by overloading them, by redefining them, or by explicitly "re-inheriting" their implementations from class objects other than LegionClass.

LegionHost, LegionVault, and LegionBindingAgent are base classes for Legion's core class types (host objects, vault objects, and binding agents). The core classes set the minimal interface that the core objects should export. Every core object is an instance of some class that is eventually derived from one of the class objects above. For example, Figure 30 shows how UnixHost and SPMDHost, two different Legion classes, derive from class LegionHost.

More specific host classes derive from each of these. A Sun workstation would run an instance of class UnixHost, whereas a Silicon Graphics Power Challenge would run an instance of UnixSMMP, a class derived from UnixHost. Similar class hierarchies will develop for vault objects and binding agents.

13.2 Classes and Metaclasses

As mentioned above, every Legion object is defined and managed by its class object. Class objects are empowered with system-level responsibility to create new instances, schedule them for execution, activate and deactivate them, and provide bindings for clients who wish to communicate with them. In this sense classes are managers and policy makers: Legion allows users to define and build their own class objects so that Legion programmers can determine and even change the system-level mechanisms that support their objects. These two important features--instance management and straightforward class object customization--provide considerable flexibility in determining how an application behaves and further supports the Legion philosophy of enabling flexibility in the kind and level of functionality

Legion classes export the class-mandatory interface, a simplified subset of which is depicted in Figure 31.

The createInstance() function causes a new instance of the class to be created and returns this new instance's LOID. The createMultiple- Instances() function can be used to create several instances of the class at once. There are actually several different flavors of createInstance() and createMultipleInstances(), allowing the caller varying levels of control over the creation and placement processes. For example, the caller can specify the host object on which the new instance(s) should be created, a list of acceptable hosts from which to choose, or even a list of characteristics of acceptable hosts (processor speeds, architectures, etc.). The same is true of the activateInstance() function. The general object placement model is that the class selects the host and vault objects when placing its instances, but includes the object placement parameters in the activation and creation functions so as to give callers a way to help the class make intelligent decisions, should the caller so choose. The deactivateInstance() function allows callers to make an active object inert, and deleteInstance() allows its caller to remove an instance from Legion.1 The addImplementation() and removeImplementation() functions allow external objects (typically Legion-targeted compilers or Legion objects that manage the compilation process) to configure classes with implementation objects. The getBinding() functions support the binding mechanism. Figure 31 does not show several other functions that allow class object clients to retrieve information about the location and characteristics of a particular class's instances, such as the instances' interface, host (if any) on which they're currently running, current state (active or inert), etc.

Although the core interface to classes is set, the implementation behind that interface can vary, depending on which behavior the class wishes to exhibit. This allows considerable policy and mechanical flexibility. For example, a class can match its scheduling and object placement policies to its instances' characteristics. If an instance runs much faster on a particular architecture, the class can factor in that affinity when selecting a host to run its instances. If certain instances communicate frequently with one another when they are created in relatively rapid succession (thereby possibly indicating that they are all part of the same instantiation of an application), the class can attempt to schedule these objects "close" to one another, perhaps on hosts with fast communications links or possibly even as multiple threads within the same process.

Class objects are in the best position to take advantage of their instances' special characteristics, since class objects can be provided or selected by the programmer providing the implementation of that class object's instances. This does not mean, however, that all programmers must build a new specialized class object for each type of Legion object that they build, thereby incurring the burden of metasystem-level programming: we expect that a vast majority of programmers will be adequately served by existing class object types.

The mechanism for taking advantage of an existing class object type is simple. Legion uses the notion of metaclass objects, class objects whose instances are themselves class objects. Just as a normal class object maintains implementation objects for its instances, a metaclass object maintains implementation objects for its class objects. A metaclass object's implementation objects are built to export the class-mandatory interface, and to exhibit a particular functionality behind that interface. To use a metaclass, the programmer calls createInstance() on the appropriate metaclass object and configures the resulting class object, via addImplementation(), with implementation objects for the application in question. The new class object can then support the creation, migration, activation, and location of these application objects in the manner defined by its metaclass object.

One example of a class object taking advantage of knowledge about its instances' implementations is a stateless Mentat class. In MPL, the keyword stateless can be used to describe a class definition, as depicted in Figure 32.

Here, the programmer has indicated that the instances of class Example do not maintain state between their member function invocations--that the instances are pure functional units. Therefore, from the client's point of view invoking a function on one instance of a stateless class is functionally equivalent to invoking the same function on any other instance of that class.2 In particular, two consecutive invocations from the same client need not be made on the same object.

The class object that supports stateless objects can take advantage of this fact when responding to class-mandatory member function invocations. For example, in response to a createInstance() call the class object need not actually create a new instance but can instead simply return the binding for an instance that already exists. Conversely, if the load on an instance rises above an acceptable threshold, the class can create a new instance and respond to requests to bind to the heavily-loaded instance with a binding for the new instance. The point is that the class object can use its knowledge about the semantics of its instances to optimize its support for them.

13.3 Host Objects

Legion host objects encapsulate processing resources in Legion--a host object may represent a single processor, a multiprocessor, a Sparc, a Cray T90, or even an aggregation of multiple hosts. A host object is a host's representative to Legion: it is responsible for executing objects on the host, reaping objects, and reporting object exceptions. It is also ultimately responsible for deciding which objects can run on the host it represents. Host objects are therefore important points of security policy encapsulation within the system.

Aside from implementing the host-mandatory interface, depicted in Figure 33, host object implementations can be programmed to adapt to different environments and suit different users' needs. Thus host objects that provide interfaces to different resources can be customized to match the resource's requirements: a host object implementation suitable for use on a normal interactive workstation will have process creation mechanisms unlike a host object's on a parallel computer whose nodes are managed by a batch queuing system (e.g. LoadLeveler [See IBM]).

Host object implementations provide a uniform interface to different resource management interfaces, as well as (more importantly) providing a means for users to enforce security and resource management policies for Legion objects. For example, the host object implementation can be customized to allow only a restricted set of users to have access to a resource. User authentication can be performed using any means desired. Host objects can also restrict access based on code characteristics. For example, a host might be configured to accept only object implementations containing proof-carrying code [See Necula] that demonstrates certain desired security properties. A less formally restrictive host might analyze incoming object implementations for certain "restricted" system calls.

We now consider a sample host object implementation (our default current host object) and two possible alternative implementations. The default current host object has a very simple design--it implements a non-restrictive access policy and uses the Unix process management interface (i.e. fork(), exec(), kill()) for starting and stopping objects. While simple to implement, this basic host object design has a number of limiting features that affect both performance and security. It places a high cost on object activation, since each object on the host executes within its own process and new processes are created on demand to contain activating objects. It also executes objects owned by different Legion users under the same Unix user-id (processes executing as the same user-id can send one another arbitrary signals, examine one another's state, and so on). Fortunately, we can transparently address these limitations by providing alternative host object implementations.

One possible implementation to address these performance problems might use threads instead of traditional processes. This design would improve the performance of object activation, and would also reduce the cost of method invocation between objects on the same host by allowing simplified shared address space communication. To support this style of host object, alternate forms of object implementations would need to be made available, particularly, object implementations in the form of dynamically loadable object files (as opposed to normal executable files). This would allow the host to map the needed code for objects into its address space prior to object activation (i.e. thread creation). This need for alternate forms of object implementations fits nicely into our established model for managing multiple object implementations per class as needed to support heterogeneity.

The above host object implementation would appeal to users with high performance requirements, but it shares and exacerbates our existing host object's security limitations. An alternate host object implementation to support better security properties might be based on the use of multiple Unix user-ids to run different users' objects. Our current host object typically runs under a single user-id, and all objects that it starts also run as this user. If we extend the host object implementation to have the ability to start up processes under a set of different user-ids, it could ensure that different Legion users' objects run under different Unix user ids.

This host object implementation can be supported in a number of ways. For example, the host object could be given the limited amount of privilege needed to start processes as different user id's. This could take the form of a "set uid" script without write permissions for the host object so that it would not require full root permissions. Alternate approaches are also possible, such as the use of a set of "sub-host objects"--one running as each user id--that could be used by the "primary" host object for control of low-level processes. In this design, the standard Legion authentication mechanisms could be used to ensure that only the host object is able to use these process-control daemons.

Different versions of this multi-user id host object can map different Legion users to different "anonymous" local user ids (e.g. "legion1," "legion2," etc.), or map Legion users to their associated local Unix user ids. The latter form extends directly to a simple scheme for limiting resource use to approved users--if a Legion user attempting to activate an object does not have a local Unix user-id, the activation request could be denied.

13.4 Vault Objects

Vault objects are responsible for managing other Legion objects' OPRs. Much in the same way that hosts manage active objects' direct access to processors, vaults manage inert objects on persistent storage. A vault has direct access to a storage device (or devices) on which the OPRs it manages are stored. It might manage a portion of a Unix file system or a set of databases. The vault supports the creation of OPRs for new objects, controls access to the OPRs of existing objects that it manages, and supports the migration of OPRs from one storage device to another. The basic vault interface is depicted in Figure 34.

Class objects manage the assignment of vaults to individual objects: when an object is created, its vault is chosen by the object's class. The selected vault creates a new, empty, OPR for the object, and supplies the object with its OPA. Similarly, when an object migrates or reactivated, the selection of a new vault for the object is managed by the object's class.

If an object's class (or an external scheduling agent acting on behalf of that class) decides to move the object to another host, the migration may require moving the OPR to a new vault, whose persistent storage is accessible by objects on the new host. In this case, the class (or scheduling agent) selects a new vault, and the OPR is transferred between the vaults.

The above vault activities are supported by the basic Legion vault abstract-interface depicted in Figure 34. To enable object creation, the vault provides a createOPR() method, which constructs a new empty OPR, associates this OPR with the given LOID, and returns the address of the new OPR for use by the newly created object. To support object activation and deactivation, the vault provides a getOPRAddress() method to determine the location of the OPR associated with any of its managed objects. For use during object migration, vaults support giveOPR() and getOPR() methods, which transfer a linearized (i.e. transmissible) OPR to and from vaults, respectively. The deleteOPR() can be used to terminate a given vault's management of an OPR. The isManaged() method can be used to determine if a vault manages a given object. Finally, markActive() and markInactive() methods are provided so that the vault can be notified when an object is active or inactive, respectively. This knowledge allows the vault to store the OPRs of inactive objects in compressed or encrypted forms for efficiency and security purposes.

An important feature of the vault interface is its use of OPAs to provide access to object persistence representations. When an object wants to access its OPR, it can learn the OPA from its vault. The vault must provide an address that contains enough information embedded in it to find and access the OPR. For example, consider an implementation of vaults and OPRs that is based on the Unix file system. In such an environment, an OPR might be implemented as a Unix directory, and an OPA might contain a Unix path name corresponding to a Unix directory. In this case the OPAs, besides containing the path name needed to locate the OPR, would also need to contain a type indicator that lets the object know that it should access the OPR in the form of a Unix subdirectory. In a sense, the OPA constitutes an agreement between a vault and a managed object about what kind of OPR will be used for the object. With this agreement, the object can directly access its OPR without consulting its vault. Clearly, not all object types or implementations need be compatible with all vaults. Just as class objects restrict the placement of objects and use of implementations to acceptable host objects, they also ensure reasonable placement of objects onto vaults.

The current Legion implementation supports two types of vaults (and hence, two types of OPR implementations): one for use in Unix file systems, and one for use with the SRB archival storage interface. These implementations are quite similar, as both systems support a file and directory interface typical of file systems. The addition of vaults for other file systems (e.g. Windows NT) and other archival file storage systems (e.g. HPSS) is straightforward. Alternative vault implementations can be built on top of database management systems. In this design vaults must manage the association between OPRs and database entries, and the mapping must be encapsulated in a suitable OPA format that can be used by managed objects to bind to their OPRs.

13.5 Implementation Objects and Caches

Implementation objects in Legion hide the storage details of object implementations. These objects can be thought of as the Legion equivalent of executable files in Unix or other traditional operating systems. Given this similarity to files, implementation objects support an interface typical of file objects, as depicted in Figure 35. Read and write operations that assume a client-side file pointer, and a method to determine the size of the implementation data are provided. However, a fundamental difference between file objects and implementation objects is that implementation objects cannot be written to after being read from. After being initialized with a sequence of write() methods an implementation object's contents are constant until the object is deleted. This allows important caching optimizations to be employed by implementation object clients (i.e. host objects).

Legion object implementations typically contain executable object code for a single architecture and operating system platform, but may in general contain any information that would be necessary to instantiate an object on an appropriate type of host object. For example, the implementation might contain Java byte code, a Perl script, or even high-level source code that would require compilation by a host object upon object activation. A complete list of (possibly very different) acceptable implementation objects appropriate for use with a given class is maintained by the class object. When the class calls on a host to perform object activation, it selects an implementation object based on the attributes (see "Object attributes") of the host and the instance in question.

Implementation objects allow classes a large degree of flexibility in customizing the behavior of individual instances. For example, a class might maintain implementations with different time/space trade-offs to run more quickly on hosts with abundant memory, and more slowly on hosts with less memory. To provide users with ability to customize their cost and performance trade-offs, a class might maintain slower, low-cost implementations for use with some instances, and faster, higher-cost implementations for use with other instances created by users willing to pay more.

In our discussion of object activation in "Object Activation," we described how host objects typically employ an external implementation caching object to avoid storage and communication costs. Since the contents of implementation objects do not change, a hosts can safely cache the downloaded contents of an implementation object for later use, saving a potentially significant amount of communication costs. Furthermore, if multiple host objects share access to some common storage device they can share the downloaded contents of implementation objects--that is, if one host downloads an implementation data to shared storage other hosts do not have to download that implementation themselves. Both of these performance enhancements are supported in the current Legion implementation through the use of implementation cache objects.

The interface to the implementation cache object is depicted in Figure 36--a single method is provided to return the path of a local file containing the same data as contained in a named implementation object. In our current Legion implementation, each host object is associated with an implementation cache, and implementation caches can be shared among any number of hosts. Instead of performing implementation downloads, host objects invoke the getImplementation() method on their local implementation cache object, which in turn downloads requested implementation data, caching the results of common requests. Thus the use of implementation caches results in object activation being approximately as inexpensive as running a program located in a file system visible on the host.

Our implementation model makes the invalidation of cached binaries a trivial problem. Since class objects specify the LOID of the implementation to use on each activation request, to begin using a new version of an implementation, a class need only replace the old implementation LOID with the new implementation LOID on its list of valid binaries. The new version will be specified with future activation requests, and the old implementation will simply time-out and be discarded from caches. Since the implementation is keyed on its LOID, there is no danger of "invalid" cached binaries being used to execute objects.

13.6 Binding Agents

Section 12.0 introduced the binding and class-of mechanisms and the role of binding agents, which exist in Legion to help client objects map LOIDs to OAs and to find the class of an object, given that object's LOID. The core interface to a binding agent is depicted in Figure 37.
The getBinding(LOID) function returns a binding for a specified LOID, and getClassBinding(LOID) returns a binding for the class of a specified LOID; both are intended to be invoked directly by a client object that is in search of a binding. The getBinding(Binding) and getClassBinding(Binding) support the rebinding mechanism (section 12.4), allowing a client to pass a stale binding, and to suggest that the binding agent return a different binding in response. The addBinding(Binding) and removeBinding(LOID) functions allow a binding agent to act as a database of bindings under the control of external objects. A class can use removeBinding(LOID) to remove an instance's binding when that instance becomes inert or gets deleted, and can call addBinding(Binding) upon creation, activation, or migration of an instance. In this way, a class object can help a binding agent better reduce the number of binding requests it makes to the class object.

Binding agents are not technically necessary for the correct execution of the binding mechanism; clients can directly contact class objects and LegionClass's class map to obtain bindings for objects and classes with which they wish to communicate. However, in a system that consists of millions of potentially migratory objects--as we envision Legion becoming--binding is a necessary and common operation. Binding agents exist to help make the binding mechanism scalable. For instance, in the example of section 12.2, the binding agent runs a simple algorithm in response to the getBinding(LOID) call--it checks its local cache and (if necessary) it contacts the appropriate class object to obtain the binding. Even this simple strategy allows clients to benefit from the execution of the binding mechanism by other clients that share the same binding agent, thereby reducing the total amount of binding traffic in the Legion system.

A binding agent can implement several different strategies to improve its ability to provide bindings for its clients. For example, a binding agent might attempt to ensure that the bindings in its cache don't become stale, by either periodically "pinging"3 the objects named in its binding cache or contacting their classes to make sure they're still located at the same OA. Binding agents may also choose to get up-to-date values for bindings whose time-out field indicates that they are about to expire.

In addition to these strategies in which binding agents act essentially autonomously, many binding agents can be configured to cooperate with one another to serve their clients. For instance, binding agents could be organized hierarchically, as DNS name servers are, or could emulate a software combining tree [See Yew et al], thereby sharing the responsibility for providing bindings and improving the mechanism for scaling to the millions of objects the system will need to support.

The above strategies attempt to improve the response time of binding requests, but they default to the full binding mechanism of contacting the appropriate class object if a binding cannot be otherwise obtained. Other binding agents may slightly change the semantics of the binding agent member functions in an attempt to optimize on different performance metrics. For instance, they may try to decrease the variance in the response times to binding requests. This could be accomplished by responding to a getBinding() call with a simple check the binding cache, avoiding the outcall to classes, even if the binding is not in the cache. To better respond to future requests, the binding agent could contact the class during the binding agent's idle time to get the binding, rather than while the client waits. Unlike the example of section 12.2, a client of this kind of binding agent should not assume that a binding does not exist just because the binding agent doesn't return it; the client may be able to expect more timely responses to its requests.

13.7 Context Objects and Context Spaces

As described in "More about the LOID," Legion objects are identified by their LOIDs. A LOID contains a set of fields including those that identify the class of the named object, a class-unique instance number for the named object, and a public key for the named object. Given this set of fields, LOIDs can grow quite large. Whereas LOIDs are typically transmitted and manipulated in binary form, a "dotted-hex" textual representation for use by human users is also supported. An example of a typical LOID is depicted in Example 38.

The LOID naming scheme is central to a number of Legion design features, but as Figure 38 clearly demonstrates, LOIDs are by no means convenient for human users. To address the basic need for a convenient object naming mechanism, and to provide a tool for organizing information in Legion, we define the interface to a user-level naming service called context spaces.

Context spaces consist of directed graphs of context objects that name and organize information. A context object provides an interface for managing a list of mappings between user-defined string names and LOIDs, as depicted in Figure 39. Operations are provided to insert a < name, LOID> tuple, to remove a string name, and to find the LOID associated with a given user-level string name. Also, a method is provided to return a list of < name, LOID> pairs, elements of which match a specified regular expression. At most one tuple containing any string name may be contained within a context, although any number of different string names may map to the same LOID.

In isolation, a context object may be used to provide a simple, convenient user-level naming service for a user's objects. However, the names inserted into a context can map to other context objects' LOIDs, providing a natural mechanism for constructing a directory service. Connected graphs of context objects are a basic mechanism for organizing information in Legion, and are referred to as context spaces. Every Legion object contains the LOID of a current working context and a root context,4 and library routines are provided for traversing context space to map context paths to LOIDs.

On the surface, context space appears to provide a basic directory service. However, much of the importance of context space in Legion is derived from the fact that any kind of object can be named in context space--contexts are not limited to listing names of other contexts and files. Therefore, context space provides a convenient way of organizing information about any of the objects that are available in a Legion system. For example, Fgiure 40 depicts a simple portion of a context space used to organize information about host objects. One view of context space provides hints about how to find hosts of given types, whereas a different view provides information about resource ownership. Similar organizational schemes are equally useful for objects of other types.

13.8 Core object replacement

For information on replacing core objects, please contact the Legion Research Group.

1.We should note here that an object can disallow any member function invocation requests, typically based on the identity of the caller. This is especially important to the system-level functions implemented in core objects. Back

2. Of course, a function may return a different result if it queries its environment in some way for information. Mentat considers any environment information that may be different across different stateless objects to be state; in other words, if an object does this, it should not be declared as stateless. Back

3. ping() is an object-mandatory member function that returns the LOID of the called object. Back

4. Note that there is no notion of a global "root" context for the system. The root is a user-definable starting point for resolving fully qualified context paths. Back

Back to Developer Manual Table of Contents