David Plainfosse

Marc Shapiro
email: marc.shapiro@inria.fr

A Distributed GC for Object Oriented Systems

We describe a distributed garbage collector proto col targeted for uncooperative distributed object ori ented systems. The protocol has been implemented on distributed Lisp system and a few performance measurements are discussed. Since this implementa tion, we have refined deeply the protocol to address non FIF O channels. A new reference model is pro posed along with the protocol to improve invocation efficiency.

Introduction

Our research is concerned with distributed garbage collection. Distributed garbage collection is a dif ficult problem that has only been addressed par tially. All known algorithms that can collect cycles are either not fault-tolerant [Lang 1992a), can delay garbage reclamation [Hughes 1985a) or are not scal able [Liskov 1986a]. On another hand, incomplete techniques [Dickman 1992, Piquer 1991a] are usually more resilient to messages failures, but these bene fits rely on the assumption that distributed cycles are relatively rare. Thus, designing a distributed garbage collection poses a challenging problem: re claiming all kinds of data structures while achieving fault-tolerance, scalability and efficiency.

Our protocol (hereafter called SGP) [Shapiro 1990] addresses this challenge but fails to collect cycles. It is based on a variant of reference counting and bears some similarities with a number of other proposals [Piquer 199la, Dickman 1992]. One of the requirements in designing this protocol was to achieve a high degree of scalability while kee p ing the overhead as small as possible. The former re quirement led us to reject the use of all kinds of global synchronization. In particular, we paid attention not to rely on any kind of termination protocol, which are notoriously costly and not scalable. Our protocol is cheap and efficient and fulfills the latter requirement since it needs no additional foreground messages or systems calls, and rely on any standard communica tion protocol. In particular, we do not use any expen sive communication mechanism such as broadcast or causal protocol.

In order to evaluate the SGP protocol, we have pro totyped it on a distributed Lisp system, Transpive [Piquer 1991c], implemented at INRIA, and running on a multi-Transputer board hosted by a Sun server [START_REF] Shapiro | Robust distributed references a.nd a.cyclic ga.rba.ge collection[END_REF]]. For the purpose of this evaluation, we replaced Piquer's original Indirect Reference Count garbage collector [Piquer 199la], provided with Tran spive, with a prototype implementation of the SGP protocol. This prototype allowed us to make several performance measurements in terms of CPU cost and message traffic. These results are encouraging but needs to be improved in order to minimize the over head on applications.

The distributed collector interacts strongly with the invocation protocol to track object accessibility. As a consequence, we think that distributed systems should be designed to support such a service. Soul [Shapiro 1991] is the first system to integrate at the design stage, a distributed GC along with uniform lightweight references for either local or remote ob jects [Shapiro 1992b]. Consequently, we have refined our protocol [Shapiro 1992a] which is now tightly cou pled to the reference model of Soul and relies on small number of sub-protocols.

The organization of this paper is the following. Sec tion 2 demonstrates the necessity of providing dis-tributed GC along with a distributed system. Sec tion 3 overviews the SGP protocol. Section 4 describes our prototype implementation and presents some per formance measurements. Finally, Section 5 describes several refinements added to the SGP protocol and the interaction with the reference model.

Motivations

Manual reclamation is an error-prone, time consuming activity.

Moreover, recent studies (Delacour 1991] argue that it also reduces program re-usability. Consequently, the need for garbage col lection in programming languages is now widely ac cepted. Recent proposals to include GC in C++ [START_REF] Edelson | [END_REF][START_REF] Ferreira | Reclaiming storage in an object oriented platform supporting ex tended c++ and objective-c applications[END_REF]] are part of this trend. Designing a collector for such a language poses a chal lenging problem: accessing type information at run time while achieving acceptable overhead. The former problem is further complicated in languages such as C or C++ where pointers may be subverted. Along with these two majors goals, the collector should not be in trusive nor impose restrictions on the programming language.

Similarly to programming languages, we think that distributed systems should provide transparent stor age management. Most of distributed systems pro vide transparent location and invocation mechanisms but leave users to deal with reclamation of garbage objects. In contrast, we think that distribution trans parency necessitates distributed GC.

Moreover, manual reclamation of obje<:ts in dis tributed environment can become intractable. Dis tributed systems provide a distributed computation model where processes run in parallel on different spaces or machines. Processes share objects through remote references, that may cross space boundaries. In such an environment, deciding if an object is garbage or not is definitely a harder task than in cen tralized one. A single object can be remotely refer enced from a number of diff erent spaces. In this case, reclaiming an object requires cooperation between all the spaces which hold references to it. If the heap is shared by many applications written by different pro grammers, if it is accessed in parallel, if it also includes disk storage (as in persistent object systems) and dis tributed access , then manual resource management is simply out of the question.

The problem is further complicated by considering common message failures such as lost, duplicated, or out-of order messages. Each of these failures may invalidate the liveness or safety property of the dis tributed a GC algorithm. For instance, in order to dis card remote objects it is necessary to exchange back ground administrative messages. The loss of such a message may lead to never collect a garbage object. On the other hand, a duplicated message may lead create a dangling remote reference.

3

Overview of the SGP Protocol

The application (mutator) rests upon two separate layers of object management (see Figure 1). The bot tom layer is independent of object semantics, struc ture, or programming language: this is the distributed GC protocol specified in (Shapiro 1990] and described briefly here. The distributed collector propagates ac cessibility information supplied by the upper layer. The upper layer is a language-specific run-time, ex tended to interface with our distributed GC. In the upper layer, one finds storage management (object al location, and local tracing garbage collection) as well as remote invocation functions (i.e. communication stubs).

The two layers share information in the form of lists of incoming and outgoing references. Coopera tion between layers is limited to simple interactions to maintain safe consistency between those lists.

Mutators in different spaces communicate by RPC style invocation, i.e. by messages. An invocation is mediated by communication protocol for marshalling and unmarshalling messages; the communication pro tocol is the interface between the application and the system, encoding typed information into a typeless form. The arguments and results in an invocation con tain any mixt ure of pure data, references, and migrat ing objects. When sending or receiving a message, the communication protocol first writes information about the remote references or objects into the tables that are shared between the two layers.

To provide fault tolerance, extra time and own ership information is piggy-backed onto the existing mutator messages. Occasional control messages are exchanged, in the background, to remove inaccessible sc10ns.

The SG P protocol relies on the existence of a stan dard local tracing garbage collector. The distributed protocol is based on a conservative extension of refer ence counting.

Each space maintains a list of potential incoming and outgoing references, respectively scions and stubs. Both the scions list and the stubs list are conservative estimates. If two dif f spaces possibly refer to a single object of space A, each will be assigned a scion in space A. This differs from reference counting be cause we need an entry per remote space to deal with unreliable communication. This policy renders scion deletion an idempotent operation and permit tolerat ing lost or duplicated message. In the former case any subsequent control mess ages received will allow us to reclaim previously garbage scions. The latter case will have no ef f ect since all garbage scions would have been been previously collected.

Local garbage collection proceeds from the union of the local root and the scions list and removes objects and stubs. Since local GC starts from the union of the local root with the (conservatively estimated) scions, all non-reachable local objects are true garbage. Each local GC removes useless stubs. In turn, stubs are used to clean remote scions, yielding successively bet ter estimates.

When a stub on space A is deleted, the correspond ing scion on space B can be removed. To this ef f ect, a live message is sent from space A to space B. How ever this message can be duplicated or lost.To guard against loss, periodic live messages are sent from A to B containing the list of all existing stubs pointing to B; by comparison space B can deduce scions that are not reachable, and remove them.

One common problem in distributed systems is the message delivery delay. Suppose that one space B sends a message to a space A containing a reference to a given object, say x. At the same time, a delete message is sent from space A to space B to inform that the remote pointer on object z has been discarded. If object x is not locally referenced upon receiving the delete message, it will be remove from the scions list and collected at the next local GC.

To avoid this problem, we keep on each space a vector of highest timestamps and we timestamp en try items. When sending a reference, the stub creates the entry items and store in it the value of the local clock. The same value is used to timestamp the muta tor message. Upon receiving a mutator message, the receiver compares the timestamp value extracted fr om the message with the one fo und in the vector of high est timestamps. This vector contains a space identifier and an associated timestamp for each remote space. A timestamp is increased each time a message is re ceived. If the corresponding entry in the vector does not yet exist the initial value can be taken from the message. live messages carry the current value of the timestamp vector corresponding to the target space. Upon receiving a live message, the timestamp value found in the message is compared to the value in the entry items to detect messages in transit ..

4

Prototype on a Distributed Lisp Sys tem

We have experimented with the SGP protocol on Transpive a distributed Lisp system [Piquer 1991c]. The choice of Transpive allowed us to quickly imple ment the SG P protocol and to learn a few lessons, although the distributed model of Transpive is quite dif f erent from SG P's.

In this section, we compare the measured perfor mance of our prototype with Piquer's Indirect Refer ence Count (hereafter called IRC), in terms of com munication and CPU overhead. Our measurements of two applications (merge sort and matrix multiplica tion) were taken on a Parsytec board composed of four T800 Transputers with one megabyte of memory each, hosted in a Sun. Each application was timed twice in a row; the figures are better the second time because of Transpive's caching policy. The measurements, re peated dozens of times, have shown extremely low variance. Our experiments were able to test resilience to message loss but not to termination, due to lack of a fault-tolerant application. Furthermore, we were not able to quantify how conservative or how scalable our protocol is.

Table 1 shows local execution times. The overhead is due to management of (the Transpive equivalent 5.9

13.5

9.8

1.17

1.05

1.20 1.12 1.12 1.12 A second measurement concerns the number of con trol messages sent and their frequency. Our message sending protocol is different from Piquer's and slows down local processing a little because we group stubs into a single structure, instead of sending a unique stub per control message. We have chosen the former policy because it reduces message traffic. As shown on Table 2, this" buffering" strategy reduces dramatically the number of control messages sent in SGP compared with IRC protocol. Note that the number of control messages sent does vary a little between the two exe cutions. Note also that we obtained the same results whatever the size of list in the merge sort application. It shows that our message sending policy is somewhat independent of the number of objects sent between spaces.

The original SG P model did not take into account the replication of objects. Consequently, we have adapted the SGP protocol into the replication model ofTranspive. This has the result that the collection of scions is more complex and slower than we expected. This increases the conservative aspect of SG P and can be troublesome if memory is heavily in demand. A way to decrease the delay f or collecting scions is to increase the sending frequency of control messages. Consequently, there exists a tradeoff between buffer ing policy and the frequency of control messages.

Moreover, the fine grained sharing support of Tran-spive is definitely an uncooperative environment for distributed GC. In particular, memory consumption is heavy since it requires a huge number of entries in the control data structures. Consequently, it increases the overhead of SGP on application and the frequency of local GC.

The performance results are encouraging but need to be improved , to minimize the overhead on appli cations. The buf f ering policy dramatically reduces the number of control messages. The resilience to message failures has been successfully demonstrated. This result validates our design guideline. However, fault-tolerance to space failures and to duplicate mes sages remains to be investigated. Although, the SGP design relied on very different distributed program ming model from Transpive, the prototype behaves correctly with respect to the safety property. That is, it does not reclaim any accessible objects. It demon strates that the SGP protocol is generic and adapt able. Therefore, it is a good candidate for a system service.

5

Refinements to SGP protocol

Since our implementation, we have added sev eral refinements [Shapiro 199:2a] to the SGP protocol. These refinements concern both the reference model and the management of delayed messages. We also improved the design of the distributed GC itself that is now divided into a small number of sub-protocols. Each sub-protocol encapsulates a piece of work and collaborates with others. Figure 2 shows the dif f erent sub-protocols and their relationships with the main control data structure.

As shown on Figure 2, we distinguish two kinds of sub-protocols: the mutator protocols and the GC protocols. The former are responsible for maintain ing conservative consistency when passing references from one space to another. The latter track global accessibility and tighten the consistency removing un referenced scions entries.

Application send and receive messages using a low overhead "presentation layer" protocol, with scions and stubs created or updated automatically as needed. The marshalled form of a reference is a locator.

The transport protocol describes the way mes sages are handled (under what circumstances mes sages are discarded for example.

The presentation protocol describes the way ref erence are marshalled in to and unmarshalled from messages.

The invocation protocol details the way in which a reference is used. That is, how locating of the tar get object interacts with the activity of invoking its methods.

The cleanup protocol is responsible for periodi cally sending control messages containing the whole list of lived stubs.

In this section certain key features of the mecha nism are hilighted and discussed in some detail. Par ticularly, we describe the main dif f erences with the SGP protocol and we highlight the interactions be tween the reference model and the distributed GC activity. For the sake of brevity we omit voluntary some details of the protocol. improves invocation efficiency. A stub contains now two kinds of locators (hereafter called locator). The GC invariant enforces that it exist always a chain of strong locator (in absence of space failures) between the source and the target object.

The strong locator serves only distributed GC pur pose and is never used for invocation. Instead invo cations use always the weak locator that shorcuts the chain of stubs and scions. This weak locator improves resilience to space failures since accessibility is not en tailled by indirection space failures. It also improves invocation efficiency because it can access objects in a single hop.

Transport Protocol

The transport sub-protocol is responsible for send ing and delivering messages from one space to another. It also determines the circumstances under that a ref erence may be rejected. This sub-protocol has been improved on the SGP proposal in order to extend the window of acceptance of delayed messages.

We keep now a vector of timestamps, the threshold vector, to deal with delayed messages and keep stub �creation is idempotent. Each threshold vector entry '----� .•• -; �contains a space name and an associated timestamp.

'<.l.r---� -. ;.;"° ,'

In the SGP proposal, we increased the matching en--./ try of the threshold vector each time a message was We have modified the reference model in order to improve accessibility and invocation efficiency. In the original model, objects were only accessible through a chain of stubs and scions potentially crossing sev eral spaces (hereafter called indirection spaces). We noticed two drawbacks with this scheme. First, the failure of an indirection space prevented access to ob jects. Second this scheme was totally inefficient with respect to reference passing. Precisely, passing a ref erence to a chain of stubs and scions resulted in the creation of a new pair of scion, stub on each indirec tion space. The new model solves both problems and sponding entry in the threshold vector.

Actually, a message must be rejected only when acting upon it is not idempotent. That is when the corresponding stub has been discarded. Consequently, threshold entries are now updated each time a stub is reclaimed instead of each time a message is received. The local GC sub-protocol is responsible for reclaiming stubs and therefore is in charge of updating thresh old entries on the basis of timestamps found in garbage stubs. This new policy requires us to keep timestamp value in stubs. Therefore, it increases a little the space cost of the algorithm.

Cooperation with Local GC

Since our distributed GC relies on local GC we needed to find an easily adaptable local GC for C++. Local garbage collection for C++ is a difficult prob lem that has not been successfully addressed yet. All known proposals have majors drawbacks since they are either not efficient enough [START_REF] Edelson | [END_REF], impose language restrictions over inheritance and polymor phism [Bartlett 1989), or are too intrusive to be widely used [START_REF] Ferreira | Reclaiming storage in an object oriented platform supporting ex tended c++ and objective-c applications[END_REF]]. A recent proposal [START_REF] Edelson | [END_REF] matches our requirements: easy to use, efficient, and providing a finalization meehanism.

First, the root set must be extended to take into account the scions list. A straightforward way of ex tending the roots set consists in keeping a head refer ence to the list of scions in the address space of each application. A better solution is to store scions in a fixed memory area known to the local GC. This area should be write protected to protect scions against un desirable modifications from applications.

The local GC is responsible for reclaiming garbage stubs. Stubs must be finalized for two reasons. First, as stated in Section 5, the threshold vector must be in creased when a stub is reclaimed. Secondly, stubs are linked through weak pointers and the linked list must be updated to remove deleted stubs. This latter work may be handled in two ways. First, the local GC may update the list each time it reclaims a stub. This solu tion requires either a finalization mechanism or double linked list. The double linked list is space consuming while the finalization is time consuming since it re quires to traverse the whole list. A better way is to delay stub reclamation to the next traversal of the list by cleanup protocol. The local GC only marks stubs as deleted and the cleanup protocol update the list when it traverses it. This solution avoids costly mech anisms as well as synchronization problems between the local GC and the cleanup protocol.

Related Work

Distributed garbage collection is a difficult prob lem which has only been addressed partially. One key reason is that while most proposals rely on cen tralized techniques, adapting such techniques to dis tributed environments is not a straightforward task. Stop the world algorithms require costly termina tion mechanisms when faeing distribution, whereas reference counting is completely defeated by com mon messages failures. In order to adapt those techniques to distributed environments, many re cent proposals try to relax traditional invariants [Dickman 1992, Piquer 1991b, Watson 1987] whereas others rely on reliable communication protocols [Hughes 1985b, Lang 1992b[START_REF] Mancini | [END_REF]]. The for mer family algorithms is usually based on reference counting. Therefore they cannot garbage collect dis tributed cycles and must assume that such graphs are rare. The second family ensure better liveness but all known algorithms are not resilient to mes sage failures [Lang 1992b), may be completely de-feated by space failures [Hughes 1985b], or fail to ad dress large network (Liskov 1986b]. Our protocol be longs to the former family and bears some similarities to a number of proposals based on reference count ing (Dickman 1992, Piquer 1991b]. Unlike those ap proaches, however, we maintain an entry item per source space that permits us to tolerate message loss whilst avoiding the dangers of duplicated messages.

Dickman [Dickman 1992] proposes Optimizing Weighted References Counting improving tradi tional Weighted Reference Counting [Bevan 1987, Watson 1987] in two aspects: message failures re silience and indirection cells. Resilience to message failures is provided through a weak invariant that re quires that each object weight (total weight) is always greater or equal to the sum of all remote reference weights (partial weights). The weak invariant per mit tolerating message loss but duplicated message re mains problematic. The algorithm avoid the creation of indirections cells when partial weights cannot be split. However, this is enforced through a special null weight value. In this case, the total weight is always greater than the sum of partial weights preventing the object from being reclaimed by error. However, live ness is not ensured for weak objects which conform only the weak invariant. For this reason, the author assumes than the algorithm is always used in conjunc tion with a global tracing collector to reclaim garbage distributed cycles and weak objects.

In [Piquer 199 1b] Piquer describes his Indirect Reference Count {IRC) algorithm which improves Weighted Reference Count [Bevan 1987] by avoiding indirection cells. The algorithm also eliminates the need for increment messages that may conflict with decrement messages in traditional schemes. Thus, cre ation and duplication of a remote pointer are per fo rmed locally without informing the space where the object is located. In order to achieve local creation/duplication, remote pointers have been ex tended with a new field, named an indirect pointer.

The indirect pointer serves only distributed GC pur poses, and refers either to an object or to another remote pointer. The whole set of remote pointers referencing a single object forms a distributed graph which can be traversed using indirect pointers. Muta tors never use indirect pointers, instead relying on the direct pointers to access objects in a single hop. As with others proposals relying on reference counting, the IRC algorithm is not resilient to message failures: liveness is not enforced against message loss and safety is not preserved against duplicated message.

Hughes [Hughes 1985b] describes an elegant algo-rithm based on timestamps and local tracing. The al gorithm timestamps objects and relies on the premise that garbage objects' timestamps remain constant whereas non-garbage objects' timestamps increase monotically. A timestamp threshold is computed to distinguish garbage from non-garbage objects. O b jects that carry timestamps less than the threshold can be safely reclaimed. Unfortunately, the threshold computation relies on a termination algorithm which is notoriously costly and not scalable. Moreover, the algorithm is not resilient to space failures since a failed space prevents increasing the threshold, hence block ing garbage collection on all other nodes.

In contrast to many proposals that attempt to com pute on each space the global accessibility of objects.

Liskov and Ladin [Liskov 1986b] rely on their highly available centralized service to compute global accessi bility of objects on a single space. This service is phys ically replicated, hence achieving high availability and fault-tolerance. All objects and tables are assumed to be backed up in stable storage. Clocks are synchro nized and message delivery delay is bounded. These assumptions allow the centralized service to build a consistent view of the distributed system. Each lo cal collector informs the centralized service about in Furthermore, the centralized service determines the garbage threshold date, making a termination proto col unnecessary.

Recently Lang et al. [Lang 1992b] describe an orig inal proposal to combine reference count and mark and sweep. The algorithm collect distributed cycles within predefined groups. Groups are dynamic collec tions of spaces ( i.e a space may be removed or added during garbage collection) and may overlap or include other groups. The algorithm relies both on counters and local GC to perform mark and sweep within a group. Reference counts must be kept accurate, hence message failures are not tolerated. Group GC is con servative with respect to inter-group references: any subgraph ref erenced from outside the group is not collected until a larger group is formed encompass ing the entire graph; therefore liveness is not guaran teed . Thus, large cycle reclamation requires extending group size such that the group includes all spaces that hold a cycle vertex. Distributed garbage collection of very large networks is proposed through a hierarchy of included groups. Included groups benefit from larger groups GC that perform some of their work. How ever, large group GCs are longer than smaller ones and therefore retain more floating garbage. For that reason, the authors assume that large group GCs are rare compared to small group GCs.

In [START_REF] Lins | [END_REF] [Lins 1991] to address distribution issues. As a result, they propose a simple algorithm to garbage collect cycles in a distributed environment. The general idea of the algorithm is to perform a local mark-scan whenever a reference to a shared graph is deleted. That is, a mark-scan is initiated each time an object is suspected of belonging to a garbage cycle (i.e when its counter is decremented down to one). The mark phase decrements counters each time it visits an object belonging to the subgraph. At the end, all nodes with counters equal to zero are part of a dead cy cle and may be safely reclaimed. Lins [Lins 1991] im proves the basic idea to perform the mark-scan lazily. Spurious objects are not scanned at once but instead they are queued in a special list. When the alloca tor fails to supply memory the corresponding list is scanned in order to reclaim potential garbage cycles.

Unfortunately, mark-scan of subgraphs must be com puted in critical sections. In other words, two dif f erent spaces cannot invoke cycle detection concurrently.

Conclusion

Most of the proposals for distributed garbage col lectors have never been implemented. In contrast, we have experimented with the SGP protocol and the performance measurements are encouraging. We have aslo tested the resilience to messages failures but space failures and duplicated messages remain to be inves tigated. We have added several refinements to SGP protocol. The design of the protocol now relies on small number of sub-protocols that collaborate with each other to provide distributed GC. We have also de scribed the representation of a remote reference which is now composed of two locators. The distributed GC invariant preserves access to remote objects through a chai n of strong locators. The invocation protocol uses weak locators that shortcut the chain of strong loca tors. This new design is part of the Soul project that aims at providi ng efficient and li ghtweight references along with distributed GC. A prototype implementa tion of Soul is underway.

Figure

  Figure 1: System layering

  received. Messages were only delivered to applicationOom.pPni� they carried a timestamp greater than the corre-.... ;:r..

Figure 2 :

 2 Figure 2: Relationships between sub-protocols and main data structures

  coming and outgoing references, and about the paths between incoming and outgoing references. The path computation is expensive but necessary for reclama tion of distributed garbage cycles. Based on the paths transmitted, the centraliz.ed service builds the graph of inter-site references, and detects garbage (includ ing dead cycles) with a standard tracing algorithm. The centralized service informs LGCs of accessibility of objects. In a later paper [Ladin 1992) Ladin and Liskov sim plif y and correct the deficiencies of the above proposal, adopting Hughes' algorithm and loosely synchronized local clocks. Hughes' algorithm eliminates inter-space cycles of garbage, thereby eliminating the need for an accurate computation of the paths and for the central service to maintain an image of the global references.

Table 1 :

 1 Execution Times

			Control Messages
	Application	IRC	SGP	SGP / IRC
	(sort 100)	31	28	10	8	0.32	0.28
	(sort 200)	41	39	10	8	0.24	0.20
	(rnult 20 20)	101	96	20	18	0.20	0.19

Table 2 :

 2 Message Overhead of) stubs and scions. Our implementation is on aver age 10% slower than IRC and 20% slower than with distributed collection turned of f . This result is en couraging: our implementation is not optimized and retained some obsolete data structures and process ing from Piquer's implementation. Futhermore, the fault-tolerance property of the SGP protocol requires a some additional work compared with Piquer's ap proach that largely justifies some added cost.

  ] Lins and Jones combine Weighed Ref erence Counting with Lins'local algorithm for Cyclic Reference Counting


Julien Maisonneuve
email: julien.maisonneuve@inria.fr

Marc Shapiro
email: marc.shapiro@inria.fr

Pierre Collet

Implementing References as Chains of Links

The goal of this work is to provide uniform trans parent access to objects, be they local, remote, persis tent, or mobile. In this way, we facilitate distributed programming and persistence management.

An object (the target) is accessed through a refer ence. A reference retains its meaning as it is copied, stored, passed in messages, and as the target migrates.

A reference is used to invoke a procedure (or method) of the target object. References support standard single-space targets, as well as fragmented objects (9).

The cost of using a reference to a local object is com parable to the cost of accessing the object through a pointer. In the implementation, a reference is a chain of links. Each link embodies a small piece of func tionality. A chain may be composed of an arbitrary number of Links.

Introduction

Distributed systems programming has to deal with different programming paradigms to achieve dis tributed cooperation. A transparent, scalable invo cation and designation scheme greatly simplifies the task of the programmer. Moreover, the ability to per form some work prior to every invocation if needed can provide useful language extensions.

To address these goals, we propose the concept of References. References are used like normal object pointers to invoke methods. The diff erence is that The cost of using reference s is close to the cost of a normal invocation in the local case, and is low in the case of local inter-context invocations. A references is a chain of links from a source to target, each link performing a specialized function, as fast as possible.

The number of those links is variable according to the desired functionality of the chain.

This work was motivated by the lack of flexibility and scalability of most of today's identification and invocation sclhemes.

Previous Work

Distributed object identification has often been implemented with location-independent, system provided unique identifiers (UIDs [START_REF] Leach | UIDs as internal names in distributed sys tems[END_REF]). We see a num ber of problems with UIDs: they are costly to deref erence, they do not conveniently support fragmented objects (2), and they do not scale well. UIDs imply knowledge of a global state that we would like to avoid in the design of a scalable system. Furthermore, UIDs differ greatly from ordinary pointers, forcing program mers to deal with two very diff erent models.

Ports, used by some systems [START_REF] Rozier | Overview of the Chorus distributed operating sys tem[END_REF][START_REF] Avadis Tevanian | Mach: A basis for future Unix development[END_REF] present sim ilar problems. Also, they group a number of func tions together that are not always needed at the same time, thus adding additional cost to elementary opera tions. Those functions are locating, naming, queueing, scheduling and communication protocols. Also, they hide distribution in a system layer that makes multi ple policies hard to design due to lack of information and control.

In some languages, such as C++, it is possible to devise user-defined pointers with special dereferencing operators (the overloaded -> or * in c++) yielding a raw pointer. Distribution, persistence, and other similar models may be hidden in such "smart pointers" [START_REF] Stroustrup | The evolution of c++ 1985 to 1987[END_REF][START_REF] Daniel | Smart pointers: They're smart, but they're not pointers[END_REF] using an appropriate dereference procedure.

An example is the permPtrs to persistent objects in SOS [START_REF] Shapiro | SOS: An object-oriented operating sys tem -assessment and perspectives[END_REF]. A permPtr contains the UID of the tar get persistent object and a raw pointer that is ini tially null. On first access, the dereference procedure maps in the target (if it's not already there), sets the pointer to its address, and returns the pointer. Another popular object identification abstraction uses stub objects. A stub has the same interface as its target, but all the operations are redefined to send messages along a connection to the remote target that is identified in the stub's data. In our opinion, stubs alone are not flexible enough when dealing with ob jects that can move, or whose location is not precisely known.

Stubs can be extended to handle persistent objects, as in Amadeus [START_REF]Overview of the Amadeus project[END_REF]. In this case, a dummy, uninitialised object of the same size as the target is allocated. Its procedures are redefined to trap to the system. On first invocation, the program traps, causing the data to be read in (overlaying the dummy object) and the procedures to be redefined to their proper meanings; the invocation is then restarted. Subsequent invoca tions execute the correct procedures, which find the data already loaded. This approach does not provide enough flexibility for a real persistence system.

An extension to the stub idea, called proxies [START_REF] Shapiro | SOS: An object-oriented operating sys tem -assessment and perspectives[END_REF].

gives access to fragmented or replicated object � . I . n SOS, a fragment containing the data for a replica ts imported (i.e. migrated in) on first access, as detected by the compiler. Its procedures must know how to communicate with the other fragments and maintain consistency. Using this approach, arbitrary policies can be implemented. The burden is placed on the proxy code, that can become quite complex and mono lithic.

The Emerald language provides references support ing a few predefined cases [START_REF] Jul | Fine-grained mobility in the Emerald system[END_REF]. An Emerald reference is a pointer to a descriptor that contains the target's data, a remote addr ess (based on a UID), or a pointer to a further descriptor that itself contains the data.

Emerald references support efficient access to local data and transparent access to mobile (local/remote) objects. Persistence is not provided.

Chains of Links

Our references are similar to those of Emerald.

They allow transparent designation and access of ob jects that is independent of the object's state or loca tion. They also offer transparent inclusion of special policies for sharing, placement or persistence. Finally, they support this scheme efficiently, keeping the cost of local invocations over references comparable with normal invocations.

A reference is a chain of maillons1, each of that is similar to an Emerald descriptor. A mail/on is also like a smart pointer, supporting a dereference proce dure: at each level of maillon, the procedure performs a piece of work. This mechanism supports both effi cient local pointers, and arbitrary-length chains im plementing complex policies.

A maillon is composed of two parts: a data part (usually the identification of the next link on the chain) and a pointer to its dereference procedure that knows how to interpret the data part. This deref erence procedure can change dynamically to •accom modate the state of the object and provide different functions.

The simplest maillon acts like a pointer. Its data part is a direct pointer to the target. Invocations over this maillon results in invocation on the referenced object through the dereference procedure.

Another simple maillon type acts as an indirection to the next maillon that permit the creation of chains, each link providing a particular service. The next maillons address is stored in the data part. The deref erence procedure simply jumps into the next maillon's dereference procedure.

These maillons are useful for example to create in directions in order to share objects, or to keep track of objects in some "object table" (e.g. Edelson's "root tables" [START_REF] Daniel | Precompiling c++ for garbage collection[END_REF]). A garbage collector could conceivably re move redundant indirection maillons.

More interesting cases are references to remote, per sistent and fragmented objects. They imply the use of specialized stubs for each function.

1The French word for a link of a chain.

3.1

Reference to Remote Object

In our terminology, remote qualifies an object in another address space, be it on the same machine or not. The actual location of the remote object is totally transparent to the client.

A remote maillon is initialised with its dereference procedure pointing to an initial binding procedure. This procedure has to establish the conditions for sub sequent invocations and will be called on first invoca tion.

More specifically, this binding function has to eval uate the reference contained in the maillon to decide which protocol is best suited to communication, and must establish the invocat�on path. It then completes the invocation. Further invocations will go more di rectly to the stub by resetting the dereference pointer to point to a simple indirection procedure (as in the local case).

In order to have an uniform interface, an invocation on a remote object must go through a stub object with the same interface as the target. The stub address will be used by the indirection procedure to relay invoca tion after the binding phase.

Usually, stubs do the marshalling as well as the communication part. We felt it necessary to separate both operations to keep the invocation of the remote object transparent wherev•er the target may be. We therefore divided what is usually called a stub into a marshalling stub and a connection stub.

Upon invocation of the methods of a marshalling stub:

• the procedure name and arguments are mar shalled in a message,

• the connection stub is invoked with the message,

• the connection stub waits for a response message,

• the marshalling stub unmarshals the response message, and

• the marshalling stub returns the result.

On the other end, at the destination context, a scion is responsible for the reconstruction of the in vocation, its delivery and the return of a reply. Stubs and scions are generic objects that perform the mar shalling and unmarshalling of invocations: they are mechanically generated from the declaration of the class they represent.

Each reference potentially uses a diff erent transport protocol depending on the location of the accessed ob ject. The binding procedure can dynamically decide on the best protocol. If the referenced object appears to be in the same context, the maillon is transformed into a simple indirection maillon (its dereference pro cedure being an indirection to the local object). If it points to a different context on the same machine, a URPC or LRPC protocol [l) using shared memory can be used. Otherwise, a RPC-like protocol will be used to carry the invocation across the network. The latter two imply the creation of a stub whose interface con forms to the target object's interface. This stub will be referenced by the data pointer so that it replaces the object in the invocation.

3.2

Type Checking

In distributed environments, one may not always know the actual type of a transmitted reference, or guess wrong about it. The results of such errors can be unpredictable since scions will try to reconstruct invocations based on incorrect data specifications. To avoid that, we must perform minimal type checking.

Current compilers for well-typed languag.es are typ ically built on the assumption that the program can be type-checked statically. This is not necessarily true when we consider persistent or remote objects: we have to be able to type-check them to detect user er rors. These compilers need to be extended to emit type information, that can later be used for run-time type checking [START_REF] Gautron | Two exten sions to C++: A dynamic link editor and inner data[END_REF].

The binding procedure can be responsible for lim ited type checking. Since objects are not supposed to change type dynamically, verification at binding time seems to be a reasonable option. The type informa tion can be stored in the maillon itself or in a place where it can be recovered using the maillon.

A type mismatch error is usually a fatal error to the faulty process since it means that the program guessed wrong about the semantics of the objects ac cessed, thus making them unusable. This condition must be handled by a run-time module to produce sensible termination/recovery behaviour.

Reference to a Persistent Target

References can be used to access persistent data.

We will only consider a simplified view of a persistence system, accommodating a single copy in memory and a single one on disk; the full architecture of a storage system, along with concurrency and consistency con trol between multiple copies is out of the scope of this paper [START_REF] Soulard | A generic FO-structured framework for persistence support in di stributed settings[END_REF].

A persistent object is stored on disk. It is copied into memory upon first access and then used as a local object. If modified, it is copied back to disk after use.

As with remote targets, the binding procedure can be used to establish the conditions for performing an invocation. Applied to persistence, this binding func tion allows us to load the object before invoking its member functions.

The same remarks that were made about type checking in remote references can be applied to per sistent references. The binding procedure is also the place to check for type conformance.

A maillon to a persistent object contains its tar get's identification (e.g. the target's name on disk) , a type field (containing the compiler-generated expected target type), and a pointer, initially null. On first ac cess, the dereference procedure will: lock itself against concurrent updates, read �n the object, check the read in type against the expected type, set the pointer to the newly-read object, change the dereference pointer to the indirection procedure, unlock itself, and return the pointer. Subsequent accesses directly execute the indirection code. Un loading the object is relatively easy if there is a single such persistent target maillon; any aliases should be indirection maillons to the per sistent maillon. To unload, atomically set the deref erence pointer back to the initial load procedure and set the lock, then copy any modifications to disk and unlock.

A more realistic view of a persistence model would include a storage context interacting with user con texts. Multiple storage and consistency policies can be supported by using speeialised stubs and multi-level maillons chains [START_REF] Soulard | A generic FO-structured framework for persistence support in di stributed settings[END_REF].

References to Migratory Object

3.5

Reference to Fragmented Object

A fragmented object (FO) is a distributed object made of fragments (local objects) located in different address spaces. In many cases the fragments in a par ticular address space can be known early and instanti ated statically. With respect to the reference system, a static fragment behaves just like a stub, and the same techniques described in the previous section are used. In the general case however, the fragment must be instantiated dynamically by a "fragment factory".

In this case, a mixture of the techniques described for persistent and for remote targets is used. When a ref erence to a FO is initially created, such as by receiving it in a message, in a migrated object, or in persistent store, it is in the unbound state [START_REF] Dickman | Contrasting fragmented ob jects with uniform transparent referencesfor dis tributed programming[END_REF]. An unbound ref erence has the following characteristics:

1. it identifies some remote fragment, but not nec essarily the one that will ultimately be used; 4

Distributed Reference Management

This section will review the general mechanism of the distributed references along with the invocation protocol and the garbage collector.

In order to be able to use a reference when it is transmitted to another space, we must register the fact that the referenced object is accessible from outside. This is done by creating a scion pointing to the refer enced object. The scion's identification becomes the external identifier for the object , that wm be trans mitted to the outside world.

Thus, in order to create the scion when a refer ence is exported, references must be detected when passed in a parameter or as a parameter in a message. The automatic generation of stubs must generate the proper code when a reference is detected.

If this reference is again passed to another space, a scion-stub pair is formed in the intermediate space that is a simple indirection . . That way, indirect chains are created between the source of the reference and its target. A way to avoid the marshalling-unmarshalling step in this case should be provided to make indirec tions cheaper, although this is an optimisation.

Shortening Chains

Liberal use of indirect reference chains allows a ref erence to be passed cheaply in messages while retain ing the guarantee of reachability. However, when con sidering communication, references are harmful: not only because of the overhead and poor locality, but more fundamentally because sending a reference along an indirect chain creates yet another indirect chain. If this same reference is returned as a result, things dete riorate further. It is necessary to have a way of short ening unnecessarily long chains to avoid unacceptable remote communication delays. This work is performed by the invocation protocol itself.

In the initial binding phase, the initial connection message used to perform the type checking is sent to the destination. The reply to this message contains the actual location of the target (or rather of the ter minal scion pointing to it); the reference is then up dated and the invocations will follow the new short path.

When the binding step is over, the target object object can move as a result of object mig, ration. The chain is reconstructed as explained before. The next invocation over the bound chain will result in a loca tion exception being returned from the migrated space to the invoker with the identification of the next scion in the chain. The caller can then reset the destina tion field to point to the new location and restart the invocation.

4.2

Garbage Collection

Garbage collection is useful in centralised objects systems, but it is even more important in distributed objects systems. It allows us to avoid the problems as sociated with the tracking of remotely referenced data in an environment where they necessarily flourish.

Distributed references allow an easy integration with a distributed garbage collection system because we already keep track of outgoing and incoming refer ences. The addition of a local garbage collector and of a specific protocol allows us to have a workable d i s tributed garbage collector.

The distributed garbage collector uses the connec tion stubs to track external references and the scions to track incoming references. It also needs a small number of data structures for itself. Every scion con tains an indication of the space that points to it. Also, to improve the fault-resistance of the protocol, times tamps are used and have to be included in the mes sages and in the stubs and scions.

The local garbage collector traces references from the local root and the set of all local scions. An unreachable stub is garbage and can be collected. The scion-stub pairs that become useless, i.e. through chain shortening, are automatically reclaimed when ever it is safe.

A connection stub associated with a marshalling stub contains a locator composed of two parts, called strong and weak. Each part points to a scion and consists of the identifier of the space containing the scion and the valid scion name within that space. The strong part identifies the scion that matches the as sociated stub. The weak part identifies a scion that, while part of the same chain of strong indicators, may be closer to the target object. Weak parts are used for communication and location, that rely on the in variant that the indicated scion will not be collected, being protected by the strong chain.

Distributed garbage collection relies on the invari ant that (in the absence of failures) there is always an uninterrupted chain of stubs' strong parts and scions (hereafter called a "strong chain") between the source and target of a remote reference.

A scion may exist for which the corresponding stub no longer exists. This may cause the local garbage collector to believe that there is a remote reference to a local object, whereas in fact, none exists. For this reason, garbage collection is somewhat conservative.

The protocols ensure that eventually the unreferenced scion will be reclaimed. Then, the objects reachable only from that scion become garbage and may be re claimed by the local garbage collector. In our scheme, all unreferenced scions will eventually be reclaimed. Thus, all local and acyclic distributed garbage will eventually be reclaimed (to the extent that the Local Garbage Collector is itself exhaustive).

The weak locator chain is used for invocations 2 and the strong chain i s lazily short-circuited in a safe fashion as described earlier. Obsolete indirect stubs and scions will be cleaned up later by the garbage collector.

Application code sends and receives messages us ing a low-overhead "presentation-layer" protocol, with scions and stubs created or updated automatically as needed. Messages, in particular from the garbage col lector, can be piggybacked to offer better performance.

A detailed account of the distributed management of references can be found in [START_REF] Shapiro | Robust, distributed references and acyclic garbage collection[END_REF].

Reference Scope

In order to keep the system scalable, the scheme described above is valid only within a ce. rtain domain. Between domains are gateways that are responsible for translating protocols and naming conventions. Also, references must remain valid in the domain where they ares sent or be translated to remain so.

The gateways hosts scions that look terminal with respect to the garbage collector and the shortening protocol, but that are only specialised translators to other remote objects in another domai n. That way references can span several domains but also be trans lated to interact with other protocols. The references were designed without being specif ically targeted to a precise language. However, we needed an object-oriented language, one versatile enough to allow us a flexible and efficient implementa tion. It turned out that C++ seemed a good option : it had most of the features we needed, we had some 2H objects do not migrate, the weak locator is guaranteed to indicate the space containing the target object.

knowledge of it, and we had a (local) garbage collector in sight for c++.

The first design was very close to the original model, but not very well suited to C++. The maillons had (at least) two fields: one contained a code pointer and the other a pointer to a data part. The nature of the func tion pointed to by code determined the nature of the data part. The idea was to jump to our code function without modifying the stack, thus keeping the argu ments for the real invocation. In the case of the local indirection, the function just had to perform the in vocation. However, it was not easy to reconstruct the invocation from in code in certain cases (particularly dealing with virtual functions).

Our second try was based on two observations: first reconstructing the C++ calls by hand was a pain; sec ond the code we had to generate to perform this in vocation was excessively long because we had to guess what the compiler knew so well. It was not really slow, but we found another much cleaner way with comparable cost, and improved clarity.

The second implementation was a bit dif f erent : we let the compiler build the invocation itself. We re defined the operator -> to call our code function, itself returning the address of the actual object (or stub). It was also inlined so that ref->foo(1) be

came (ref.(•code)())->foo(1).

The maillons are typed objects (actually C++ tem plates) that contain a code pointer and a pointer to an object of the referenced class, (or rather of the ref erenced abstract class, since we mostly care about in terface conformance and do not want to inherit data).

The procedure pointed at by code returns the address of a local object that can either be a real object or a stub.

As references are copied or passed as parameters, they must .revert to an unbound state. This is why we use a copy constructor to reset the code pointer to the bind procedure. That way, we ensure that a ref erence chain is unique and that stubs are not shared, an essential property for garbage collection.

The stub and scions generation has to• be done by a preprocessor (in fact almost a real C++ compiler, since it has to generate them from class declarations). The stub generation i s still manual, but we're studying c++ precompilers for automating it.

Local references must occasionally be modified, like during object migration. When a reference is created, its constructor stores its address in a table so that the reference can be retrieved using the address of the object it points to. This is similar to the root pointer discovery in a local garbage collector.

The cost of local invocations is low because it re quires only a added call of leaf, parameter-less func tion consisting in a return instruction. The indirection maillon (that calls another maillon) is even faster since the dereference procedure can be reduced to a jump to the next maillon's code procedure.

The current prototype supports local, remote and URPC invocations based on the same marshalling principle. Garbage collection and distributed refer ence management is under implementation.

7

Conclusion

We have designed a flexible, uniform reference sys tem for local, remote, persistent, migratory, and frag mented objects, supporting a range of different policies as well as distributed garbage collection. Flexibility derives from two key design decisions:

1. a reference is implemented as a chain of links of arbitrary length;

2. each link has its own dereference procedure.

This design is the base for a scalable reference scheme not using UIDs, supporting distributed, ro bust garbage collection [START_REF] Shapiro | Robust, distributed references and acyclic garbage collection[END_REF] and is the basis for an object-support OS framework [START_REF] Shapiro | Soul: An object-oriented OS framework for object support[END_REF].

We have presented a preliminary design that is un der implementation. The system is designed with per formance and flexibility in mind, and should reflect those goals in its complete implementation. We plan to have a working prototype and experiences at the time of the workshop.

•

  Julien Maisonneuve and Pierre Collet are also• affiliated with Laboratoire MASI, Universite Paris 6, 2 place Jussieu, 75005 Paris. tThis work is supported in part by the Ministere de la Recherche et de la Technologie they allow the target to be in another context, on an other machine or even stored on disk. Fragmented and migratory objects are also addressed.

  Migratory objects are objects that are accessed in a single context at the same time, by phases, then in another, and so forth. The simplest policy to acco modate such objects is to move them where they are accessed, thus the name of Migratory. A migratory object typically has several references pointing to it, a number of which are indirected through intermediate spaces. When an invocation is performed through one of the references, in the target context, the specialized migratory scion detects the access. It initiates the object migration while patch ing the other scions pointing to the object to point to freshly created stubs. The local references must also be patched to point to freshly created stubs, so we have to keep track of them. On the invocation site, the object is reinstalled and scions are recreated for the incoming references of the previous location. Then the (now local) invocation can be performed. This requires again to patch the local reference.

2. the location of the remote fragment may not be precisely known 3 .

 3 it does not support the full interface of the target, but only the single operation bind; 4. it must be bound before use. Binding at first use is ensured by setting the head maillon 's dereference pointer to bind. bind is a generic procedure, independent of the tar get's expected or actual type. It sends a request mes sage to the fragment indicated by the unbound mail lon, passing identification of the invoker (taken from its context) and the expected type (stored at compile time inside the maillon). That fragment responds with the type of the caller's local fragment and with initial isation data., including a single bound reference, i.e. one with a precise location, and assigned to a precise interface of its target. The type and the initialisation data are passed to the language-specific runtime, to check against the expected type, and to create and/or initialise the local fragment, the address of which is returned. Finally, the maillon is set to indirect to the new local fragment. After this, the local fragment will communicate with its peers over the bound reference retrieved by bind. It should be noted that fragmented objects are the general case. The mechanisms for local, remote, and persistent targets, specified in the previous sections, are transparent optimisations for special, restricted cases.

6 Implementation

 6 This section gives a few comments about the im plementation in progress. It i s by no means a imple mentation report.

Acknowledgements

We would like to thank David Plainfosse for his work on distributed garbage collection and for many talks that helped to shape up the system. We would also like to thank Daniel Edelson for his useful remarks on this paper.


Marc Shapiro

Laurent Amsaleg

Alain Sandoz

Robert Cooper

A Binding Protocol for Distributed Shared Objects

A number of actions, collectively known as binding, prepare a reference for invocation of its target: locat ing the target, setting up a connection, checking access rights and concurrency control state, type-checking, instantiating a proxy, etc. Existing languages or op erating systems support only a single binding policy, that cannot be tailored tt> object-specific semantics for the management of distribution, replication, or persis tence. We propose a general binding protocol covering the above needs; the protocol is simple (a single RPG and one upcall at each end} but recursive; however the recursion can be terminated at any point, trading off simplicity and performance against completeness. This comp rehensive, unified protocol is capable of sup porting different languages and object models, and may be tailored to support various policies in a simple man ner.

provided the initial ideas for referencing and binding to FOs. David Plainfosse implementated SSP Chains; Marcin Skubiszewski did a graphical animation of the implementation.

Introduction

Any computer system supports some reference mechanism (such as ports, sockets, file descriptors, UIDs, capabilities, or the like) for identifying and accessing objects so that they can be shared by programs. When applied to large-scale distributed object-oriented applications, existing distributed ref erence mechanisms have serious shortcomings: they do not support garbage collection, type safety, object groups, replication, persistence, migration, nor appli cation policie.s for managing distributed data in gen eral. The current work examines some of these issues, and proposes a binding protocol that includes up-calls to application-or language-specific policy modules.

This protocol is used to ensure type safety and to This study takes place in the context of SSP Chains 19], a light-weight, fault-tolerant reference mechanism supporting garbage collection; but it is likely that our ideas could be applied to other reference mechanisms as well.

2

Background and motivations

Objects are of fine grain a.nd arbitrary type; types change over time; and objects may be composed of distributed fragments.

Our object and reference model (explained later, in Section 3) distinguishes logical objects (the targets of references) from the lowest-level resources that imple ment them, called atoms (identified by address).

Limitations of existing binding sys• terns

In operating systems, binding means locating a tar get, checking rights, and setting up an access path and method from the client to the target.

(For instance

Unix primitive open binds a file reference.) The final target is typically outside the client's address space (e.g., a file implemented by the kernel or a service pro vided by another process).

An OS binding is done at run time, is location independent, and relies on an untyped channel.

In language systems, atoms are memory locations; a binding is a mapping between a variable and such an atom along with the code operating on the data.

A language binding is type safe, but references do not cross address space boundaries.

Some systems combine features of both operating system and language bindings. For instance in a re mote procedure call (RPC) system [START_REF] Birrell | Implementing Remote Procedure Calls[END_REF], binding sets up a typed stub object that hides an untyped connection interface to a server. Similarly, a persistent object sys tem [START_REF] Morrison | Bindings in persistent progra.mm ing lan guages[END_REF] faults on the first access to an on-disk object, and copies it into a memory cache object, before the application can observe that it wasn't there; the result of binding is the cache, itself bound to a disk location.

In order to transparently share (potentially persis tent) objects in the distributed system, there is a need for a more flexible and smooth combination of system and language bindings. An outline of the protocol is as follows (a. more de tailed presentation comes in Section 5). The unbound reference targets some remote atom of the referenced object; binding produces a local proxy for the object (for instance, a stub or a cache) that in turn connects to a further atom (respectively, a remote server or some on-disk data). Binding invokes method accept bind of the initial target. On the client side, instan tiation method new is upcalled with the information returned by the target.

A general binding protocol

An important goal of distributed system design is transparency, e.g., the target of a reference being ac cessed independently of its location. From the per spective of an object's client, transparency is a good thing. But the implementor of an object may need control over location; for rnstance, a replicated file manager must control replica locations. In our pro posal, the target of a reference controls transparency via accept-bind. The accept-bind default sets up trans parent remote access, but we will look at other exam ples, notably persistent objects.

Objects and references

In this section we state the object and reference model assumed hereafter. This model is relatively strong, but restricted versions of the protocol will run in a system with a weaker model.

Objects and references vs. atoms and addresses

An object is any entity of interest in the computer system. A reference designates some particular target object. The abstract concept of reference is imple mented by a system-provided object called a handle.1

The holder of a handle (a "client") may pass it as an argument or result of an invocation, and may invoke the target. Handles have a well-defined interface, de scribed in Section 4.

An object is a logically encapsulated entity, possi bly composed of sub-objects. A bottom-level object (a physical resource, such as a memory location, or a system primitive, such as a transport connection) is an atom. A handle designating an atom contains i!ts address. The base level of invocation is the local procedure call of an atom.

User objects are composed of two kinds of atoms:

memory extents (attached to some class) and OS prim itives. The former is identified by a memory address, the latter by an OS identifier, that we also call an ad dress to emphasize the efficiency requirement. Such an OS address is normally hidden by a stub. A stub is a normal memory atom known by its memory address.

Object, class and type model

We assume very little about objects: only that ev ery object accepts upcalls to method accept-bind, spec ified in Section 5.2.

We A type reference characterizes an interface, i.e., the signature of the methods or operations that ap ply to objects of that type. An object supports at least all the operations of its eff ective typ e, known at run time. The client will call at most the meth ods of the statically-known presumed type of the refer ence. The effective type of an object must conform to the presumed type of references to it. Confor mity checking occurs either at compile time (within a statically-linked set of compilation modules) or at run time (across static checking boundaries). In or der to support dynamic type checking, a handle must store the the presumed type of the reference, provided by the compiler.

We make no assumption about types. We only as sume the existence of type references,2 and that a class has a way to check its conformity with a given pre sumed type reference. We do not define conformity, because it is language dependent.

Fragmented objects (FOs)

An object is a single logical encapsulated entity.

However, many interesting objects are actually repre sented by a group of atoms instantiated at different times and/or in different locations. For instance, a persistent object (see Section 6.3) has a disk image (one atom), and zero or more images cached in mem ory (more atoms). We call any such distributed group of atoms a "fragmented object" (FO).

Binding a reference to an FO yields a local atom, the caller's proxy for the FO [START_REF] Shapiro | Structure and encapsulation in dis tributed systems: the Proxy Principle[END_REF]. We return to FOs in Section 6.

4

Handle primitives

Recall that a handle is the system-provided object that implements the reference abstraction. The op erations on references are listed below (ignoring the obvious ones such as create, delete, duplicate).

Binding

The operation bind binds a reference, in order to make later invocations simple and efficient. Binding performs some checks and sets up an access chain to the target; it yields a handle to be used in place of the original. The checks should verify the pre-requisites to invocation, e.g., access rights, concurrency control state, type, etc. The binding protocol is detailed in Section 5. To support specific policies, our binding protocol gives some control to the target object.

Invoking target

A bound handle supports invoking by following down the acoess path to the target, and executing one of its methods.

For instance, dereferencing a pointer yields the cor responding memory address, in order to load or store the corresponding memory cell. Dereferencing a Unix file descriptor number occurs when executing a read, write or similar system call.

Just as every reference resolves to an address, every invocation resolves to a local atom invocation.

Faulting

Some systems support implicit binding through faulting: an attempt to invoke through an unbound handle raises a fault.

To provide faulting, unbound and bound handles appear the same to client software but th•e system checks the state of the reference at invocation time.

Unbinding and redirecting

Operation unbind breaks an existing binding; the reference must be bound again before use. Unbind can be user-or system-initiated, e.g., using an LRU algorithm or timeouts. In general whenever any cor rectness conditions established at bind time may have been violated, the binding should be broken. This can occur either at the client or at the target end of the reference.

To implement unbinding, the system adds some state at both ends of the access chain and tests this state at each invocation. This state can be the same as the one used to implement faulting.

Combining unbinding with faulting is one way of supporting redirection of references. Redirection breaks existing bindings and selects a new target. Run-time mobility of users, objects, machines, or ap plications, necessitates redirection. This same mecha nism supports fragmented objects, as will be seen.

Redirection is transpar•ent and atomic, for all clients of the same reference. Examples include Unix 1/0 redirection or the SmallTalk become primitive.

5

Binding in detail

This section details the binding protocol. First we specify it without justification. Section 5.1 outlines the different steps; Sections 5.2 and 5.3 describe the up-calls to application-or language-specific modules.

In Sections 6 and 7, we will apply it to a number of interesting examples.

Specification of the binding protocol

Binding a reference is the execution of the bind method on the handle object representing that ref erence:

unbound-handle.bind (a ppl-specific-args)

-+ bo und-handle
The bind method is system-provided. It extracts the presumed type of the reference from the handle, and locates the target atom. It then performs a remote invocation of the target's binding method, passing the application-specific arguments (of which we will see some examples in the course of this paper) and the presumed type:

target.accept-bind ( prsumd-type-ref, a ppl-specific-args)

-+ proxy-class-ref, cntntn-ref, init
The accept-bind method is provided by the target ob ject; it returns a reference to a class (that can cre ate the proxy object), a "continuation" reference, and some initial data. These results are returned to the client side, where the system then upcalls:

proxy-class.new (prsumd-type-ref, cntntn-ref, init) -+ proxy-object
This returns a proxy, which will be an initialized atom of the specified class. The continuation reference con nects the proxy to the rest of the access chain.

The default accept-bind returns a stub class for in voking the target (the server) remotely, an open con nection to the target, and null initial data.

Note that proxy-class-ref is a reference to a class object. Before calling new it must be (recursively) bound, yielding proxy-class (see Section 7). The pro tocol will also iterate if the continuation reference is unbound (see Section 6).

Specification of upcall method accept bind

The unbound reference designates some initial atom. The binding protocol callls method accept-bind of that original target, allowing it to control the out come of the binding.

The first argument is the presumed type of the ref erence. If it conforms, then the target is assured of understanding messages that will later be sent by the proxy. The targ•et checks this type in some language specific manner.

The other arguments are (unspecified) "application-specific" arguments. These could include an access mode, an authenticator, a site identifier, or a transaction identifier for the caller.

Method accept-bind returns the information neces sary to choose or create the proxy on the client side: a proxy class reference, some initial data, and a c•ontin uation reference. Different proxy classes may imple ment different presentation and/or transport protocols or dif f erent consistency policies.

Normally the initial target will return a bound ref erence to itself, but it can also return a null reference if no continuation is needed, or an unbound reference to itself or another atom. An unbound reference forces the proxy to iterate the bind protocol again !before invoking.

Specification of proxy-returning up call method new

After the RPC to the initial target returns to the client, the system upcalls (at the client side) method new of the specified class, with the presumed type, initial arguments and the continuation reference.

The new method is supposed to first check the class for conformity with the presumed type, presumably by calling a language-specific dynamic type checker.

.x -• . . .. Ji: ..... Method new returns the address of a local proxy. It creates one, or possibly re-uses an existing appro priate proxy. If creating the same proxy twice is to be avoided, then the arguments must contain enough information to ensure uniqueness.

The proxy uses the continuation reference to set up the access chain. For instance a stub will connect itself to its server; a cache to its file server; a replica to other replicas.

Note that the RPC to the initial target returned not a class object but a class reference. In order to call the method new of the class object, the reference must be bound, recursively invoking the binding protocol. If the class has already been bound, then the binding protocol can return immediately. Otherwise is should go to a trusted class repository. The proxy returned by the class repository contains the actual code for the class (it is a locally-cached, read-only copy of the contents of the repository).

6

The binding protocol applied to dis tributed object management

In distributed systems a logical object is often repli cated for availability and fault-tolerance, or cached for performance. Thus a logical object can be fragmented, i.e., constructed as a group of fragments in differ ent locations. Few existing reference systems support groups or fragmented objects (FOs); those that do wire in a. single binding policy. We show here how the general binding procotol supports many different forms of fragmented object and different object distri bution policies. Our solution for referencing an FO is to reference a specific factory3 fragment; at bind time, the factory's accept-bind may redirect the reference to another frag ment (possibly creating or migrating it on the fly). For an example, see Fig. 1. Any fragment will do as a fac tory, as long as it implements an appropriate accept bind. For fault tolerance, the factory itself may be a replicated object.

Remote access through a stub

Let us first illustrate the default application of the binding protocol, providing remote access to a "server" through stubs [START_REF] Birrell | Implementing Remote Procedure Calls[END_REF]; see right part of Fig. 2

. 4

In this example, the reference of Client 2 to xd is redirected, at bind time, to a local stub, itself con nected to a remote in-memory server Xm • There after, the client calls the stub's methods locally. A stub method marshalls arguments into a call message, sends the message, and awaits and unmarshalls the re turn message. A "stub generator" mechanically gen erates stubs and scions from interface specifications. -----.

, ,�,�� , '?.

/2d, bind 3 . --------' ----� !.��'! } ....... ..;'

2a •• ••••• •••••••••� Cache Xm File x.i ---- 2c •••• ••••••••-• -c.lli1ti iAitia1ty ---cna!ed iD IOWld I • • • • • Cl'ell ad in l'OllDd 2

Cached persistent object

We show how the general binding protocol supports distributed access and caching of a persistent object. This is illustrated by the le. ft part of Fig. 2. Initially, the persistent object exists as an atom on disk xa, managed by an object storage server. The initial ref erence designates the disk atom through the server; the server implements accept-bind.

The purpose of bind is to copy the on-disk atom into a cache Xm, an in-memory atom. Thus accept bind checks the client's access rights, and allocates a scion at the storage server, describing the open object.

It returns a cache class with an appropriate interface,

an open connection to the storage server to serve cache misses and to ftush updates made by this client, and initial data to prime the cache. The cache class is instantiated, yielding Xm.

Cache call-back

In the next section (Section 6.5) we will look at some cache consistency policies. All require a call-back reference from the server to caches. The same bind ing protocol supports passing the call-back reference from the client to the server, but this requires a bit of ingenuity. We will describe two implementations, a pessimistic and an optimistic one .

The pessimistic implementation requires two rounds of binding. The first cr• eates the cache, and the second passes the cache reference to the server. In the first round, the server's accept-bind returns a cache class, empty initial data, and an unbound reference to itself. This crea.tes an empty cache proxy that will implement the second round, by faulting at the first access. In the second round, the application-specific arguments, supplied by the proxy, contain a reference to the cache, which will b� recorded by accept-bind as the call-back. The second round returns the same cache object, primed this time with initial data to prime it, and a bound reference to the server. This implementation is fully transparent, as the client need not be aware that something special is being done to set up the call-back.

The optimistic implementation avoids the first round by instantiating the cache in advance, for in stance at compile time. Based on the presumed type of the reference, it is bound at compile time to a cache (a partial binding) that implements the optimistic pro tocol. The proxy's bind method allocates an empty cache at the client end and passes its reference in the application-specific arguments. The class reference re turned by accept-bind normally would be the same as the statically-bound cache class; if so new just returns the address of the existing cache, primed with the ini tial data. If however the class is dif f erent, then another round is necessary, as above.

Existing systems with call-backs, such as AFS [5J, install proxies statically. Our optimistic i mplementa tion also binds a caching proxy statically. It ha.s the advantage over AFS that, if a dif f erent policy is de cided alter compiling the client, our optimistic imple mentation automatically falls ha.ck to the pessimistic implementation.

6.5 Shared persistent object caching poli cies Even when multiple caches are allowed for the same object, no more than one should be allocated per client or per machine. The Spring binding protocol [START_REF] Michael | Experience building a file system on a highly modular operating system[END_REF] is es pecially designed for cache management and ensuring uniqueness. There is a single (optional) file cache man ager per machine; all clients on one machine share a single cache to any file, via the cache manager.

Again, the general binding protocol accomodates this. A pessimistic, transparent implementation needs three rounds of binding, as illustrated in Fig. 3. Ini tially the client has a reference to a file at the file server. In the first round the client contacts the file server; the file server returns a proxy class that knows about cache servers (and an unbound reference to it self). In the second round, the proxy :first asks the local cache server to instantiate a cache Xm, passing the file reference as an argument; the cache is initially empty and refers to the server through the (unbound) reference passed by the client. The proxy then binds, passing the Xm reference as application-specific argu ment; the file server responds with the same proxy class and the (unbound) reference to Xm (not to it self). In the third round, the client binds to a stub x�, which binds to the cache, with itself binds to the server, which returns initial data.

As an. optimization, if the server already has a call back reference to the appropriate cache manager, it responds with a reference to the cache, skipping the second round. If the cache is already bound, the cache server binding of the third round can also be skipped.

Also, an optimisitic impl•ementation (along the lines of Section 6.4) needs only a single round, binding directly to the cache manager. The optimistic implementation is the same as the binding protocol used in Spring [START_REF] Michael | Experience building a file system on a highly modular operating system[END_REF], with the added advantage of automatic fall back onto the pessimistic implementation in case a different policy is decided at run time.

7

How the recursions in the protocol support type and class management

In the previous sectio•n we showed how the binding protocol supports object-specific distribution policies.

In the current section, we will show how it supports language-specific code and type management policies.

7.1

Recursive definition of handles and types

If a handle contains a presumed type, and a type is represented by a. handle, then a. type-handle con tains a type-type-handle, and so on. What then is the type of a type? One reasonable interpretation is to consider an object universe with a partitioned type universe. For instance, each site in the system man ages a separate schema; then the type-type identifies the schema. Two types with different identifiers in dif ferent schemas may still conf orm; if a global schema oversees the local schemas, then recursively invoke the global conformity checker.

The recursion terminates by a (static) decision not to implement any higher levels. For instance, for those references that can be type-checked statically, the pre sumed type can be left out of handles, and the corre sponding run-time check omitted. In a system that needs dynamic type checking but supports only a sin gle type system, then type-types (and higher levels) are omitted.

There is clearly a trade-off between flexibility and potential complexity of a type check; it is doubtful a real system would need any more than a small number of levels. For instance, Spring uses a single level; the SOS bind is recursive but only a single level is ever used in practice. Similarly, the CORBA specification implicitly assumes an optimistic implementation [START_REF]The Common Object Request Broker: Architecture and specification[END_REF].

Dynamic linking and recursive bind ing of classes

The binding protocol itself is recursive since bind

Conclusion

We have presented a simple but comprehensive binding protocol for references to distributed shared objects. This protocol consists of one RPC from client to target, one up-call to the target object's accept bind, and one up-call to the language-support run-time new at the client's end. The latter up-call is directed by the data. returned by the former.

We have shown many examples of useful applica tions of the general protocol; by appropriate action in accept-bind and new, objects can select between many different distribution policies, e.g., data ship ping (caching) or function shipping (remote access).

Similarly, the protocol enables the language-support runtime to perform run-time type checking and/or loading of code efficiently and safely.

The efficiency of the protocol can be questioned, since it is based on unlimited recursive RPCs. How ever, the examples make it clear that in most cases, an optimistic implementation uses a single RPC, em ulating the binding protocols of systems such as RPC systems, SOS, Spring, or CORBA. However, our op timistic implementation is a.lso more versatile, since it automatically falls back on the pessi mistic approach when the static assumptions are false. It does this at the price of some local checking.

The work described is part of the Soul distributed object support system. Th•e reference system of Soul (SSP Chains) has been implemented; however it cur rently supports only a simplistic version of the binding protocol. At the time of this writing, the protocol and the examples are specified on paper only, but are we plan to integrate these ideas into Soul and check them out i n practice.

An extended ver$ion of thi3 paper, a$ well a$ related pa per$ are acce$$ible by anonymo-.s FTP on ho$t ftp.inria.fr, directory INRIA/Projects/SOR.

For

  instance, the Unix binding operation open takes a pathname and yields a file descriptor. It sets up an access chain consisting of the sequence: file descriptor number, file descriptor, memory-inode, cache blocks, disk block addresses, disk blocks. Thus the access chain is composed of a sequence of handles and ob jects, possibly of different kinds.

xFigure 1 :

 1 Figure 1: Fragmented object example. Client has ref erence to .Factory; at binding, factory initializes Cache, redirects client to Cache, redirects cache's reference to Replica. 1.

Figure 2 :

 2 Figure 2: Persistent object and remote access exam ples. When binding Client 1 's reference, Xd is copied to Xm, a.nd the reference redirected to Xm• When Client 2 binds, its reference is redirected to remote-invocation stub x,, itself bound to Xm•

  3We use the word factory differently from Meyer[START_REF] Meyer | Object-Oriented Software Con$tnsc tion[END_REF] for in stance. He use:s it for a class. We use it for the manager of a fragmented object instance, that decides in particular when to create new fragments within that FO. 'In this a.nd the following figures, the arrows represent ref erences, rounded boxes represent atoms, and thick lines delimit address spaces. The solid items exist initially; the dashed items appear during the execution of the binding protocol. A refer ence can be redirected, as in the case of the x reference in apace B, initially directed to X<f and later redirected to x.,.. x <i..,•• .. .....

  --: cache mgr -. Y. .......•.

Figure 3 :

 3 Figure 3: Cache manager example (pessimistic imple mentation). R ound 1: client binds file reference (la), yielding cache-aware proxy with continuation to server {1 b). Round 2: proxy instantiates empty cache Xm, passing file reference (2a); proxy binds to file {2b), passing reference to Xrn {2c); this yields stub x. con nected to cache (2d). Round 3: stub binds to cache, cache binds to file and i s initialized.

  ing a reference returns a class reference, which in turn must be bound before use. The first level of recursion ensures that th•e class of an object is loaded before creating instances of that class. A class manager class class loads new classes, i.e., reads the class code from a class repository, and dynamically links it into tbe client's address space. The recursion terminates there if the class manager is statically linked (this is the case in SOS for in stance [10]). If however multiple class managers were needed (for instance to support different object code formats) then the binding for a class-object would re turn the reference for the corresponding class-class ob ject, causing another level of recursion. Again, class references can use a specialized repre sentation, such as string name or registration number in the class repository, when there is no possible con fusion with other handles. Multiple representations can be distinguished from one another by recursion. Again there is a trade-off between flexibility and complexity. Dynamic linking can be avoided entirely if all classes are known statically. Or, dynamic linking can be supported, but under control of a statically linked class manager, class class.

  •Thia research waa supported in part by Esprit Ba.sic Re search Action BROADCAST 6370, and by a grant from Unix

	implement group policies, which in. turn support mi
	gration and persistent, replicated, or otherwise frag
	mented objects.
	Systems Laboratories.
	l

In what follows the word "object" is reserved for an appli cation object, as opposed to a handle.

Conce• ptually a type reference is the reference of a type ob ject, e.g., one that contains a description of the type. However, for this work, there is no obligation to keep type objects around at run time. The implementation of a type reference could just be a hash of its interface (as in SOS/C++[START_REF] Ga | Two exten sions to c++: A dynamic link editor and inner data[END_REF] ), a unique type identifier, or some other compact repreaentatio•n (more in Sec tion 7).

An object-oriented operating system -assessment and perspectives. Comp"ting Sy$tem$, 2(4):287-338, December 1989.

Acknowledgments

I wish to thank Paulo Amaral, Andrew Black and Jeff Chase for first raising some of the issues discussed in this paper. Mesaac Makpangou and Peter Dickman