UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Object properties: a mechanism for providing runtime services to objects in a distributed system Finkelstein, David 1994

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1994-0496.pdf [ 2.36MB ]
Metadata
JSON: 831-1.0052087.json
JSON-LD: 831-1.0052087-ld.json
RDF/XML (Pretty): 831-1.0052087-rdf.xml
RDF/JSON: 831-1.0052087-rdf.json
Turtle: 831-1.0052087-turtle.txt
N-Triples: 831-1.0052087-rdf-ntriples.txt
Original Record: 831-1.0052087-source.json
Full Text
831-1.0052087-fulltext.txt
Citation
831-1.0052087.ris

Full Text

Object Properties: A Mechanism for Providing RuntimeServices to Objects in a Distributed SystembyDavid FinkeisteinB.S. (Mathematical and Computational Sciences) Stanford University, 1986A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENT FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE STUDIESCOMPUTER SCIENCEWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAOctober 1994© David Finkelstein, 1994In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.Department of Cocu—r-2. cic JC.GThe University of British ColumbiaVancouver, CanadaDate QcçZ V2DE-6 (2/88)AbstractObject-oriented systems are increasingly used as a means to develop distributed applications.Objects provide a natural unit of encapsulation for remote data, and the system can makeremote invocations transparent to local users. Generally the underlying system provides avariety of services to objects in the system, such as persistence or concurrency control, whichare used by developers of distributed applications. There are problems with existing mechanisms for providing such services, however: they may require the programmer to design a different subclass of each user class for every service available, limit the choices of servicesavailable, or inhibit performance by providing services to all objects even when not everysevice is needed. The work in this thesis attempts to solve these problems through a newmechanism for providing services to objects called properties. Properties allow services to bedelivered transparently to objects on an as-requested basis. Additionally, a mechanism fordescribing inter-object relationships has been incorporated into the property scheme, allowingproperties to be used to provide complex services such as atomic transactions. Properties weredeveloped for the Raven distributed system and language developed in the Department ofComputer Science at the University of British Columbia.11Table of ContentsAbstract.iiTable of Contents iiiList of Figures vAcknowledgment viChapter 1 Introduction 11.1 The System Interface Problem 11.2 Providing Services in Object-oriented Systems 21.3 Thesis Statement 41.4 Outline 5Chapter 2 Design of the Object Property Scheme 72.1 Introduction to the Raven System 72.2 Property Scheme Design Goals 82.3 Selecting Services via Properties 122.4 Property Behavior Semantics 162.5 Assigning Properties to Instances 202.6 Inter-Object Relationships 222.7 Combining Properties 29Chapter 3 Implementation of the Object Property Scheme 313.1 Data Structures for Property Support 313.2 Providing System Services Through Properties 343.3 Dependent Invocations 373.4 Property Inheritance 423.5 Part-Of Clusters 473.6 Self-Invokes 513.7 Parallel Invocations and Property Support 533.8 User Properties 573.9 Status of the Implementation of Properties 59Chapter 4 Object Storage: Details of the Durable and Persistent Properties 604.1 Object Storage Overview 604.2 Storage Model 634.3 Implementation Details 674.4 Dependent Invocations on Storable Objects 764.5 Storage of Collection Class Objects 784.6 Object Name Service 80Chapter 5 Discussion and Future Work 815.1 Property Scheme Design 815.2 Implementation of Property Support 855.3 Object Storage 885.4 The.Raven Collection Classes 90111Chapter 6 Related Work 926.1 Object-oriented Systems 926.2 Sunnary 97Chapter 7 Conclusion 99Bibliography 101ivList of FiguresFIGURE 1. Assigning properties in the class definition 21FIGURE 2. Assigning properties by using pnew 22FIGURE 3. Class definition with instance variables showing inter-objectrelationships.23FIGURE 4. Some of the objects comprising a mail message, just prior to beingassigned to the MAIL MESSAGE object.26FIGURE 5. After assignment, objects have new properties and behaveaccordingly.27FIGURE 6. Object capability structure 32FIGURE 7. An Example of Recovering a Property Inheritance Assignment 44FIGURE 8. Objects in a Part-Of Cluster 48FIGURE 9. GID Structure 62FIGURE 10. Object Storage Model 63FIGURE 11. Storage Manager Role 64FIGURE 12. TDBM Manager Role 65FIGURE 13. Gifi Manager Role 66FIGURE 14. Format of encoded buffer in memory 68FIGURE 15. Format of a fully encoded object 71FIGURE 16. Formats of data storage on disk 73FIGURE 17. Format of struct STORAGE_INFO data structure 77FIGURE 18. Multiple Transactions Modifying a Single Object 82vAcknowledgmentFirst, I’d like to thank my family, especially my parents, for the support (both financial andotherwise) they’ve given me these past three years.I’d like to thank Don Acton and Terry Coatta, my Partners in Crime (or Raven, as it were) forall the assistance they’ve provided me, from simply kicking around ideas to help in trackingdown those elusive bugs. Without you two around, I had no other option but to graduatemyself. I’d also like to thank my supervisors, Norm Hutchinson and Gerald Neufeld, not simply because you’re supposed to do that sort of thing in your Acknowledgment, but for theguidance they’ve given me especially during those long meetings where I’d come up withstrange scenarios involving object relationships. Thanks also to those who helped during theredesign of Raven, by contributing their ideas and providing me with feedback on mine:Stephan Mueller, Raymond Ng, and Jim Thornton. And a special thanks to Steve Loving, whohelped encourage me in my dream to return to school.viCHAPTER 1 Introduction1.1 The System Interface ProblemComputer operating systems are designed to present a virtual machine to the programmers andusers of the computer. The operating system provides an interface through which applications canmake requests to and receive services from the operating system. For example, operating systemsusually provide a file service. By calling operating system routines, applications can find, read,and write files in the system. Many modern operating systems have a microkernel architecture,where the actual set of services provided by the operating system kernel itself are small. Instead,special servers provide the additional functionality of file service, networking, etc. Although theimplementation is different, the basic model presented to the programmer is the same as that provided by more monolithic operating systems.Unfortunately for developers of distributed systems, particularly systems designed formulti-threaded environments, the operating system interfaces can vary widely between different1CHAPTER 1 — Introduction 2operating systems. For example, the interface used by BSD Unix (or systems based on BSD Unix,such as SunOS) differs from that of Unix SVR4. Anyone who has attempted to port applicationsfrom one environment to the other can attest to the problems which can arise due to the differences in system calls. The interfaces to Mach and OS/2 are similarly incompatible with those ofthe other operating systems mentioned. These differences make the development of distributedapplications more difficult. Attempts have been made to create a standardized interface for Unixsystems. For example, many Unix systems support the POSIX application program interface [11],although most applications are still not written to this standard.Another mechanism for providing a standardized interface is to use an object-oriented environment. Object-oriented systems allow the applications programmers to use a standardized interface to the object system. Since objects interfaces provide strict, well-structured accesses to theobjects, they make a natural choice for providing the basis of a uniform system interface. It is necessary to port the object environment to each different platform, but once this has been accomplished, all user applications should be portable between platforms with a simple recompilation.Common object models have also been proposed and developed, primarily for the needs ofobject-oriented developers [14], [24].1.2 Providing Services in Object-oriented SystemsProgramming to a common object environment simplifies the development of applications in adistributed system. However, there remains the issue of exactly how user objects in the environment will receive system services. This is not a trivial question, as objects can require numerousservices ranging from persistence to concurrency control to recoverability.CHAPTER 1 — Introduction 3One mechanism is for the system to simply provide “system call” methods. In this scheme,object methods replace the system calls found in other operating systems such as Unix. This canbe accomplished in one of two different ways:(1) The system includes system objects which are responsible for providing services to user level objects. For example, objects which require concurrencycontrol can invoke methods on a object which coordinates locking (e.g., aLockManager object):LockNanager. lockMe(self);would ask the LockManager to lock the current object.(2) The system provides classes from which objects can inherit behaviors whichcorrespond to the services the object needs. For example, objects whichrequire persistence can inherit methods from a Storage class:self . storeMeToDisk ;would store the contents of the object to disk.One system which uses this technique is Arjuna ([23], see Section 6.1.2). This system callmechanism has the advantage that objects can be tailored to receive only those services they need.However, it suffers from a number of problems. First, it requires the programmer to manage theuse of the services. The programmer must invoke the appropriate methods to acquire and releaselocks, store the object to disk, etc. Although it’s not necessarily a bad thing to make programmersresponsible for managing the services they use, it does increase the likelihood of errors due to theprogrammer neglecting to release locks and from similar mistakes. This mechanism can also leadto the problem of class explosion: since the system provides multiple services, multiple versionsof each user class might be required [1].Another mechanism for providing services to objects in an object-oriented system is to provide a set of services automatically to all objects. In such a system, every object would be persistent, controlled against concurrent accesses, etc. This scheme has the advantage that theCHAPTER 1 — Introduction 4programmer doesn’t have to be concerned with managing the use of system services, they are provided transparently by the system. For example, the Guide system ([4}, see Section 6.1.6) provides persistence to every object in the system. The major drawback of this approach is a lack ofperformance. Since every object receives services, the system must devote time and resourcesupon every object invocation.Programmers and users ideally require a system which combines the best features of bothmechanisms described above. Users of classes need to create instances that can receive any combination of system services, yet class designers shouldn’t be required to include support for everypossible service a user might desire in the class implementation, nor should there need to exist different versions of each class for every combination of services available. Users also desire maximum performance, requiring that invocations on the objects in the system be as fast as possible.For example, users should be able to create String objects which persist, which are controlledagainst concurrent accesses, or possibly both, yet objects which do not receive services should notsuffer any undue performance penalty. Additionally, such a system should be complete enough tosupport distributed atomic transactions, a rigorous measure of the usability of a system.1.3 Thesis StatementAn object-oriented operating system can associate each system service with a property, which,when assigned to an object, indicates the object should receive the corresponding service. Theoperating system can determine which services to provide to an object by an examination of theobject’s property set. The research presented in this thesis attempts to show that:It is possible to identify and support a set of system services through object propertiessuch that:the semantics of the system services provided are independentfrom the others;CHAPTER 1 — Introduction 5• services are provided on an instance-by-instance basis;• services are provided automatically to an instance upon each invocation, without requiring any code in the class to use the service;• the set of services provided to an instance can change dynamically throughoutthe lifetime of the object;• the user can augment the set of services available;• inter-object relationships can be described, allowing the system to providecomplex services that span invocations on multiple objects;• the services available, together with inter-object relationships, is sufficientlycomplete to support distributed atomic transactions yet does not limit the system to support only such transactions.1.4 OutlineA description of the object property scheme, including semantics for each system supportedproperty, is found in Chapter 2. This chapter includes a general overview of Raven, the object-oriented operating system the property scheme was developed for, and discusses how the propertyscheme is used by Raven to provide services to objects. This chapter also discusses other aspectsof the property scheme, such as the various inter-object relationships that were developed.Details of the implementation of the property scheme are given in Chapter 3. This chapterdescribes how services are provided to objects via properties. Certain issues and problemsencountered during the implementation are also discussed.Chapter 4 describes the basic object storage service which was developed. It discusses thevarious issues confronted when designing the service, and provides details of the implementation.A discussion of additional issues, and the future work which can be done to address them,can be found in Chapter 5. Many of the issues discussed in this chapter did not become apparentuntil later stages of the implementation or during testing.CHAPTER 1 — Introduction 6Examples of other object-oriented systems, and the mechanisms they use for providing services to objects, are presented in Chapter 6.Conclusions are presented in Chapter 7. A list of the data structures used by the runtime system to support properties is given in Appendix A. Class definitions for the various classes whichwere developed or modified in the course of implementing this thesis are given in Appendix B.Design of the Object PropertyScheme2.1 Introduction to the Raven SystemThe object property scheme was developed for the Raven system. Raven consists of a programming language and a runtime system which together form an environment for exploring issuessurrounding distributed and parallel applications on both multiprocessor and distributed processorplatforms. The development of the Raven system is an on-going project in the Department ofComputer Science at the University of British Columbia. In addition to the work described in thisthesis, Raven has been primarily used to investigate issues in parallel and concurrentprogramming [3] and to explore issues in configuration management of distributed systems [7].The Raven language is an object-oriented language with a syntax similar to that of C. Thelanguage contains specialized constructs to directly support parallel execution of method invocations, some of which have repercussions for the various properties, as discussed in Section 3.7.The Raven runtime system provides support for objects written in the Raven language. Though7CHAPTER 2— Design of the Oblect Property Scheme 8the syntax of the language is stable, significant enhancements to the runtime system are continually being made.The complete Raven environment currently consists of a compiler, a class library, theruntime system, and a threads environment [161. The Raven system is not very reified: very littleof the runtime system, including the code that supports properties, is written in the Raven language itself. Instead, the bulk of the runtime system is written in C. Raven currently runs in itsthreads environment under Unix on Sun and MIPS workstations in a distributed environment.Raven is also running in a parallel environment under Mach 3.0 on a 20-processor Sequentmachine. A microkernel running on multiprocessor MC88 100 workstations is being developed tosupport the Raven system in a native environment [19]. A detailed overview of Raven, includinga description of the language semantics, can be found in [1].Each incarnation of the Raven environment is defined as a Raven World. Each Raven Worldhas a corresponding UDP port number on the machine it is running through which it communicates with other Worlds. A Raven World is uniquely identified by its host identifier and port number. Different Raven Worlds, even those on the same local machine, are normally isolated fromeach other until the Worlds are informed of each other’s existence.2.2 Property Scheme Design GoalsThe property scheme was designed with a number of goals in mind. The primary goal of thescheme is to provide a mechanism by which services can be provided transparently to objects onan instance-by-instance basis, in a flexible yet powerful way that does not limit the system or theprogrammer to a small set of possible services. The scheme was designed with each of the goalsoutlined below in mind.CHAPTER 2— Design of the Object Property Scheme 92.2.1 Orthogonality of Property SemanticsWhen properties are designed so that their semantics are independent from each other, the properties are defined to be orthogonal to one another. The necessary strictness of the semantics has significant impact on the implementation of properties: properties can be designed, developed, andtested separately, and then added to the system without any concern that they might cause sideeffects. This is true whether the property being added is new, or simply a new implementation ofan existing property.Orthogonality is primarily useful because it makes the semantics easier to understand. Theprogrammer doesn’t have to be concerned with any changes to the semantics due to propertyinteractions. When property semantics are independent, programmers can specify any combination of properties for an object with the knowledge that the object’s behavior with respect to eachproperty will always be correct. It is also an enabling feature; that is, when properties are orthogonal, it allows many other features to be included in the system, such as dynamic property assignment.2.2.2 Properties Assignable Dynamically to Any InstanceTo combat the problem of class explosion, the scheme was designed to allow properties to beassigned on a per-instance basis. In this way, sub-classes do not need to be created simply to gainthe benefit of additional property behaviors. By allowing objects to receive services on a perinstance basis, performance can be improved: objects can receive only those services which theyneed, and so suffer no performance overhead related to services (such as persistence or concurrency control) which they may not require.To further enhance the usefulness of the system, another goal of the design was to allowproperties to be assigned dynamically to objects, even after the object had been created. Sinceproperties are orthogonal, adding new properties to an object after instantiation can’t createCHAPTER 2— Design of the Object Property Scheme 10unwanted side-effects. Dynamic property assignment can be useful especially in a client-serversystem. Consider an object server which creates objects for use by various clients. Different clients may require objects with different sets of properties. With dynamic property assignment, theproperty set desired doesn’t need to be passed to the server. Also consider the situation where oneapplication creates an object, a second application wants to use the object, but the second application needs the object to have properties which weren’t required by the first application. For example, an object representing a block of text created by a text editor can be referenced by the body ofa mail message. Although the text editor may not have created the text object with the persistentproperty, the mail handler can ensure that the object is persistent by dynamically assigning it thatproperty.2.2.3 Transparency of UseTransparency implies that a programmer can implement classes without including special code touse properties. By placing all support for properties into the runtime system, the programmer isfreed from the responsibility of asking for system services each time they are needed. This declarative model has advantages over the procedural model. The possibility of program errors withregards to receiving services from the system is greatly reduced, since the programmer does nothave to be concerned with acquiring and releasing locks, writing object state to disk, etc., or determining when such events should occur. Additionally, even though the user of a class can assignany properties to instances of the class, the programmer doesn’t have to be concerned with supporting all the properties in the method code (an unrealistic expectation, especially given that theproperties available may change over time). This ties in well with orthogonality: a user of a classcan create an instance of that class with any desired set of properties, without worrying about sideeffects between the properties desired or between those desired by the user and any additionalproperties specified by the class designer.CHAPTER 2 — Design of the Oblect Property Scheme 112.2.4 Support for Atomic TransactionsOne primary goal of the system is for the property scheme to be powerful enough to supportatomic transactions. It was a further goal that this could be accomplished without having todevelop a special service devoted specifically to serializing invocations, but instead build theatomic transaction support using more general services.2.2.5 Additional Support for Distributed ComputingSupporting atomic transactions allows the development of distributed databases and other robustapplications. More simple applications, such as mail agents, do not require the same level of system support as a database. Other applications, such as name services, could benefit from systemservices which allow them to be highly available (e.g., some mechanism by which they could bereplicated). As the property scheme was being designed, one of the goals was to provide sufficientservices so that a wide variety of applications could be built. Additionally, the system needed tocontinue to support the experiments being conducted in the areas of concurrent programming andconfiguration management.2.26 User ExtensibilityTo this point, properties have been described as a means of providing system-supported servicesto objects. The logical extension of this design is to extend properties so they can be used to provide objects with user-supported services. Such an extension allows users to develop their ownservices without the need to modify the runtime system to support them. This is extremely important, because the system properties could never provide all the services desired by users. It alsoallows potentially new system services to be designed and tested at the user level before beingincorporated into the runtime system.CHAPTER 2— Design of the Object Property Scheme 122.3 Selecting Services via PropertiesEach of the goals enumerated above are important features for inclusion in Raven. To be trulyuseful, however, the properties should provide desirable behaviors when used in combination, andnot simply in isolation. On the surface, this goal may appear to be incompatible with the goal oforthogonality. However, useful behaviors can be viewed as being composed of other, simplerbehaviors. For example, an atomic invocation on an object requires recoverability, concurrencycontrol, and persistence of the object state. Atomic transactions involve invocations on multipleobjects and place additional requirements on the system, but it was a primary goal to design aproperty scheme that allowed atomic invocations to be performed by combining several properties together. If a new property had to be created for each desired behavior (e.g., if the systemneeded to support recoverability, concurrency control, persistence, and an “atomic invocation”property), then the number of properties could quickly grow to an unmanageable number (anundesirable property explosion, although growth would be linear and not exponential, as in classexplosion), with a corresponding increase in the likelihood that the property semantics could notbe designed in an orthogonal manner. For these reasons, considerable time was spent selecting theproperties and developing their semantics.The process of property selection began with an examination of a atomic transactions, to seeif they could be supported by composing several services together. Fundamentally, atomic transactions can be broken down into three components:• Serializability of invocations: If multiple transactions invoke methods on thesame objects, there must be some serial ordering of invocations so that to eachtransaction it appears that it has exclusive access to the objects for the durationof the transaction.• Recoverability: In the event of abnormal method termination (or possibly atthe user’s discretion) the system needs to be able to undo all the work that hasbeen done so far.CHAPTER 2— Design of the Object Property Scheme 13Persistence of data: Once a transaction commits, any changes that it performedmust be permanent.Attention was further focused to investigate the services which a single object would requirefor an atomic method invocation. Recoverability and persistence map directly as services requiredfor an atomic invocation. The single-invocation analogue for serializability is concurrency control: since Raven is multi-threaded, objects must be protected against concurrent accesses. Thisprovides a serial ordering of the invocations on the object. Consequently, the first three serviceschosen were concurrency control, recoverability, and persistence.The semantics of persistence which are required in order to support atomic transactionsmust include strong guarantees about writing the object state to storage: once the method invocation finishes, the object state must be updated before control is returned to the caller. Thesesemantics are necessarily very expensive to implement, since each invocation on a persistentobject could result in 110 traffic. For many applications, it would be an acceptable compromisebetween persistence and performance to delay writing the data to disk for a number of seconds sothe application can return from each invocation on a persistent object without blocking first.Machines and disks are generally reliable, so the chances of losing data by delaying the write asmall number of seconds is extremely small. Many modern file systems, such as LFS [20], willbuffer sequences of disk writes to memory in order to perform one larger disk write as opposed tomany smaller writes. For objects which are being frequently modified, buffering writes in memory and only updating the version in non-volatile storage periodically can provide a desirable performance improvement. For these reasons, the system needs to support two types of persistence:one which provides a strong guarantee about when object state is written to disk, and one whichprovides greater performance by delaying updates.In a distributed environment it is often advantageous to replicate data (such as name serviceinformation) on many different sites. This allows both an increase in performance (since clientsCHAPTER 2— Design of the Object Property Scheme 14can access servers which are the most local) and availability (since the system is not dependent onthe status of a single node). To support the development of highly available applications, a mechanism by which the system can make and maintain replicas of objects is required. Providingobject replication was therefore chosen as another system service to support through properties.To round out Raven’s support for distributed computing, two other system services werechosen. First, since Raven’s design allowed objects to be migrated between machines, somemechanism by which objects could be fixed to their current host (most likely their host of creation) was desired. Second, there are often objects which, once instantiated to a particular state,should not be modified. An example of such objects are those which comprise a mail message:once the message has been composed and sent, the objects should be considered to be “read only”and not modifiable. System support for creating immutable objects was therefore also desired.In all, seven system services were chosen for support: concurrency control, recoverability,persistence with both strong and weak guarantees about storage updates, replication, immobility,and immutability. Security was not chosen as a service to provide for several reasons. First, Ravenhas no notion of a user, simply of the local Raven World; this precludes the use of access controllists or other mechanisms which provide access to objects on a per user basis. Second, the implementation of Raven allows only one capability structure for each object; this precludes the use ofmultiple capabilities, each with potentially different access rights. Third, little thought had beengiven to security during the initial development of Raven. Developing a notion of security forRaven is beyond the scope of this thesis, so all issues involving system support of security wereleft unresolved.CHAPTER 2— Design of the Object Property Scheme 15To correspond to the services provided, seven properties were chosen:(1) Controlled(2) Recoverable(3) Durable(4) Persistent(5) Replicated(6) Immobile(7) ImmutableThe Durable property corresponds to persistence with a strong guarantee that object statewill be updated to storage, while the Persistent property corresponds to the weaker, more efficientnotion of persistence. To receive a service from the system, an object needs only to be given thecorresponding property.By default, objects are created “plain”, that is, without any properties. The Raven systemhandles plain objects in the following way:• The object exists only in RAM. Therefore, the object does not survive betweenreboots of the system.• No system control exists to prevent multiple threads from executing methodswithin the object simultaneously.• The object can migrate from machine to machine, either at the discretion of thesystem or when the object is explicitly asked to move itself.• Any changes made to the object’s instance data are immediately available andare not recoverable.For the vast majority of objects created and used in the system, these semantics should be allthat are needed. Most objects will be created for short-term use and will not require any specialCHAPTER 2— Design of the Oblect Property Scheme 16system properties. When an object is assigned one of the properties, the system handles the objectdifferently; it is provided with the service which is associated with that property.2.4 Property Behavior SemanticsOne of the first questions encountered when deciding upon the semantics of property behaviorwas deciding at what level the properties would operate: should property behavior be limited to asingle object invocation, or should it affect an entire invocation chain when the objects in thechain all have the same property? Each of these semantics has distinct advantages and limitations.Limiting the scope to a single invocation is a very convenient notion: properties can be describedby how they effect one object, and can be viewed from the perspective of a single object. Limitedscope is desirable in the general case for concurrency control: since locks are freed after eachinvocation, there is more concurrency and less potential for deadlock. However, it greatly complicates the issue of providing support for transactions, as a two-phase locking protocol cannot beused, and some other method must be used to enforce serializability. It would also require that thesystem be able to abort transactions at will: Consider a transaction Ti which invokes a method onobject 0. After the invocation, a second transaction T2 also invokes on object 0. If Ti aborts,then T2 must also be aborted. Extending the scope to encompass all invocations is desirable in thegeneral case for recoverability: if at some level the invocation can’t continue, all the work so farshould be aborted. If recovery simply restores the current object’s state, programmers maybecome loathe to program using many small objects and instead encapsulate data into larger units.But extending the scope can also lead to programmer confusion, since it can quickly becomeunclear exactly how far up the calling chain each of the properties may be propagated. Furthermore, extending the scope does not eliminate the problem of providing semantics conducive tocreating transactions.CHAPTER 2— Design of the Oblect Property Scheme 17The semantics decided upon came with the realization that there are two distinct concernsinvolved. The first involves objects and the system services they require, and the necessity to provide these services in a uniform manner. By viewing services from the point of view of the object,it becomes the natural choice to have limit the effects of properties to a single object invocation.The second concern is the understanding that objects are often placed in a relationship with eachother, so that what happens to one object is predicated on what happens to the other. To providefor this, the property scheme requires a mechanism for describing inter-object relationships thatallow the scope to be extended in the calling chain. This is described in Section 2.6.For each of the properties, the semantics of behavior are described below. Since propertiesare orthogonal, the system will handle any object with any one of these properties in the sameway, regardless of how many other properties the object has. Although it may appear on the surface that some of these properties are not orthogonal, that is not the case. Recoverable, Controlled, etc. provide only the semantics described, and do not attempt to provide more complexbehaviors, such as serialized access or atomic invocations.2.4.1 ControlledAn object given the Controlled property is protected against concurrent accesses by multiplethreads which may modify its instance data. Multiple readers, but only a single writer are allowedaccess to the instance data. Threads which cannot be granted the access they require (e.g., theywish to write to the instance data while someone else is reading) are blocked until the request canbe satisfied.2.4.2 RecoverableAn object given the Recoverable property has the “all-or-nothing” property. Only when a methodterminates normally are any changes made to the object’s instance variables made permanent. IfCHAPTER 2— Design of the Object Property Scheme 18the method terminates abnormally, the state of the instance variables is reset to the state they hadjust before the method started.The Raven programming language includes a restore statement. If the current object isRecoverable, executing a restore will restore the object’s instance variables to the state theywere in before the method started. If the object is not Recoverable the restore statement isignored. Execution continues with the next statement after the restore. Control is notreturned to the caller.2.4.3 DurableAn object given the Durable property has a copy placed in non-volatile storage (e.g., on disk).Any changes to the instance data of a Durable object are written to non-volatile storage before themethod returns control to the caller. Furthermore, the system ensures that the entire object state iswritten atomically—only consistent, complete objects are written. It would be disastrous if onlyhalf the object state were written to storage, since upon restart the object image loaded in wouldbe inconsistent. Return of control to the caller implies that the object state has been updated instorage. A Durable object’s capability also survives system failure or restart. These semantics arenecessary for the correct support of atomic transactions and database applications.2.4.4 PersistentThe Persistent property is similar to the Durable property, except that no guarantee is made as towhen the stored instance data will be updated. Although the in-RAM copy will be marked to bewritten to storage whenever a method modifies the object’s instance data, Persistent objects areonly written out periodically by the system to improve performance by reducing 110 traffic andincreasing parallelism. It is not guaranteed that the current state of the object will be in storage atthe time of a system failure, but the version in storage will be complete and consistent.CHAPTER 2— Design of the Object Property Scheme 19The semantics of Persistent are similar to those offered by the traditional Unix file systems,however Unix system semantics make no guarantee that the file will be written in a consistentstate (i.e., some dirty pages may get written while others may not).Although Durable and Persistent are very similar properties, the semantics of the two aredifferent. Orthogonality still holds: if an object is both Durable and Persistent it properly obeysboth semantics, since the semantics of Durable subsumes the semantics of Persistent. For mostapplications, such as mail agents, simple Persistence will be sufficient.2.4.5 ReplicatedAn object given the Replicated property can be replicated on different machines. The decision toreplicate is made by the runtime system in an effort to improve efficiency (for example, when anobject is heavily accessed by processes on two different machines). Replicated objects have weakconsistency: the system does not ensure that all copies of the object always have the same state.Replication is especially useful for improving performance and building highly available applications, such as name servers.2.4.6 ImmobileAn object given the Immobile property cannot be migrated between machines, and remains fixedon its current host. Immobility is desirable for objects which implement machine specific tasks,such as support for specialized devices or servers.2.4.7 ImmutableThe Immutable property prevents an object’s instance data from being changed. If a threadattempts to invoke a write method (i.e., a method which can modify the instance data) on anImmutable object, a runtime error is generated.CHAPTER 2— Design of the Object Property Scheme 20Properties take effect only after the object has been created and its instance variables havebeen initialized. This permits an object which is created with the Immutable property to bebrought into a usable state before the system prevents any accesses which could modify theinstance data.2.4.8 User-Defined PropertiesThe seven system properties described above are each implemented directly by the system.Although it is not possible for a programmer to modify the implementation of any of these properties, programmers can define semantics for and create implementations of their own properties.The user-defined properties are assignable in exactly the same ways as are system properties.User-defined properties, by their nature, can only affect data in user space; that is, theireffects are identical to invoking methods on objects. If the programmer defines several properties,it becomes the programmer’s responsibility to maintain the orthogonality of the properties.2.5 Assigning Properties to InstancesSince objects in the Raven system can have any combination of properties, a programmer needs tospecify which properties an object will have. The Raven language provides keywords for specifying the different properties:• Controlled property: controlled• Recoverable property: recoverable• Durable property: durable• Persistent property: persistent• Replicated property: replicated• Immobile property: immobile• Immutable property: immutableCHAPTER 2— Design of the Object Property Scheme 21• Test property: test_prop• User properties: u_prop_i, u_prop_2, u_prop_3, u_prop_4Object property specification can be done in two ways:(1) The class designer can specify that all instances of the class will have certainproperties. The class designer does not need to write any code to support theproperties, since they are all supported by the system.As an example, consider the code fragment from a class definition shown in Figure 1. Allinstances of the class HappyObjects would be given the Controlled and Recoverable properties.class HappyObjects controlled recoverable{somelnt : Int;behav doSome thing 0;}FIGURE 1. Assigning properties in the class definition.(2) At object creation time, the programmer can specify a list of properties forthe object. Objects in Raven are created using one of two different methods.The new method returns an instance of the class, which will have only thoseproperties specified by the class designer. The second creation method ispnew, which takes a list of additional properties to assign to the instance asone of its arguments.CHAPTER 2— Design of the Oblect Property Scheme 22Consider the code fragment shown in Figure 2, which shows an assignment to the instancevariable someObject. Since someObject is of class HappyObjects, it will have the Controlled andRecoverable properties, as well as the Persistent property and a user-defined property.behavior someBehavior{someObject = HappyObjects.pnew(persistent & U_prop_i,argi, ...);)FIGURE 2. Assigning properties by using pnew.Although the runtime system supports dynamic property removal (since it must be able toremove properties from an object when the object no longer inherits them) there is no syntax inthe programming language to allow programmers to dynamically remove properties from objects.2.6 Inter-Object RelationshipsAs described in Section 2.4, property semantics were developed by viewing properties asthey applied to a single level invocation on an object. But objects do not exist simply in isolation,and therefore some mechanism by which the relationships between objects can be described isnecessary in order to provide support for more complex behaviors like atomic transactions. Inaddition, to achieve the goal of dynamic property assignment, some mechanism must also exist byCHAPTER 2— Design of the Oblect Property Scheme 23which objects can be placed in some relationship that provides the dynamic assignment of properties from one object to the other. Towards these ends the Raven language was modified to providethree methods of describing relationships between objects: Dependent references, Inherits references, and Part-Of references. When the designer of a class wishes to describe an inter-objectrelationship, a class instance variable can be marked as either dependent, inherits, orpartof. Consider the class definition shown in Figure 3. In this example, firstlnstanceVar is a Dependent reference, secondlnstanceVar is an Inherits reference, and thirdlnstanceVar is a Part-Of reference.class ExampleClass{aFirstlnstance : cap dependent;aSecondlnstance cap inherits;aThirdlnstance : cap partof;)FIGURE 3. Class definition with instance variables showing inter-object relationships.2.6.1 Dependent ReferencesDependent references are the tool by which the scope of a property is extended beyond a singleinvocation to encompass a calling chain. A Dependent reference is defined as follows. When anobject P has a reference to another object C which is marked dependent (they can be thoughtCHAPTER 2— Design of the Object Property Scheme 24of as Parent and Child objects), C is said to be Dependent on P. The dependency refers to property dependency: the properties of the child are dependent on those of the parent. When the parentinvokes a method on the child, state information associated with the properties is passed upwardsto the parent when the method returns. Any actions that would normally be taken before the returnfrom the child become dependent upon the parent.Dependency has meaning only for properties; as such, it does not affect plain objects. In thecurrent design of Raven, the semantics for Dependent references affect only the Controlled,Recoverable, and Durable properties. It makes little sense to speak of “Dependent Immutable” or“Dependent Immobile”, although some semantics for these situations could be contrived; also,since Replicated only provides weak consistency and Persistent makes no guarantees as to wheninstance data will be written to storage, no semantics for Dependent Replicated or Dependent Persistent have currently been devised.As examples of how Dependency works, consider the following situations, where the objectP has a Dependent reference to an object C, and P invokes a method on C:• If P and C are both Controlled, then the access privileges (read or write privileges) associated with the invocation on C are retained by the thread whichmade the invocation and are passed back to P Other threads are still blockedfrom accessing C. Since the thread now in P still holds access privileges, it canmake subsequent invocations on C with impunity (assuming that the accessrights held are sufficient for the invocations—if the initial invocation onlyrequired read privileges, the first future invocation that requires write privileges will block if other readers are present). The thread relinquishes control ofthe object C when its invocation on P returns, at which time the thread’s control of P is also relinquished.• If P and C are both Recoverable, then any changes made to C are not committed until the changes made to Pare committed (i.e., the invocation on P returnsnormally). If P returns abnormally, or an restore statement is executed, thenCHAPTER 2— Design of the Object Property Scheme 25both P and C are restored to the states they were in before the invocation on Pbegan.• If P and C are both Durable, then any changes made to C are not written todisk until the changes made to P are written. The invocation on P will notreturn until both P and C have been written. Since the Durable propertyassures that objects are written in their entirety, it is guaranteed that both P andC will be written in an atomic fashion.If P is a dependent child of a third object G, then the state information for the properties ofC and P are passed to G. State information about a property is kept by the thread, and passedback from a child to a parent until the top level of the Dependent chain is reached. Raven placesno limit on the number of Dependent references that may exist to an object.2.6.2 Property InheritanceSection 2.5 described how properties are assigned at the time of object creation. An additionalway in which an object can receive properties is dynamically at runtime through property inheritance. When an object is assigned to an instance variable which has been marked inherits, theobject is then assigned all the properties of the object holding the reference. Since the object beingassigned can also have instance variables which are marked as inherits, the runtime systemmust compute the transitive closure of all the references which are marked inherits andupdate the properties of all the objects so referenced. The complete set of properties of an objectare those assigned at creation time plus those it inherits from another object. In the current designof Raven, an object can inherit properties from at most one other object, and there is no way to“mask out” certain properties, i.e., to specify that an object should not inherit a property dynamically. The design also does not include a mechanism by which objects can be prevented fromacquiring properties dynamically, nor a mechanism by which the class designer can specify thatinstances of the class should never be given certain properties.CHAPTER 2— Design of the Object Property Scheme 26SETProperties: [None]Item: <Inherits>Item: <Inherits>Item: <Inherits>..___ø.FIGURE 4. Some of the objects comprising a mail message, justprior to being assigned to the MAIL MESSAGEAs an example of the use of property inheritance, consider a mail message. All the objectswhich make up the mail message (e.g. the To: and Subj ect: fields) need to be Persistent.However, it is sufficient to simply create the main mail message object as Persistent, and haveeach of the sub-objects inherit Persistence from the main object. The advantage of such a schemeis obvious when you consider that objects that comprise the mail message, such as Sets or Strings,may have been created by other applications (such as an editor) and may not have been createdwith the Persistent property. (See Figure 4 and Figure 5.)The ability to dynamically assign properties to an object is important in client-server systems where servers create objects for use by different clients. With dynamically assignable properties, clients can be assured that the objects they use will have those properties they need. Thebehavior of the object can be specified by the user of the object, and the creator need not know inadvance which properties to assign.STRINGProperties: [None]“acton@cs.ubc.ca’MAIL MESSAGEProperties: PersistentTo: <Inherits>Subject: <Inherits>STRINGProperties: [Nonelcoatta@cs.ubc.ca’STRINGProperties: [None]“Meeting Today”STRINGProperties: [None]“davef@cs.ubc.ca”CHAPTER 2— Design of the Object Property Scheme 27FIGURE 5. After assignment, objects have new properties andbehave accordingly.Property inheritance should in no way be confused with the traditional notion of inheritancewhich describes the inheritance of methods and behaviors by one class from another. Propertyinheritance is a relationship between two objects, indicating that additional system servicesshould be bequeathed to an object. Objects can inherit properties from other objects of any class.2.6.3 Part-Of ReferencesDependency describes a relation between objects which affects how the system handles objectswith properties. In object-oriented systems, objects are often bound closely together. Consideragain a mail message object. The mail message is composed of many other objects: a From:field, a To: field, etc., each of which are themselves often composed of many other objects—e.g.,the To: field could be a Set or a List or just a simple String object. In such circumstances, thesub-objects make little sense in an isolated context. They are intrinsically part of the mail messageobject. This relationship goes beyond simple Dependency; the objects are tightly coupled togetherrSETProperties: PersistentItem: <Inherits>Item: <Inherits>Item: <Inherits>MAIL MESSAGE /Properties: PersistyY”To: <Inherits>Subject: <Inherits>STRINGProperties: Persistent“acton@cs.ubc.ca”/NSTRING“coatta@cs.ubc.ca”ISTRINGProperties: Persistent“Meeting Today”STRINGProperties: Persistent“davef@cs.ubc.ca”CHAPTER 2— Design of the Object Property Scheme 28by the relationship the programmer has created between them. To describe such a relationshipbetween objects, Raven allows class instance variables to be marked partof.By specifying a reference as partof, the reference is considered to be marked as bothinherits and dependent. For the programmer, there is no semantic difference betweenspecifying a reference as partof and specifying it as both inherits and dependent.The system interprets Part-Of to imply a tight coupling between the objects. As such, theRaven runtime system can make special use of Part-Of relationships. Consider a chain of objects,A—>B--->C, where C is Part-Of B and B is Part-Of A. Together, A, B, and C can be viewed as asingle cluster by the Raven system. Since the objects in a cluster are tightly coupled, object clusters can be used by the Raven system in a variety of ways:• Object clusters can be written to disk as a single unit, even if they are not contiguous in memory. Similarly, when the root object of an object cluster isloaded in from disk, the entire cluster is loaded, since it is probable that manyof the objects in the cluster will soon be needed.• Object clusters can be migrated together between machines. Simply migratingthe root object of a cluster would be inefficient, since any invocations by thecluster root object on other objects in the cluster will either have to be remote(i.e., across machine boundaries), or cause additional object migrations (withtheir associated overhead).Clusters are an efficiency mechanism for the runtime system and do not alter the semanticsfor the programmer. Because objects can inherit properties from at most one other object, anobject can be Part-Of at most one other object. The Raven system does not limit the number ofreferences that can exist to an object that is Part-Of another.As a possible use of Part-Of, consider again the mail message objects of Figure 4, only thistime with instance variables marked partof instead of inherits. Performance would sufferCHAPTER 2— Design of the Object Property Scheme 29greatly if the system only loaded in the root object from disk when the mail message wasaccessed, or only migrated the root object to another machine; in a very short time, the otherpieces of the object will need to be accessed. By logically clustering the objects together the overall performance of the system can be improved.It should be emphasized that Part-Of is used by the runtime to provides performance optimizations only, and is otherwise no different than specifying inherits and dependent.2.7 Combining PropertiesSince properties in the Raven system are orthogonal, they can be easily combined. No side effectsresult from adding properties to objects; instead, the system simply provides the new functionalityof the added property. Properties can be combined to produce the exact behavior required, whileinvocations on the object do not incur any overhead for system services not used.Although many objects will have only a single property (e.g. Controlled or Persistent), morecomplex applications and objects require several properties. One natural pairing is Immutable andReplicated. Since an linmutable object cannot be modified, it can be replicated on many machines(or even in several places on the same machine) without any concern for maintaining consistencybetween copies.Different applications will require different pairings of properties. Consider a name service.The name service must support concurrent lookups by multiple users, provide a facility for addingand removing names, while maintaining the integrity of the service across system reboots. Theobjects which comprise the name server need to be both Controlled and Persistent, otherwise thename server will not function properly.CHAPTER 2— Design of the Object Property Scheme 302.7.1 Supporting Atomic TransactionsMore complex systems require more properties. By combining Raven properties and placingobjects in a Dependent relationship, it is possible to create database systems which support atomictransactions. Objects in the database need to be Controlled, Recoverable, and Durable. By puttingthe objects in a Dependent relationship, the invoking thread has exclusive access to the objectsuntil the transaction returns, as the thread will retain all the concurrency control locks for theobjects touched. New locks can be acquired, but old locks will not be released until the top levelinvocation returns. This behavior is analogous to a two-phase locking protocol, and therefore provides the serializability required for atomic transactions. Since the objects are Recoverable, anyabnormal termination or if a restore statement is executed will restore the state of all theobjects touched to the values they had before the transaction began. Finally, the new state of allthe objects will be written to storage at the same time, in an atomic fashion, prior to the returnfrom the top level invocation. As such, in the event of a system failure, either all the objects areupdated in storage, or none of them are.CHAPTER 3 Implementation of the ObjectProperty SchemeIn order to test the ideas developed in the previous chapter, core features of the property schemewere implemented and integrated into the Raven runtime system.3.1 Data Structures for Property SupportAn object in Raven is referenced using a capability pointer to the object. These pointers are normal 32-bit integer pointers to memory. Capability pointers point to a block of memory which contains a capability structure. These structures contain the data, or pointers to the data, used by theruntime system for the management of the object, as well as a pointer to a block of memory whichcontains the object’s actual instance data. The capability structure is shown in Figure 6.An object’s property set is stored as an integer value inside the capability structure. This 32-bit value is divided into two 16-bit words. The first word is used to store the set of properties theobject was assigned at creation, while the second stores the currently inherited properties. This31CHAPTER 3—Implementation of the Object Property Scheme 32struct capabilityfuncptr invoke;cap id;cap is_a;cap parent;cap inh_root;cap storage_manager;method_type method_type_to_use;struct gid *gid;voidp rw_lockvoidp cluster_lock;properties obj ect_properties;u_char *data;invoke: Pointer to the invocation function to useid: Pointer to this structure, for sanity checkingis_a: Capability of class object which we are an instance ofparent: Capability of object we inherit properties frominh_root: Root object of inheritance treestorage_manager: Capability of object which manages our storagemethod_type_to_use: Indicates if a remote invocation is neededgid: Pointer to object global identifierrw_lock: Pointer to object concurrency control lockcluster_lock: Pointer to object cluster lockobject_properties: Object property setdata: Pointer to object instance dataFIGURE 6. Object capability structure.design limits the number of properties that the system can support to 16—each bit position indicates whether the object has a particular property or not. In addition to the seven system propertiesand the four user properties, Raven provides a “test” property that was used extensively during thetesting of property inheritance and dependent invocations. The test property can also be used asthe basis for testing new system properties before modifying the compiler and the runtime systemCHAPTER 3— Implementation of the Object Property Scheme 33to support the new property name. In total 12 bits of each word are accounted for, allowing up tofour more to be added before these fields would need to be widened.As described in Section 2.5, a programmer can specify new properties for an instance byproviding a list of properties as an argument to the pnew method. It is a natural convention to listthese properties using an “&“ operator, as in pnew (prop & prop & prop. . . ) : when a programmer wants an object to have “concurrency control and recoverability” it can simply be written as “controlled & recoverable”. To facilitate this, each of the Raven properties isrepresented as a bitmask of all is, with a 0 in the position corresponding to that property. Theobjects property mask is then created by performing a bitwise-and of the properties the object wasgiven. If an object is created with a particular property, it will have a 0 in the corresponding position of the first word of its property mask; if it inherits a property, it will have a 0 in the corresponding position of the second word of its property mask. By storing properties as bitmasks, theruntime system can easily detect when an object has a particular property. The bitmasks are givenin Appendix A.2. Simple macros have been written to test and set the appropriate bit positions foreach of the properties.The other pieces of the capability structure used by the runtime system to support propertiesare:• The parent capability: Points to the capability structure of the object fromwhich properties are inherited. If no properties are currently being inherited,this value points to the nil object.• The inh_root capability: Points to the root object of the property inheritancetree. Note that not all inherited properties may be from the root object; somemay be from an intermediate object.• The storage_manager capability: Points to the object which manages thestorage of this object to disk (see Chapter 4).CHAPTER 3— Implementation of the Object Property Scheme 34• The gid pointer: Points to a data structure containing the object’s globallyunique identifier (see Chapter 4).• The rw_lock pointer: Points to a lock data structure used for concurrencycontrol, or NULL if the object is not Controlled.• The cluster_lock pointer: Points to a lock data structure used for Part-Ofcluster locking (see Section 3.5).3.2 Providing System Services Through PropertiesThe purpose of properties is to allow system services to be provided transparently to objects. Services are provided whenever a method is invoked on an object. To accomplish this, the runtimesystem uses a series of pre- and post-invocation functions, with one set of functions for each ofthe properties. Immediately prior to the method invocation, the property set of the object is examined. For each property the object has, the appropriate pre-invocation function (termed a pre-handier) is executed. When the necessary pre-handlers have been executed, the method code itself isexecuted. After the method returns, prior to returning control to the calling object, the appropriatepost-handlers are executed.The order in which the pre- and post-handlers are executed is very important to ensure correctness. For example, it is necessary that locks not be released until after the Durable and Recoverable post-handlers have executed, since these functions may need to read or write the instancedata of the object; it would be disastrous if another thread began modifying the object’s instancedata while the Durable post-handler was attempting to write the data to disk. Correctness placesseveral restraints on the ordering that can be used, the primary one being that concurrency controllocks must be acquired before any other work is done and released only after all other work is finished. Correctness also requires that the Recovery post-handler execute first, since it may restorethe object state. They system must not propagate an incorrect state to replicas of the object, orstore an incorrect state to disk.CHAPTER 3—Implementation of the Object Property Scheme 35The current ordering of the pre-handlers is as follows:(1) Controlled(2) Durable(3) Persistent(4) Replicated(5) Test property(6) Recoverable(7) User properties (u_prop_i through u_prop_4)The post-handler order is the exact inverse of the pre-handler order.There are no pre- and post-handlers for the Immutable and Immobile properties. To supportthe Immutable property, the runtime system checks the method type just prior to executing theControlled pre-handler. If the method is a write method (i.e., if it modifies the object’s instancedata), then a runtime error is generated. The determination of the method type is done by theRaven compiler through an analysis of the statements in the method. Although the compiler canbe fooled and generate an incorrect method type, and some invocations of write methods may notin fact modify the instance data, this implementation is extremely simple, and provides a reasonable implementation. The Raven runtime system does not currently implement object migration,and as such, the Immobile property is not used. However, when migration is implemented, immobility will still not need a pre- or post-handler, as it will simply be checked for just prior to objectmigration.Since the property set of an object can change dynamically, it’s possible for one thread to bereading the property set as it begins an invocation while a second thread is modifying the propertyset as the result of its own invocation. This problem is addressed by several features of the runtime. First, the property set is stored as an integer value. It can be assumed that the hardware canCHAPTER 3—Implementation of the Object Property Scheme 36read and write integer values to memory atomically; as such, a thread reading the property set willnot see a partially updated property set that is being written by another thread. Second, a threadmust have the object’s concurrency control lock in order to modify the property set; if no lockexists, then that thread can be assumed to have exclusive access to the object. Since the concurrency control lock is acquired before any work is done (even work required by the other properties), it can be assumed that the property set of an object will remain stable for a thread after it isgranted the lock (unless the thread modifies the property set itself). If the property set waschanged while threads are waiting to he granted the object’s concurrency control lock, they arerestarted, object immutability is rechecked, and the threads once again begin the process of executing the pre-handlers.One alternative to using a careful ordering of the pre- and post-handlers is to have the handlers executed atomically—that is, require that no other threads be allowed to execute while onethread is inside the set of pre- or post-handlers. Using a careful ordering provides better performance, but it also precludes the use of user-defined properties for providing alternate forms ofsome of the system services, particularly concurrency control, since no ordering could allow bothsystem-supported concurrency control and user-supported concurrency control to be the first prehandler executed. However, if the handlers were executed atomically, some mechanism wouldstill be required to deal with the problem of dynamically changing property sets, and potentiallyundoing work done in a pre-handler for a property which the object will not have when themethod is actually executed.An examination of the pre- and post-handlers helps demonstrate the orthogonality of theproperties. The handler code for each of the implemented properties makes no references to anyother property, nor does the code access data structures used by the pre- and post-handlers of theother properties. The exception to this rule is the handlers for the Durable and Persistent properties, which perform almost identical tasks. Although separate implementations could have beenCHAPTER 3—Implementation of the Obfect Property Scheme 37made, it would have required an almost complete duplication of the existing data structures andcode. It was therefore decided to combine the implementations and allow them to share data structures and supporting objects (see Chapter 4).3.3 Dependent InvocationsWhenever a method is invoked on an object which is referenced via an instance variable whichhas been marked dependent, the runtime system must keep track of state information associated with the properties. This is accomplished by maintaining this state information in the thread.Currently, the runtime system uses the thread to thread keep track of information for the Controlled, Recoverable, Persistent, and Durable properties; these properties therefore supportDependent invocations. Each thread has associated with it a corresponding thread object (aninstance of the Raven Thread class). Thread objects include among their instance variables thefollowing:• session_chain: An integer value which is used by the runtime system as apointer to a list of lock structures currently held by the thread.• lock_depth: The integer value of the current depth in the invocation chain,starting at the top-most Controlled object and counting only Controlled objectsin the chain, lock_depth is basically the count of the number of locks heldby the thread.• shadows: An integer value which is used by the runtime system as a pointerto a list of object shadow copies, i.e., copies of object instance data. Theseshadow copies are created for Recoverable objects and are used to restoreobject state.• cal lDepth: The integer value of the current depth in the invocation chain,starting at the top-most Recoverable object and counting only Recoverableobjects in the chain.CHAPTER 3—Implementation of the Object Property Scheme 38• function_chain: An integer value which is used by the runtime system asa pointer to a list of functions that need to be executed at some later time. Theuse of function_chain is discussed in Section 3.4.1 and Section 3.5.3.• storage_chain: An integer value which is used by the runtime system asa pointer to a list of objects which need to be written to storage. storage_chain is discussed in Section 4.4.Each Dependent invocation has associated with it a corresponding identifier. A chain ofDependent invocations all use the same identifier, which is set to the id (integer value of thecapability pointer) of the root object of the Dependent chain.When an invocation is made in Raven, a parameter structure is passed to the invoke routine.This parameter structure contains data used in the course of the invocation, such as the methodname, and the actual parameters used by the method. These parameter structures are pushed ontoand popped off of the C-level stack with each invocation. The runtime system can examine thecurrent parameter structure for its current invocation, or trace upwards through the parameterstructures for previous invocations. The parameter structure contains a boolean flag, dependent Invoke, that indicates if the current invoke is Dependent or not. The Raven compilerchecks each invocation to see if the invokee is Dependent upon the invoker; if so, the compileremits code to set this flag to TRUE (a predefined boolean value used by the runtime). This allowsthe runtime system to know when a Dependent invoke is occurring. Details about invocations inRaven, including the use of parameter structures, can be found in [1].The parameter structure contains another flag, isDependentRoot, which is normally setto FALSE, as well as an integer field for the Dependent invocation identifier, dependent ID.When the runtime finds the dependent Invoke flag set, it examines the parameter structure forthe previous invocation. If this structure has a non-zero value for its dependentlD, this value isused as the Dependent invoke identifier of the current invocation. If this value is zero, then theCHAPTER 3—Implementation of the Object Property Scheme 39invoker must be the root object of the Dependent invocation. The isDependentRoot flag isset to TRUE in the invoker’s parameter structure, and the local dependent ID is set to the Id ofthe invoker.Normally, post-handlers are executed only for properties which an object has. However, it ispossible that the root object of a Dependent invocation chain does not have the Controlled,Recoverable, or Durable properties, yet objects with these properties were invoked somewhere inthe chain. The post-handlers for these properties must therefore be executed when the invocationon the root object has completed. If the isDependentRoot flag is set, these post-handlers areexecuted. The post-handlers check the value of this flag, and perform the necessary work ifDependent invocations were made on objects with the corresponding property (see Section 3.3.1,Section 3.3.2, and Section 4.4).A Dependent invocation chain only includes objects which are Dependent upon their callers. If an invocation is made on a non-Dependent object, then any further invocations made fromthat object will be part of a new, separate Dependent chain. For example, consider a chain of invocations, A—>B--->C--*D-—*E, where E is Dependent on D and B is Dependent on A. Both the invocation on A and on D are considered to be roots of Dependent invocations, and will have theirisDependentRoot flags set. Properties which support Dependency need to keep track of theId of the current Dependent chain, to ensure that the post-handler does not do work prematurely:using the above example, when the invocation on 0 terminates the Durable post-handler needs towrite 0 and E to storage, but not A and B.3.3.1 Dependent Invocations on Controlled ObjectsEach invocation on a Controlled object has an associated lock depth, which is basically a count ofthe number of locks the thread currently holds. An initial invocation on a Controlled object has alock depth of one; an invocation it makes on a Controlled object would have a lock depth of two,CHAPTER 3—Implementation of the Object Property Scheme 40etc. The lock depth is unaffected by invocations made on objects which do not have locks: if Ainvokes on B which invokes on C, and only A and C are Controlled, the lock depth of the invocation on C will be two. The locks held by the thread are kept in a list referenced by thesession_chain instance variable of the thread object. To support Dependent invocations, thelock information data structure described in [1] was augmented to include a field for the value ofthe current Dependent invocation identifier; this field is also called dependent ID. The value ofthis field is set by the Controlled pre-handler to the current value of dependent ID found in theparameter structure.When a method terminates, the post-handler checks the dependent Invoke flag. If it isset, then the handler simply returns without releasing any locks; if not, then locks are released upto the current lock depth. If the isDependentRoot flag is set, then the post-handler mustrelease all locks that were acquired during the Dependent invocations. If the current object is Controlled, all locks with a lock depth greater than the current depth are released, since all the locksacquired after the current lock will have a lock depth greater than the current lock depth. If however the current object is not Controlled, then the session_chain is traversed starting fromthe most recently granted lock. If the dependentlD of the lock information structure is equal tothe id of the current object, the lock is released, and the next lock in the chain is examined. Thisprocess continues until no locks remain in the chain, or a lock information structure has adependent ID not equal to the id of the current object.3.3.2 Dependent Invocations on Recoverable ObjectsWhen Recoverable objects are part of a Dependent calling chain, the shadow copies of theobjects’ instance data must be retained by the thread until the top level invocation in the Dependent chain terminates. The thread also keeps track of the current depth in the invocation chainusing the instance variable cal lDepth.CHAPTER 3—Implementation of the Object Property Scheme 41Each time an invocation is made on a Recoverable object within a Dependent calling chain,a shadow copy of the object is made and placed on the shadows list kept by the thread. The current value of the callDepth is then set for this invocation, and stored with the shadow. Whenthe top level invocation terminates, the shadow copies are simply discarded, as they are no longerneeded. However, if a res tore statement is encountered, then the list of shadows is traversedand all objects whose shadows have a higher call depth than that of the current object have theirinstance data restored to the value of the shadow, and these shadows are removed from theshadow list.3.3.3 Remote Dependent InvocationsEach time a remote invocation is made in Raven, a worker thread is created on the remotemachine to execute the method code [1]. Normally, this thread is destroyed after the method finishes executing. However, since property state information is kept in the thread, remote Dependent invocations must be treated in a special manner. Additional problems arise due to the natureof the implementation of properties: since most of the data structures used are regular C structuresand pointers, references to the state information cannot be easily passed back to the originalmachine. Propagating the state data back can be expensive, and troublesome to maintain, aschanges are made to the data structures or support for Dependency is added to additional properties. To address these concerns the following solution to the problem of remote Dependent invocations was adopted.Every remote invocation now includes an additional integer parameter in which the ID ofthe current Dependent calling chain is passed (or zero if the invocation is not Dependent). Apotential problem can occur, however, since Dependent IDs are just the location in memory of theroot object of the Dependent chain, and there may be an object at that location on the remotemachine which gets invoked as part of the remote invocation. Therefore, the actual ID passed is(<real Dependent ID> 1), as no object could ever reside at an odd memory address.CHAPTER 3—Implementation of the Object Property Scheme 42When the remote thread finishes execution of a Dependent invocation, in addition to any returnvalue it also passes back the globally unique ID (GID, see 4.1.1) corresponding to the Threadobject of the remote thread. The remote thread then suspends itself, so the Thread object and itsassociated data structures are not destroyed.The gid of the remote Thread object is stored with the state information for each propertyin the local thread. When the invocation on the root object of the Dependent invocation chain finishes, the property post-handlers are executed. As the post-handlers traverse their state data, if areference to a remote Thread object is encountered then a remote invocation is made on thatobject (see Appendix B. 1). The remote worker which is created does not awaken the original, suspended worker; instead, it simply uses the worker’s instance data to perform the appropriate worknecessary for the specific post-handler. This is possible because all remote worker threads of anoriginal thread have the same session identifier as the original thread, and this session identifier issupposed to be unique for all threads in the system. Once all the post-handlers have executed, theoriginal worker is awakened and is then destroyed.Currently, the system stores the remote Thread object gid in the state information ofevery property, even if no objects with that property were invoked upon by the remote thread.Therefore, remote Dependent invocations will require one additional remote invocation for everyproperty which supports Dependency.3.4 Property InheritanceIn the general case, supporting property inheritance is fairly straightforward. The Raven compilerdetects any assignments which are made to a class instance variable which is marked with theinherits keyword, and emits code to call a special runtime routine, UpdatelnheritsQ,which does the work of “disinheriting” properties from the old object which had been referencedCHAPTER 3—Implementation of the Object Property Scheme 43by the instance variable and “bequeathing” properties to the new object assigned to the instancevariable.The basic steps taken in disinheriting properties from and bequeathing properties to a targetobject (i.e., an object which has been de-assigned from or assigned to an instance variable whichprovides property inheritance) are the same. When bequeathing properties, two additional stepsmust be taken: first, the system must ensure that the target object is in the same Raven World asthe bequeathing object; and second, the system must check to see that a property inheritance cycleis not being created, by checking to see if the target object is the root object from which thebequeathing object inherits properties.The system first computes the transitive closure of all objects which inherit properties fromthe target object. These objects are then locked to prevent any concurrent accesses to them whiletheir properties are being updated. Next, the property mask maintained in each object’s capabilitystructure (see Figure 6) is recomputed, and any work associated with the gaining or losing ofproperties (e.g., creating or destroying locks used by the Controlled property) is performed. Thevalue of inh_root stored in each object’s capability structure is also updated accordingly. Thispointer points to the root object of the property inheritance tree; an object which no longer inheritsany properties has its inh_root set to point to itself. The value of the parent pointer for thetarget object must also be updated; this is either the object from which properties are directlyinherited, or nil if no properties are inherited. Finally, the locks on the objects are released.Currently, the system does not do any performance optimizations, such as checking to see ifdisinheriting or bequeathing properties actually affects the property sets of all the objects in thetransitive closure, and then omitting the unaffected objects from the set of objects that need tohave their property masks updated.CHAPTER 3—Implementation of the Object Property Scheme 443.4.1 Recovering Property Inheritance AssignmentsAlthough providing property inheritance is straightforward in the general case, it becomes muchmore complicated when the assignment which provided property inheritance can be recovered.Consider the example shown in Figure 7, where anlnstance provides property inheritance.behavior doSomething (){if (anlnstance == oldObject)anlnstance = newObject;restore;}FIGURE 7. An Example of Recovering a Property Inheritance Assignment.The original object (oldObj ect) which had been referenced by anlnstance and all objectswhich inherit properties from oldObj ect will have their property masks changed, and newObj ect and all objects which inherit from newObj ect will have their property masks changed.Furthermore, these objects must behave as if they have (or don’t have) the appropriate properties;if newObj ect was uncontrolled before, but has the Controlled property now, it must be given alock. However, once the restore statement is executed, all the work which was done to disinheritoldObj ect and bequeath properties to newObj ect must be undone. Since the data structuresCHAPTER 3— Implementation of the Object Property Scheme 45used by the runtime system to support properties are mostly C structures, and since the propertyinformation is stored in the capability structure and not in the object instance data itself, theshadow structures used by the Recoverable property cannot be used to recover all the state thatexisted prior to the method invocation.To solve this problem, recoverable assignments which provide property inheritance aretreated in a special way. When the assignment is made, only the minimal amount of work necessary to provide correct functionality is performed, and the remaining work is delayed until recoverable invocation terminates normally (or, in the case of a Dependent invocation on a Recoverableobject, when the top-level invocation returns). This minimal amount of work involves modifyingthe property masks, and creating the data structures needed for any properties newly inherited byan object (e.g., creating locks for newly Controlled objects), but does not include destroying thedata structures used by properties for any objects which were disinherited. Therefore, the locks,storage managers, shadow copies, etc. of objects which have been disinherited will be retained.Furthermore, the objects in the transitive closures will remain locked until the status of the invocation has been determined, as the objects must be protected against concurrent accesses throughout the time that their property sets might change.One of two scenarios will now occur: either the invocation will terminate normally, or will itwill be rolled back. After the minimal work described above is performed, a special function isqueued up to be executed when it is known which of these two situations has occurred. This function is added to a list of similar functions kept by the Thread object in its function_chaininstance variable. One function exists to handle the work associated with disinheriting objects andanother to handle the work of bequeathing properties to objects. With the function, a list of parameters (which include the set of objects in the transitive closure) is kept, as well as the current levelof the invoke depth (corresponding to the invoke depth of the current shadow copy). The execuCHAPTER 3—Implementation of the Oblect Property Scheme 46tion of the functions in the function_chain is performed by the post-handler for the Recoverable property and by the code which implements the restore statement.If the method terminates normally, the function_chain is traversed in the order it wascreated, and each function is executed in sequence. If a res tore statement is encountered, thefunction_chain is traversed in the reverse order of its creation until the invoke depth of thefunctions in the chain are of a higher level than the invoke depth of the current recovery shadow.The functions take as one argument a boolean flag indicating the status of the method termination.This allows them to either complete the work begun when the assignment was made, or roll itback to the previous state it was in.An alternate scheme to performing the minimal work necessary when a recoverable assignment is made is to make the optimistic assumption that the method will terminate normally, anddo all the work associated with disinheriting and bequeathing properties accordingly. It is not possible to do a “pessimistic” assumption, since the object assigned to the instance variable mustreceive the services associated with the properties it inherited as a result of the assignment. However, this scheme will be very expensive in the case where the assignment is recovered, since allnew data structures for the disinherited object will need to be created (which, in the case of Persistent or Durable objects, will require coordination with the on-disk storage; furthermore, the system must not in any case delete any on-disk versions until it is absolutely sure that the object is nolonger Persistent or Durable). Delaying most of the work until later does not increase the amountof work that needs to be done. Furthermore, at least some work must be done even in the optimistic case, since all the objects in the transitive closure must be unlocked. Since the locks wereacquired directly and not as the result of an invocation, it cannot be assumed that they will bereleased by the Concurrency post-handler, since the post-handler may never be executed.CHAPTER 3—Implementation of the Object Property Scheme 473.5 Part-Of ClustersThe partof keyword also provides property inheritance, and therefore much of its implementation is similar to that described in Section 3.4. When the compiler detects an assignment to aninstance variable marked partof, a special runtime function, UpdatePartOf ( ), is executed.As with property inheritance, this function and its support functions must treat recoverable assignments to Part-Of instance variables in a special manner, as described in Section 3.5.3.In addition to providing property inheritance and dependency, the partof keyword is usedby the runtime system to provide a logical clustering of objects. The transitive closure of allobjects which can be accessed from a root object (i.e., an object which is not Part-Of any otherobject) using Part-Of references comprises the Part-Of cluster. This clustering information is currently used by the Durable and Persistent pre- and post-handlers to store and retrieve all objects ina cluster to and from disk as a single unit (see Section 4.3). Once object migration is implemented,clustering information can also be used to migrate entire clusters between disks. How objects areremoved from and added to Part-Of clusters is described below. The effects of such changes toPart-Of clusters on object storage are discussed in Section 4.4.There is one potential problem with using Part-Of clustering information in the mannersdescribed above. Consider the situation shown in Figure 6, where two objects form a Part-Of cluster. One thread (Ti) invokes a method on one object of the cluster, while another thread (T2)invokes a method on the other. If Ti is a worker thread for a remote request the system maydecide to migrate the cluster. However, lea fObj ect may be in an inconsistent state becausethread T2 is invoking on it. If the objects in the cluster are Controlled, the system can acquire allthe locks before doing the migration; however, there is no guarantee that either rootObj ect orleafObj ect have concurrency control locks (and indeed, since only one thread is accessingeach object at a time, neither object may need to be Controlled). The system has no mechanism byCHAPTER 3—Implementation of the Object Property Scheme 48FIGURE 8. Objects in a Part-Of Cluster.which it can detect that uncontrolled objects in a cluster are in a consistent state, yet it may need tomake a copy of the instance data of these objects for the purposes of migration or object storage.To solve this problem, and to more rigorously enforce the notion of clustering, a new concurrency control lock is added to each Part-Of cluster. This lock is shared among all the objects inthe cluster, and any access to any objects in the cluster must first acquire this lock before acquiring any concurrency control locks on the objects in the cluster. Although this cluster lock rendersany local object locks superfluous, the current implementation does not perform any optimizingand all locks are still acquired.TiT2CHAPTER 3—Implementation of the Oblect Property Scheme 49By placing a cluster lock on all the objects in a cluster, the system is effectively creating oneControlled object out of all the component objects in the cluster: only one thread may access theobjects in a cluster at the same time. Although this scheme does solve the problem describedabove, adding the concurrency control lock will degrade performance slightly. Treating the objectclusters as single objects has one additional drawback: it is not possible for a thread to spawn parallel invocations on the individual objects of a cluster, as deadlock will result.The Part-Of cluster lock is acquired during the execution of the property pre-handlers, and isreleased during the execution of the post-handlers. The cluster lock is acquired just prior to andreleased just after any local concurrency control lock is acquired or released.3.5.1 Removing Objects from a Part-Of ClusterWhen an object is de-assigned from an instance variable which is marked partof, the systemmust first determine if the object is a single object or has part0 f references of its own. The transitive closure of all objects which inherit properties from the removed object is computed, andthese objects are tagged to indicate if they simply inherit properties from the removed object orare Part-Of the removed object. These objects are locked, and the properties of the objects in thetransitive closure are updated in the same fashion as described in Section 3.4. If the object hasPart-Of references, then the removed object will form the root of a new Part-Of cluster. A newcluster lock is created and assigned to all the objects in the transitive closure which are Part-Of theroot object.Since Part-Of clusters have cluster locks, it’s possible that a thread waiting on the clusterlock was attempting to invoke on the removed object (or, if the removed object is now the root ofits own Part-Of cluster, one of the objects in the new cluster). Therefore, with each queued threadthe identity of the target object of the thread is stored. When objects are removed from a Part-Ofcluster, the cluster lock waiting list is examined, and any thread which is waiting to invoke on anCHAPTER 3—Implementation of the Object Property Scheme 50object no longer in that cluster will be moved to the new cluster lock (if one exists), or restarted ifthe removed object is no longer part of a cluster.3.5.2 Adding Objects to a Part-Of ClusterWhen adding an object to a Part-Of cluster, the system first ensures that the object is in the sameaddress space as the cluster. As with removing an object from a Part-Of cluster, when adding anobject the runtime system must determine if the object is the root object of its own cluster. If so,the objects in the old cluster must have their cluster lock pointers reset to point to the lock of thecluster to which they are being added. The threads waiting on the now unused cluster lock must betransferred to the new cluster lock. If the object being added is a single object (i.e., it has no Part-Of references) then any threads waiting on its local concurrency control lock (if one exists) arerestarted. These threads are not allowed to begin execution of the method code, however; instead,they are required to begin the process of executing the property pre-handler code again. Thisforces them to acquire the new cluster lock before they are allowed to acquire the local concurrency control lock, for which they had been previously waiting. An alternate scheme to forcing athread restart is to move all the threads queued on the local concurrency control lock to the clusterlock. The current implementation of locking makes this difficult, however, since the lock depthwill not be correctly updated.3.5.3 Recovering Part-Of AssignmentsBecause instance variables marked partof provide property inheritance, recoverable assignments to Part-Of instance variables are handled in the manner described in Section 3.4.1. As withany recoverable assignment that can affect multiple objects, the primary concern is that theobjects be kept in a consistent state throughout the life of the invocation. Only a minimal amountof work is done when an object is added or removed from a cluster, and functions are queued upCHAPTER 3— Implementation of the Obiect Property Scheme 51on the Thread object’s function_chain to finish the work begun, or undo the work started,when the status of the invocation is determined.When a recoverable assignment is made, any objects removed from the Part-Of clusterretain their cluster lock. This allows them to remain protected against concurrent accesses whiletheir status is in doubt. Dropping the cluster lock (or creating a new one if the removed object isthe root of a new cluster) must be done anyway, and delaying this work until it is known that theassignment is permanent makes recovery easier, since any threads queued on the original clusterlock can be left untouched. If an existing Part-Of cluster is added to a Part-Of cluster, the existingcluster retains its cluster lock until the status of the invocation is determined. This lock is held bythe thread which is performing the recoverable invocation, so all the objects in the cluster willremain in a consistent state.3.6 Self-InvokesThe question arises about what to do about self-invokes, i.e., an object invoking a methodupon itself. Self-invokes can be viewed in one of two ways, each with its own advantages and disadvantages:(1) Self-invokes are considered to be “sub-invocations” of the initial object invocation. As such, no system services need to be provided for the invocation: allnecessary pre-handlers were already executed before the initial invocation,and the post-handlers will be executed once the initial invocation finishes.(2) Self-invokes are normal invocations, and are treated no differently than anyother invocation. All the property pre- and post-handlers are executed forself-invocations.If self invocations are viewed as sub-invocations, then the runtime can execute them moreefficiently (since it does not need to check for object properties). Furthermore, the object can becontinually modified by sub-invocations, but nothing will be written to disk until the initial invoCHAPTER 3—Implementation of the Object Property Scheme 52cation returns. Any res tore statement encountered will restore the instance data to the state itwas in prior to the initial invocation; all work done inside the object to this point will be lost. Thisprevents an object from executing a transaction upon itself. It also raises the question of whetheronly invocations explicitly made on the object self should be considered sub-invocations, or ifinvocations on an instance variable which was set to self should also be sub-invocations. Theruntime system has no mechanism by which it can determine which of these scenarios occurred,although the compiler could be modified to emit special code in the event of an invocation onself.If self-invokes are classified as normal invocations, then redundant work will be done insome of the pre-handlers (e.g., the local concurrency control lock is obviously already held by thethread). Although some efficiency is lost, programmers are presented with a single, uniformmodel of object invocation, and they can view self-invocations as if they were any other invocation. A further question arises, and that is whether self-invocations should be considered Dependent or not. If they are considered Dependent, then the efficiency of the system can be furthercompromised, as extra work for Dependency must be performed; however, it does imply thatwrites will be delayed until the initial invoke returns. If self-invokes are not considered Dependent, then all invocations following the self-invocation would consider the self-invocation to bethe root of their Dependent chain; this would preclude having self-invokes inside of transactions.In the current implementation, all self-invocations are treated as normal invocations, and arefurthermore considered to be Dependent invocations. Although the dependent Invoke flag isnot set by the compiler in this case, the runtime system checks to see if the method invoker andinvokee are the same object, and sets this flag if they are. Although this scheme is not the mostefficient, it provides the most consistent support for Dependent invocations, and helps provide auniform programming model.CHAPTER 3— Implementation of the Object Property Scheme 533.7 Parallel Invocations and Property SupportAs mentioned in Section 2.1, the Raven language contains special constructs to facilitate user-directed parallel programming. There are three primary forms of parallelism provided: companioninvocations, early replies, and delayed results. The work on parallelism focused only on the Controlled property, in an environment that pre-dated Dependency. Most of the thought given to thesefeatures was therefore directed towards their impact on concurrency control [2]. Integrating thenew property scheme (especially the notion of Dependency) with Raven’s support for user-levelparallelism has presented several challenges, many of which are yet to be fully resolved. For afurther discussion of these issues, and alternate implementations to those chosen, see Chapter 5.Property information is kept by the thread, so it is not possible to perform a Dependent invocation using a parallel thread of execution. There is no facility by which property information keptby one thread can be propagated to another thread, although some scheme such as the one used forremote invocations (see Section 3.3.3) could potentially be adapted. Consequently, multi-threadedtransactions are currently not supported.3.7.1 Companion InvocationsCompanion invocations are invocations which are started from and executed in parallel withthe current thread of execution. In the Raven language, executing the statement{ someobject.someMethod() } .startO;creates a companion thread which will invoke the someMethod method on someObj ect. Thetarget of the invocation (in this example, someObj ec t) is treated as if it were not Dependent,even if the reference to the object is marked Dependent. If this object makes subsequent invocations on Dependent objects, they will form their own Dependent chain, and the target object thecompanion thread invoked on will be the root of the chain.CHAPTER 3—Implementation of the Object Property Scheme 54Another way to achieve parallel execution in a manner similar to a companion thread is forthe user to simply create a new instance of the Thread class and have it invoke a method on anobject. As with a companion thread, the initial invocation of this thread is treated as if it were nota Dependent invocation.3.7.2 Early ReplyEarly reply is a mechanism by which a method can return a result to its invoker but continueexecuting inside the method. The statementresult (value);will return value to the caller, and a new thread will be created at this point to continue executing the method.Early replies have severe consequences for the implementation of object properties, especially when the object is part of a Dependent chain. Consider a Controlled object in which anearly reply is done. The initial invoker must give up the lock it acquired, and the spawned threadmust acquire the lock. The question arises as to what happens if the object is in a Dependentchain. The invoking thread will not give up its lock, but the spawned thread will need to acquirethe lock before it can do any work. Consider also a Recoverable object in which an early reply isdone. It is unclear what should happen if a restore statement is encountered by the new threadexecuting after the result has been returned: should the object be restored to the state it was inwhen the result statement was executed, or to the state it had prior to the initial method invocation? What if the object is part of a Dependent chain, and an object above it in the chain executesa restore? How can work done by the spawned thread be restored properly, especially if thethread is still executing inside the object? Similar problems relate to the Durable and Persistentproperties: should the object state be written to disk at the point of the result, when thespawned thread terminates, or both? If only at the point of the result, then changes made by theCHAPTER 3— Implementation of the Object Property Scheme 55spawned thread could be lost; but if the object is Durable and part of a Dependent chain, then theobject state cannot be written by the spawned thread when it terminates, since the object state canonly be written along with the objects comprising the initial Dependent chain.Rather than attempt to resolve all these issues, and to simplify the implementation, earlyreplies are ignored in some circumstances. If the object is part of a Dependent chain, or has theRecoverable, Durable, or Persistent properties, then the result statement will simply save thevalue to be returned to the caller and use it as the return value when the method terminates (ignoring any subsequent value specified by a return statement as the result to return). A new threadis not created; instead, the current thread continues execution, and control is not returned to thecaller until an actual return statement is encountered or execution of the method finishes. Thischoice decreases the parallelism of the system, but ensures its correct operation when an earlyreply is encountered.3.7.3 Delayed ResultDelayed result allows the execution of a method to finish with the expectation that a differentthread will actually provide the result to return to the caller. The statementleave;acts like a return statement, except the value to be returned to the caller is not taken from thebody of the method but is instead sent to the current thread by another thread. If this value hasn’tyet been sent, the current thread blocks (and control is not returned to the caller) until the value isreceived. A thread sends a return value to another thread using the result statement:result thread value;sends value as the value to return to the thread thread.CHAPTER 3—Implementation of the Object Property Scheme 56To properly implement delayed result, any locks held on the object (both concurrency control locks and cluster locks) must be released when the leave statement is executed. This isbecause it may be necessary for another thread to enter the object in order to perform the resultwhich will send the value to the waiting thread. However, if the object is in a Dependent chain,locks are not supposed to be released until the top-level invocation completes. If the requirementsof Dependency are maintained, then using a delayed result may bring the system into a state ofdeadlock; if locks are freed, then the semantics of Dependency are not preserved.Since delayed result provides programmer-specified parallelism, the current implementationwill release any local locks when a leave statement is executed, even if the object is in a Dependent chain. It is assumed that the programmer will take into account that locks will be releasedwhen writing code that executes a leave, and will not attempt to use such objects in transactions, since a significant consequence of releasing the locks is that serializability will be lost whenanother transaction invokes on the object while a thread is suspended waiting for a result.Releasing local locks when a leave is encountered creates the potential for an additionalproblem. Consider a thread Twhich is suspended in an object 0 waiting for a result to return to itscaller. It’s possible for another thread T’ to acquire the locks on 0 and assign 0 to an instancevariable marked inherits, or de-assign 0 from such an instance variable. When T resumes, theproperties of 0 have changed from what they were when the invocation on 0 began. Propertypost-handlers are executed after a suspended thread resumes, creating a potential mismatch in theexecution by Tof the property pre- and post-handlers. The current implementation therefore generates a runtime error if an object which contains suspended threads is assigned to an instancevariable marked inherits orpartof.CHAPTER 3— Implementation of the Object Property Scheme 573.8 User PropertiesUser properties are supported in the same way as the system properties, through the execution ofpre- and post-handlers. The invoke routines and the system pre- and post-handlers are all writtenin C. Allowing programmers to write their pre- and post-handlers in C as well is possible, but isfraught with problems. If users are allowed to write in C, they can become tempted to modify system data structures. Furthermore, programmers would need to know details of the Raven implementation in order to access object instance data; however, these details may change, introducingbugs into the user code.Given these considerations, user pre- and post-handlers are therefore supported by performing invocations on the object. The basic Obj ect class supports four (empty) pre-methods andtheir corresponding post-methods:behavior preUserN(dependentlnvoke: Int);behavior postUserN(dependentlnvoke: mt1 isDependentRoot: Int, hasProp: Int);Where Ncan be either 1, 2, 3, or 4.The integer parameter dependent Invoke which is passed to the user pre- and post-handlers is set to either True or False (predefined boolean values supported by the Raven language) depending upon whether the current object is Dependent upon its invoker. Similarly, theparameter isDependentRoot will be True or False depending upon whether the currentobject is the root object of a Dependent invocation chain. This information is provided to the programmer so that user properties can also be designed to take advantage of Dependent invocations.In such circumstances, the programmer may need to subclass the Thread class so that stateinformation for the user property can be kept in the thread along with the information for the Controlled, Recoverable, and Durable properties. The integer parameter hasProp is set to True orFalse depending on whether the current object actually has the user property. This flag is necesCHAPTER 3—Implementation of the Object Property Scheme 58sary since the post-methods will be executed when isDependentRoot is True, even whenthe object does not have that property. Without this flag, the programmer would have no way ofdetermining if the root object of a Dependent invocation chain actually had one of the user properties.The pre- and post-methods will be invoked on an instance which has user properties. Whena programmer wishes to implement a user property for a class, the programmer must overridethese methods in the class. The invocations of the pre-methods must be done in such a way thatthey do not result in a continual recursive execution of the pre-methods; similarly, the post-methods must be executed in such a way that they don’t cause the pre-methods to execute. This is doneby calling the method code directly, bypassing the property support routines. The pre-handlers areonly executed on the machine where the object resides, so there is no worry that the object datawill not be local.Although self-invokes are normally considered dependent invocations, the pre- and post-methods are not considered dependent invokes. Since the user pre-methods are executed after theRecoverability pre-handler, any restore statement executed inside the object method code willrestore the object to the state it was in prior to the execution of the pre-methods. This may createsome difficulties, since the current implementation does not re-execute the pre-methods (and thepost-methods will be executed when the object invocation finishes). The issues surrounding userproperties are further explored in Chapter 5.Since the pre- and post-handlers are written by the user, the system cannot make any guarantees about the orthogonality of user properties. No tools have been written to test for such orthogonality.CHAPTER 3—Implementation of the Object Property Scheme 593.9 Status of the Implementation of PropertiesAlthough semantics have been developed for all the properties (see Section 2.4), the runtime system does not yet provide all the services for which there are properties. The properties which arecurrently implemented are the following:• Controlled• Recoverable• Persistent• Durable• Immutable• User properties (as described in Section 3.8)Details of the implementation of the Controlled property can be found in [1]. Details of theimplementation of the Recoverable property can be found in [71. Details of the implementation ofthe Persistent and Durable properties can be found in Chapter 4.Dependent invocations are supported by the Controlled, Recoverable, Persistent, and Durable properties, even when such invocations are remote. Although the Raven semantics say nothing about Dependent Persistent invocations (Section 2.6.1), the implementation treats them in thesame manner as objects which are Durable. Dynamic property inheritance, through both theinherits and partof keywords, is fully supported. This includes the case when the assignment to an instance variable marked inherits or partof is recoverable: if a restore statement is encountered in the current Dependent calling chain, the object property sets will becorrectly restored, and all data structures (such as lock structures) used in the implementation ofsystem properties will be correctly updated. However, the system only allows property inheritance from local objects (i.e. objects which are in the same address space).Object Storage: Details ofthe Durable and PersistentProperties4.1 Object Storage OverviewObjects in Raven are normally volatile; they exist only in memory, and persist only as long as theactive process which created them (or until they are garbage collected [1]). When an object isgiven either the Persistent or Durable properties, the Raven system will ensure that a copy of theobject’s instance data will be written to disk. Since the Persistent and Durable properties functionin almost identical ways (see Section 2.4 for a description of their semantics), the concepts discussed in this chapter apply equally to both properties. The only differences between the twoproperties arise in their implementations, and are described in Section 4.3.5. In this chapter,objects which are described as being storable are meant to be those which have either the Persistent or Durable properties.The object storage system provides the following features:60CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 61• Reference swizzling: All references to other objects are capability pointers,which point to the location in memory where the object’s capability structureresides. All references to an object must be converted to unique identifierswhich correspond to the object. This allows the system to reload the object atany position in memory, as the unique identifiers can be translated back to thenew capability pointer.• Whole object storage: Objects must be stored in their entirety in an atomicfashion. If the object’s state isn’t written atomically to disk, a failure during thedisk write could result in an inconsistent version of the object on disk, and subsequently an inconsistent version of the object will be loaded into memory.• Lazy loading of object data: When a reference to an object is unswizzled, ifthat object is not currently in memory, the runtime system will not fetch theobject data immediately. The object’s instance data will be fetched only whenit is actually needed, i.e. when an invocation is made on the object.• Object clustering in storage: Objects which comprise a Part-Of cluster arestored together on disk, and loaded together from disk.Although the Raven runtime system provides garbage collection for in-memory objects, nogarbage collection is currently provided for objects in storage. The system will remove an objectfrom storage when it is no longer a storable object (e.g., while an object inherits the Persistentproperty it will be stored to disk, but when it no longer inherits that property it will be removedfrom disk storage).4.1.1 Globally Unique IdentifiersTo implement reference swizzling, the system must provide a globally unique identifier, or GID,for every storable object. GID5 are also useful for accessing remote objects, but in the absence ofobject mobility and persistence the object’s location information can be used to provide a uniqueidentifier. The original version of Raven used location information as the global identifier, andwas therefore unsuitable as a true globally unique identifier.CHAPTER 4— Obfect Storage: Details of the Durable and Persistent Properties 62The actual GID of an object is a 128-bit value composed of four distinct 32-bit fields (seeFigure 9). The first field contains the IP address of the machine on which the object was created.The second field contains the port number to which the Raven World which created the object wasattached. The third and fourth fields are incremental counters. The third field is incremented onceupon each startup of a Raven World, and the fourth is incremented once for each GID assigned bythe World. The fourth counter is reset to zero upon each startup of a World.{u_long creator;u_long world;u_long generation;u_long name;creator: IF address of creator machineworld: Port number of Raven Worldgeneration: Raven World incarnation countername: Per-incarnation GID assignment counterFIGURE 9. GID Structure.A GID is assigned to every storable object. An object which is referenced from anotherRaven World (i.e., for which a Proxy object [1] exists in the other World) is also assigned a GID.GID5 are not normally assigned at object creation time unless the object is storable. The object’scapability structure (see Figure 6) contains a pointer to a structure which in turn contains a pointerto the GID structure (see Appendix A.6). If the object does not have a GID, the pointer in thecapability structure will point to NULL.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 634.2 Storage ModelThe basic storage model used is outlined in Figure 10. At the highest level are the Raven objectsthemselves, which exist in main memory. Each storable object has an associated Storage Managerobject (see Figure 11), which is an instance of the StorageManager class (see Appendix B.2).The storage manager is responsible for overseeing the storage of the object’s instance data to disk,as well as converting stored data into user objects.Storable Objects in MemoryStorage ManagersTDBM ManagerLocal DiskFIGURE 10. Object Storage Model.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 64Objects Storage________SwizzledManager DataFIGURE 11. Storage Manager Role.At the lowest level is the local disk itself. To achieve whole object storage, TDBM [6] isused to write the object state to disk. TDBM is a transaction oriented database that stores key!value pairs. TDBM will ensure that all the data presented to it is written in an atomic fashion to alocal disk. Although multiple Raven Worlds on the same machine may use the same disk, eachWorld has its own TDBMmanager object (see Figure 12), which is an instance of theTDBMIanager class (see Appendix B.5). The TDBMmanager object is accessible inside Ravenapplications as the global object identifier TDBMrnanager. The TDBMmanager object writes thedata for all the objects in the Raven World to a file specific to that World. If the Raven World isshut down and a new instance of Raven is launched with the same World identifier (i.e., on thesame machine using the same port number as the previous World), it is considered the same Worldand will use the same file.TDBM cannot guarantee atomic updates of data if the database file is located across NFS.Object storage should therefore be done on a disk physically mounted on the same machine onwhich the Raven World is running, or the system will be vulnerable to NFS failures. The localdirectory under which TDBM should store its files is determined at startup time by examining theenvironment variable RVSTORAGEPATH. If no such environment variable exists, a default valueis used; however, this default value is not guaranteed to exist on any particular host.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 65Encoded TDBM_______DiskData ManagerFIGURE 12. TDBM Manager Role.Each Raven World has an associated GlDmanager object (see Figure 13), which is aninstance of the GlDManager class (see Appendix B.4). The GlDmanager object is accessibleinside Raven applications as the global object identifier GlDmanager. The GlDmanager hasseveral responsibilities:• It assigns GIDs to storable objects.• It maintains a GID to capability map. For every (currently known) object witha GD, this map provides the current location in memory of the capabilitystructure for the object. This map is necessary during unswizzling, when GDsmust be converted to capability pointers.• It creates capability structures for objects loaded in from disk.• It intercepts invocations made on objects currently not in memory and interactswith the TDBMmanager to fetch the objects from disk.4.2.1 Object Storage EventsAfter an invocation which modifies the instance data of a storable object completes, the object’sinstance data must be written to disk. This involves the following actions:(1) The object’s storage manager is notified that an invocation occurred on theCHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 66Fetch Object Requests Load From Disk RequestsAssign GID Requests Decode Data RequestsFIGURE 13. GIl) Manager Role.object.(2) The storage manager instructs the object to encode its instance data.(3) The storage manager adds the information in the object’s capability structureto the encoded data.(4) The encoded data is passed to the TDBMmanager along with the GD of theobject, which is used as the key under which the data is stored.(5) The TDBMmanager writes the data to disk.4.2.2 Object Loading EventsWhen an invocation is made on an object which is not in RAM, the object must be loaded in fromdisk. The capability structure used for objects not in RAM is a “skeleton” capability structure: theonly fields of the structure which are filled in are the GID and the invoke routine (see Figure 6).The invoke routine used by skeleton capabilities is a special routine called Fetchlnvoke.Fetchlnvoke ensures the object data is loaded into disk and that the skeleton capability strucCHAPTER 4— Oblect Storage: Details of the Durable and Persistent Properties 67ture is filled in before allowing the invocation to proceed. The exact sequence of events involvesthe following actions:(1) The Fetchlnvoke routine calls the GlDmanager, and asks it to load in thedata for the object with the GID found in the skeleton capability structure.(2) The GlDmanager passes the GID of the object to the TDBMmanager.(3) The TDBMmanager fetches the encoded data stored under that GD fromdisk.(4) The GlDmanager extracts the capability information and fills in the skeletoncapability structure, including replacing the Fetchlnvoke function withthe appropriate invoke function for the object.(5) The GlDmanager creates a storage manager for the object, and passes theencoded data to the storage manager.(6) The storage manager creates an object of the appropriate class, and has it loadits instance data using the encoded data.(7) During decoding, all GIDs are passed to the GlDmanager to be unswizzledand turned into capability pointers. If no capability exists for the GID, theGlDmanager creates a skeleton capability structure for the object.4.3 Implementation DetailsThe StorageManager objects, GlDmanager, and TDBMmanager are all Raven objects and interactwith each other using normal object invocations. Much of the implementation of these objects,however, is directly in C, although the Raven language has been used where possible. As anobject’s instance data is encoded and the capability information added to form the completeencoding of the object, Raven Integers are used to hold pointers to the data for passingbetween a Storage Manager, the TDBMmanager, and the GlDmanager.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 684.3.1 Object EncodingWhen a Storage Manager needs to get the encoded form of an object, it asks the object to encodeitself and return the encoded data. Similarly, a Storage Manager will provide an object with apointer to encoded data, and have the object load its instance data using the encoded data. TheObj ect class provides two basic methods:• behav enCodeData() : mtThis method traverses the object’s instance data and writes an encoded version of the data intomemory, swizzling all object references and encoding primitive integers and floating point numbers (see below). A pointer to the location of the data is returned.• behav deCodeData(data: Int);This method replaces the object’s current instance data with the data obtained by decoding thedata pointer passed in.The format of a buffer containing encoded data in memory is shown in Figure 14. The bufferbegins with an integer representing the total length in bytes of the buffer (including the four bytesneeded for the integer), followed by the encoded instance data.Total Length DataFIGURE 14. Format of encoded buffer in memory.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 69Raven currently supports three different types of instance variables: mt (simple integer),Float (floating point number), and cap (object reference). While encoding (or decoding) anobject, the type of instance variable is determined by examining the definition of the object’sclass.Ints are stored as instance variables in their (usually) 32-bit machine-dependent representation [1]. This allows integer operations to be efficient. They are encoded by simply copyingthem directly into the encoded buffer. Conversion into an external representation (such as thatobtained using XDR [25], which is currently used to encode requests and replies for remote invocations) is not needed nor done, since the object will always be reloaded into the current RavenWorld, and the assumption is made that the machine representation of integers will not changebetween incarnations of a Raven World.Like Ints, Floats are also stored as instance variables in their machine-dependent form,and are encoded by simply copying the floating point number into the encoded buffer.Object references are swizzled by writing out the GID of the object to the encoded buffer.Upon decoding, the GID is converted to a local capability by the GlDmanager. If the object referenced is not storable, zero values are written to the encoded buffer in place of the actual fields ofthe GID (which may not even exist for a non-storable object). Since a non-storable object will notsurvive system restarts, if an actual GIlD were stored the encoded object would contain a referenceto an object which no longer exists. Upon decoding, a zero-valued GID is treated as a reference tothe nil object. This practice precludes the use of the object storage system as a mechanism forproviding object paging.The current implementation relies upon the fact that each of the values stored in the encodedbuffer are a multiple of four bytes. If the encoded buffer itself is allocated on a four byte boundary(true for the current implementation of the Raven MALLOC () macro), then the values (especiallyCHAPTER 4— Oblect Storage: Details of the Durable and Persistent Properties 70integers and floating point numbers) can be easily written to and extracted from the buffer. Sinceclass definitions can vary widely, the size and format of different encoded buffers is highly variable, and the object class must be known to properly decode an object’s data.The data in the encoded buffer contains only the object’s instance data and lacks otherimportant information about the object which is contained in the object’s capability structure. Inaddition to the instance data, an object’s class, property set, parent, and inheritance root must alsobe stored. Storing this information allows the capability structure to be rebuilt upon object loading, and provides the class information necessary for decoding the data. Figure 15 shows the layout of the complete encoding of an object, including the capability information. The class name,which is assumed to be unique for all classes (an assumption shared by the remote invocationmechanism [1]), is stored along with its length. If necessary, padding is added after the class nameto ensure that the properties field begins on a four byte boundary. The properties stored in theencoded form of an object may be a different set than those the object currently has. This isbecause the object can inherit properties from a non-storable object, in which case the propertymask to be stored must be calculated by traversing up the inheritance tree until the top-most storable object from which properties are inherited is found. The Parent GID field holds the GID ofthe object’s parent (i.e., the object from which properties are directly inherited). The Inh_rootGID field contains the GID of the top-most storable object in the inheritance tree. The InstanceData field contains the contents of the encoded buffer shown in Figure 14. A final pad, if needed,is placed at the end to ensure the entire encoded object is a multiple of four bytes. Since theencoded buffer will always be a multiple of four bytes, and the class name with its pad will be amultiple of four bytes, there should never actually be a need for a trailing pad.The process of adding the object’s capability information to the encoded data is done by theobject’s Storage Manager. The GlDmanager is responsible for extracting the capability information and filling in the object’s capability structure when an encoded object is loaded from disk.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 71Name Parent Inh_rootT h Class Name Pad Properties Data Pading GID GIDFIGURE 15. Format of a fully encoded object.4.3.2 Storage Manager ImplementationObjects maintain a pointer to their storage manager inside their capability structure. When a storable object is created, or when an object inherits the Persistent or Durable properties, the objectwill be assigned a Storage Manager. All of the storable objects in a Part-Of cluster each use thesame Storage Manager.Storage Managers maintain a “cached” version of the encodings for every object they manage. These caches serve two purposes:(1) They allow the Storage Manager to compare the object’s current state with itsprevious state, to determine if the object state has actually changed. If theobject is unchanged, there is no need to write the object to disk, thus savingsignificant performance overhead.(2) They allow the Storage Manager to submit all the objects in a Part-Of clusterto the TDBMmanager for storage at once. If the Storage Manager didn’tmaintain cached versions, it would have to encode and encode each object inthe cluster every time it needed to write the cluster to disk. Furthermore, ifthe Part-Of cluster lock is ever abandoned, a lack of cached versions couldforce the Storage Manager to acquire a lock on every object in the clusterbefore encoding each object. No cluster lock implies multiple threads couldbe inside the cluster, so the Cluster Manager may have to wait a significantamount of time in addition to increasing the likelihood of deadlock.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 72The encoded data of an object is kept by a Storage Manager inside an object of the SMEntry class (see Appendix B.3). An SMEntry object contains the object capability pointer, apointer to the object’s encoded data, and the length of the encoded data. If a Storage Managermanages multiple objects, it keeps the SMEntry objects in a dynamically sizeable array. TheSMEntry for the root object of the Part-Of cluster is always the first object in the array.4.3.3 TDBMmanager ImplementationA Storage Manager presents the encoded data streams to the TDBMmanager for writing to disk.The encoded data is packaged into an object which is an instance of the class TDBMDatum (seeAppendix B.6). A TDBMDatum object is an object encapsulation containing two of theTDBMDatumStruct data structures used by the TDBM library. It contains four integer values:one integer value used as a pointer to the data, a second holds the data length, a third is used as apointer to the key under which the data is to be stored, and the fourth contains the length of thekey. A TDBMDatumStruct also requires alignment information, but data and keys are alwaysassumed to be aligned on a four byte boundary. When a Storage Manager invokes on the TDBMmanager, it creates a TDBMDatum object and sets the data pointer to point to the encoded datastored in the SMEntry object. A pointer to the object’s GIJD is used as the key under which theobject is to be stored. If the Storage Manager manages multiple objects, it passes an array ofTDBMDatum objects to the TDBMmanager. Each TDBMDatum object occupies the same position in the array passed to the TDBMmanager as the SMEntry object from which the TDBMDaturn was formed occupies in the array kept by the Storage Manager. As such, the TDBMDatumobject containing the encoded data for the root object of the Part-Of cluster will be the first objectin the array passed to the TDBMmanager.The TDBMmanager stores data to disk in one of three formats, which are shown in Figure16. The basic structure of all three formats is count data, where count specifies the numberof objects stored in the data. The key under which the data is stored is an object GID.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 731•(Encoded ObjecGID JGIlD1DataGID D3:(GIDn D0 GID1FIGURE 16. Formats of data storage on disk.Format type 1 is the most basic, and shows how a single TDBMDatum object which is presented to the TDBMmanager will be stored. The count field is one, since only one object isstored. The data field contains the encoded data that was passed in the TDBMDatum object. Thekey under which this data is stored is the key contained in the TDBMDatum object, which is theGIlD of the object.When the TDBMmanager is presented with an array of TDBMDatum objects, it stores allthe objects together on disk in one continuous block, as shown in format type 2. In this case,count contains a count of the number of encoded objects stored in the block, which is equal toKey2:(1 Encoded ObjectCount GIlD1 Size Data GID Size Data)CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 74the number of TDBMDatum objects in the array. It is followed by <count> tuples consisting ofthe key under which the object was to be stored, the size of the object’s encoded data, and theencoded data itself. The entire block is stored using the key found in the first TDBMDatum objectof the array, which will be the GID of the root object of the Part-Of cluster which is being stored.Storing the size of the encoded data allows the TDBMmanager to quickly transform a block ofclustered objects into individual TDBMDatum objects, one for each stored object, without havingto know the format of the encoded data.When an array of TDBMDatum objects are to be stored, all the encoded objects will bestored using the GID of the root object as the key. To allow the system to locate the other objectsin the cluster, the TDBMmanager stores a data block of format type 3 under the GID of theseobjects. The count field is set to zero, indicating that the data is the actual key under which theobject’s data is stored.When an object is to be loaded in from disk, the TDBMmanager is presented with aTDBMDatum object with only the instance variables corresponding to the key set. The TDBMmanager uses the key information to load in the associated data from disk. The data is examinedto determine which format it is in. If the data block is of format type 3, the TDBMmanager usesthe stored key to fetch the actual data. If only a single object was stored under the key, the TDBMmanager returns the passed in TDBMDatum object with the integers for the value pointer and sizeset to the encoded data. If multiple objects were stored in a cluster under the key, an array ofTDBMDatum objects is returned. If no object is stored under the key presented, the TDBMmanager returns the nil object.Because Raven is multi-threaded, the TDBMmanager has the Controlled property to ensurethat accesses to the disk are serialized and that the whole system does not enter a blocked statewhen a particular thread is blocked waiting for a lock from TDBM itself.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 754.3.4 GiDmanager ImplementationThe GlDmanager interacts with the TDBMmanager to load encoded objects from disk. If theTDBMmanager returns nil to the GiDmanager, the GlDmanager attempts to find the objectsomewhere on the network. The creator and world fields of the object’s GID are examined,and a remote invocation is made on the GlDmanager of the Raven World at that location in anattempt to find the object. When object migration is implemented in Raven, a broadcast or othermechanism will be needed to find the actual location of the object, since there will be no guarantee that an object will remain in the World in which it was created.If the TDBMmanager returns encoded data to the GlDmanager, the GlDmanager begins theprocess of unencoding the object data. First, it creates a Storage Manager object to manage thestorage of the object (or objects, if a cluster of objects were returned by the TDBMmanager).Next, it fills in the capability information for each object, creating a capability structure first ifnecessary. Any necessary locks (including a cluster lock) are created. The encoded data is thenpassed to the Storage Manager so the object instance data can be decoded.As described in Section 4.2.2, capability structures that exist for objects not currently inRAM use a special invoke routine called Fetchlnvoke. When a Fetchlnvoke is performed,the first action of the GlDmanager is to ensure that the object data has not already been loaded in.Although the GlDmanager is controlled against concurrent accesses, multiple Fetchlnvokescould be performed on an object before the first has completed. The final action of the GIDmanager is to set the invoke routine to the normal invoke to be used for the object.The GlDmanager also maintains a mapping of GIDs to capabilities. This allows it to find thelocal capability pointer for any object based upon its GID. The map is simply a hash table thatassociates the four integer fields of the GID with the capability pointer of the object. IIIIISc[10], a table package which performs { 4 integer) —> { 1 integer) mappings, is used to manage theCHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 76hash table. If the GlDmanager is asked for the capability pointer for a particular GID, and no suchcapability currently exists, the GlDmanager creates a skeleton capability structure whose invokeroutine is Fetchlnvoke; it then returns a pointer to this structure. The GlDmanager will turnthis capability structure into a Proxy object if the object cannot be found on the local machinewhen the GlDmanager attempts to load the instance data of the object.4.3.5 Implementation Differences Between the Persistent and Durable PropertiesIn the current implementation, the Durable and Persistent property handlers are almost entirelyidentical. Objects have only one Storage Manager, which acts for either the Durable or Persistentproperties (or both, if an object actually had both properties). In the case of Dependent invocations, both properties are handled in the same way, and conform to the Durable notion of storage:control will not be returned to the caller until all the objects have been written to disk. The onlycurrent difference between the implementation of the two properties is that in the case of Persistent objects, a new thread is spawned to perform the work of storing the object to disk, allowingthe original thread to return immediately. This does provide faster performance for the user, butdoes not provide any 110 optimizations that might be available by delaying writes to disk, such asallowing some updates to be done only in RAM. This can be accomplished with an active threadinside each Storage Manager which periodically writes the cached data to disk.4.4 Dependent Invocations on Storable ObjectsWhen storable objects are part of a Dependent chain, the Raven system must delay writing theobjects to disk until the top-level invocation completes. Furthermore, the objects must be writtenatomically; i.e., either all the objects get written to disk, or none of them do.To support Dependent invocations on storable objects, each Thread object keeps a list of theStorage Managers for the storable objects it invokes upon in a Dependent chain. A pointer to thisCHAPTER 4— Oblect Storage: Details of the Durable and Persistent Properties 77list is kept in the Thread’s storage_chain instance variable. Each entry in the storage_chain(see Figure 17) is a structure which includes the dependentlD of the Dependent chain, the capof the Storage Manager, and a list of the objects which are managed by that Manager and whichhave been invoked upon during the current Dependent invocation chain. The Durable and Persistent post-handlers append the current invokee’s Storage Manager to this chain. If the Manager isalready on the chain, the current invokee is appended to the list of modified objects kept for theManager.struct STORAGE_INFOstruct STORAGE_INFO *next;struct STORAGE_INFO *previous;mt dependentlD;cap manager;LIST *objects;FIGURE 17. Format of struct STORAGE_INFO data structure.Normally, the TDBMmanager expects to perform the storage for a single Storage Manageras one transaction. In a Dependent chain, however, multiple Storage Managers must have theirdata stored by the TDBMmanager using the same transaction identifier. To accomplish this, thefollowing steps are taken when the top-level invocation of the Dependent chain completes:(1) A transaction identifier is acquired from the TDBMmanager.(2) For every Storage Manager in the storage_chain, the local cache of eachobject in the obj ects list for that Storage Manager is updated.(3) The Storage Manager is directed to write the list of cached objects to storage,CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 78using the transaction identifier acquired in step 1.(4) The TDBMmanager is directed to commit the transaction associated with thetransaction identifier.4.4.1 Remote Dependent Invocations on Storable ObjectsThe semantics for Dependency specify that all the objects in the Dependent chain will be storedtogether. This requires that when Durable objects in a Dependent chain are in different RavenWorlds, a two-phase commit protocol (or similar protocol) be used to ensure that all the objectsare written to disk atomically.In the current implementation, a two-phase commit protocol is not implemented, as it isbeyond the scope of this thesis. Instead, each of the Raven Worlds involved in a distributed transaction will write their data separately from the other Worlds, although atomically within eachWorld.4.5 Storage of Collection Class ObjectsThe Raven class library supports a variety of classes which are collections of other objects. Theseclasses all inherit from the Collection class, and include the Array, MemoryArray, List,Set, and String classes (see [1] for a full description of the Raven class library, including theCollection classes). The implementations of these classes often rely upon other classes (usually an instance ofMemoryArray at the lowest level). For example, the String class uses anMemoryArray object to store the actual characters of the string.This implementation presents a problem for object storage. Consider a Persistent Stringobject. If this object is encoded normally, the actual characters of the string will never be stored,as these actually reside in the MemoryArray inside the String. In fact, although the String itself isPersistent, the MemoryArray is not, and so the encoded data will contain a reference to the nilCHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 79object and not even to the MemoryArray which contains the characters. Similar problems exist forthe other Collection classes. MemoryArray has its own storage problem: its implementation is done directly at the C level, so normal Raven statements cannot be used to swizzle aninstance of MemoryArray.One solution is to attempt to use the Part-Of or Inherits references when designing the Col -lection classes. For example, the String class can indicate that the MemoryArray objectshould be Part-Of the String, so if the String is Persistent then the MemoryArray will be also.There are several problems with this approach, however. If Part-Of is used, then the Collect ion class object will be given a concurrency control lock, which will decrease the performanceof operations on the object. If Inherits is used instead, then the object will be stored in pieces ondisk, and multiple fetches will be required to load it into RAM. A more fundamental problem isthat although this scheme will work for the String class, it will currently not work for any of theCollection classes which are implemented by composing multiple Collection classobjects together. The Array class, for example, is implemented as a multi-way tree, usingobjects of the class FixedArray. At any given level, a FixedArray may contain elements of theArray or another FixedArray. Although the top level FixedArray used by the Array class can bespecified as being Part-Of the Array, there is no mechanism by which other FixedArrays placedinto the top level FixedArray can be declared as being Part-Of also. Therefore, the Part-Of treestops after one level, and parts of the Array will not be Persistent. One simple solution is to reimplement the Array class (and the other Collection classes) in such a way that Part-Of canbe used so all components of the class can inherit properties. Indeed, when a class is written allobjects which are used to implement the class should be defined as Part-Of. Another solution is touse the techniques described in Section 5.4 to implement the Collection class objects, whichwould allow the Part-Of relationships to extend downward as many levels as necessary to includeall the component objects of the Collection class object.CHAPTER 4— Object Storage: Details of the Durable and Persistent Properties 80To allow String objects to be properly stored, the String and MemoryArray classesoverride the enCodeData and deCodeData methods found in the Obj ect class with specialversions which will properly encode and decode the contents of a String or MemoryArray object.This scheme can be adopted for all the different Collection classes, although at present theenCodeData and deCodeData methods have been overridden only in the String and MemoryArray classes.4.6 Object Name ServiceOnce object storage has been implemented, some mechanism by which users can identifyand name objects must be provided, so that after a system reboot particular objects that have beenstored to disk can be reloaded. Otherwise, the user will never be able to find the objects stored todisk. Using ASCII (string) names is a natural convention for naming objects (as they are for naming Unix files), and much less cumbersome for users than requiring that they remember the GIDsof the objects which they are interested in. A rudimentary name server, which provides string toGID mappings, was developed to assist in the testing of the object storage system. Ideally, Ravenshould support a well-known persistent object accessible from the Raven System object whichprogrammers can use to provide their own name service.CHAPTER 5 Discussion and Future WorkThe design and development of the Raven property scheme is extensive but far from complete. Inparticular the implementation has brought to light many issues and possible directions for futureresearch.5.1 Property Scheme DesignThe Raven system has experienced only limited use, which has been confined to answering specific research questions. Until Raven is fully implemented and used as the basis for developingdistributed applications which rely on all aspects of the property scheme, it will be difficult toconduct a comprehensive evaluation of the Raven property scheme. It’s unclear how useful thedifferent properties and features (such as Part-Of) will be for applications programmers, and inparticular the usability of the currently unimplemented properties will not be fully known until thesystem is extensively used. In the testing which has been performed, the system behaves exactlyas specified in the property semantics. In particular, transactional processing can be accomplished81CHAPTER 5— Discussion and Future Work 82by providing objects with the Controlled, Recoverable, and Durable properties, and placing theobjects in Dependent relationships.There is one problem with the current mechanism for providing transactions, however. TheControlled property is designed to prevent concurrent access to an object by multiple threads.Now consider the following scenario, as shown in Figure 18. Thread T inside object A, performsa Dependent invocation on object B. It then performs a non-Dependent invocation on object C,which then makes a Dependent invocation on object B again. The invocation from A—>B is onetransaction, while the invocation from C—*B is another (the invocation from A—>C is not part ofthe first transaction, since C is not Dependent on A). The problem arises when the invocation onC returns: if a res tore statement is executed inside A, the instance data of B will be restored toa previous state as well. However, the state B will be restored to is inconsistent with the transaction C—*B, since the state of C (which will not be restored) may have relied on the state B was inat the time of the transaction.TA— II,IiIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIuII,II — —Inon-DependentDependent C CDependent[liii BFIGURE 18. Multiple Transactions Modifying a Single Object.CHAPTER 5— Discussion and Future Work 83This problem exists because of the particular interaction of the semantics of Dependent andControlled. The runtime system has a mechanism by which it can differentiate between invocations on an object done by the same thread but as part of different Dependent invocation chains,by using the Dependent id. to restrict access to the object. However, this does not solve the problem of the semantics, which allow this situation to occur. A solution is to introduce the semanticnotion of a invocation identifier (or transaction identifier) which is assigned to every invocation.Invocations in a Dependent chain would all have the same invocation identifier. The semantics ofthe Controlled property would then be modified to control access to an object based upon theinvocation identifier, and not the thread. This is also only a potential problem when the object Bhas the Recoverable property, but due to the orthogonality of the properties the system cannot useits knowledge of the properties of B to allow the above situation to occur when B is not Recoverable.When Raven becomes a platform for developing distributed applications, the propertyscheme may need to be expanded with the addition of new features and capabilities. Potentialfuture features include:• Property masking: The ability to “mask out” certain properties; that is, a mechanism by which an instance can refuse to be assigned a property which wasspecified at creation time or inherited from another object.• Selective inheritance: The ability to selectively bequeath a set of properties atruntime to an instance. Currently, property inheritance requires that all properties be inherited. An extension of this feature would allow any set of propertiesto be dynamically assigned to an object, by specifying the properties when theinstance variable is declared in the class definition.• Alternate policies for system properties: The ability for the user to choose fromamong a set of different versions of the system properties, which each providedifferent semantics. For example, the current semantics for Replicated onlyprovide weak consistency. The system could instead provide both weakly andstrongly consistent Replication, and allow the user to choose either policy forCHAPTER 5— Discussion and Future Work 84an object. Other possibilities include different storage policies for the Persistent property, each of which trade off between more immediate updates to diskand providing more updates in RAM.User specified property ordering: as mentioned in Section 3.2, the correctbehavior of the system relies upon a careful ordering of the property pre- andpost-handlers. Because of this, it is not possible for the user to create their ownversions of certain system properties, such as Controlled, since the systemmust acquire locks before any other work is done and release them only afterall other work has completed. To allow users to write their own versions ofControlled, the system could allow the user to specify the ordering of the preand post-handlers, thereby installing user written pre- and post-methods as thefirst and last handlers to be executed. A alternative to this scheme is to continueto hide the actual ordering from the user, but allow the user to load their ownproperty handlers in place of the existing system handlers. Such a schemewould integrate well with providing alternate policies for the properties: theuser could choose from among various system supplied properties, or chooseone of their own, to install as the Controlled handler, the Persistent handler, etc.5.1.1 Note on ReplicationWhen the Replicated property is implemented, it will become necessary to decide how Replicatedobjects should be stored. Should Persistent or Durable Replicated objects be kept on the local diskof all machines where they are Replicated, or perhaps only a subset of these machines? For correctness, the system only needs to keep one non-volatile version of the object, and requiring everynode to store the replicas wastes disk space and adds to the system overhead. For a read-mostlydatabase system consisting of one master any many clones, storage is only required (and perhapsdesired) on the master node. There may also be situations where “diskiess Ravenstations” areused (machines whose only disk is used for swap space, as exist in current Unix systems), inwhich case it is not possible to do any local storage. To provide such an implementation, however,violates the orthogonality of the properties, which requires that each of the replicas behave as if ithas all the properties of the original object (including Persistent or Durable, in which case theCHAPTER 5— Discussion and Future Work 85object must be stored to local disk). Even if the user is allowed to select different policies for thebehavior of the Persistent or Durable properties, each replica should use the same policy; theobject would not be truly replicated if each replica could use different policies.One option is to provide a new service, similar to Replication, which keeps the instance dataof a list of objects in synchronization with each other. As changes were made to one object, theywould be propagated to the others. This would allow an object to have many “replicas” each ofwhich could have different properties or policies for their properties.5.2 Implementation of Property SupportThe Raven runtime system is written primarily in C. This lack of reification has actually madeparts of the implementation somewhat difficult to accomplish: if an object has the Recoverableproperty, the system must be able to restore the object’s capability information, which is kept inthe capability structure and not as part of the instance data. This complicates the recovery process,as the shadow copies used by Recoverable must be augmented with a mechanism to recompute(or save and restore) the capability structure entries. There is also no technical reason why concurrency control locks and shadow copies cannot be implemented using Raven objects, except thatsuch an implementation would result in a drop in performance, as the overhead for performing aninvocation is greater than that of a normal C invocation (see [11).A possible future implementation is to move the capability information into the instancedata. This would provide several benefits:(1) The existing support for Recoverability could be used to provide recoverysupport when assigning objects to instance variables which are madepartof or inherits.(2) It would allow the user access to the information which is currently stored inthe capability structure, which is currently unavailable for the user’s inspecCHAPTER 5— Discussion and Future Work 86tion. Raven would therefore be more reflexive: the user could modify thisinformation, changing the object’s behavior accordingly. For example, theuser could select from among different objects to manage an instance’s locking and storage, depending on the behavior the user wishes the object to have,and set the appropriate instance variables to reference these objects. Propertybehavior could therefore be further customized on an instance by instancebasis.User defined properties are a particularly valuable tool, and present a future direction for thedevelopment of all Raven properties: implementing all of the current system properties as userproperties. This would force reification of the system properties, since they could no longer relyon C-level data structures, although C data types would still be required to interface with TDBM.Since user properties are supported through the use of special pre- and post-methods, a reification of the Raven system properties would require that all properties be supported with pre- andpost-methods. As with user properties currently, these methods would need to be invoked in aspecial manner to ensure that they are not invoked recursively when the invocations on the handler methods are made.The current implementation of user properties does suffer from a significant problem.Because the pre-methods for the user properties are executed after the Recovery pre-handler hasexecuted, if a restore statement is executed then the instance data used by the user propertieswill be reset to the state it was in prior to the method invocation. However, the user post-methodswill still be executed, and they may rely on information set by the pre-methods. The problem isfurther complicated by the mechanics of the restore statement: the invocation is not terminated, it instead continues on inside the method after the instance data has been restored. A solution to this problem is to force the system to return control to the caller when a restorestatement is executed. If all the Raven properties were implemented using Raven objects, thecomplete property state of the object could then be restored and the post-handlers would not needCHAPTER 5— Discussion and Future Work 87to be executed—it would be as if the invocation never took place. (An exception to this schemewould be for the Controlled handlers: locks must always be acquired first, and if any wereacquired, they would need to be freed; as such, the Controlled post-handler would still need to beexecuted.)The current implementation is also deficient in that it does not completely obey the specifiedsemantics for Dependent invocations. As described in Section 3.7, when a leave statement isexecuted the system will temporarily release (suspend) any locks held on the current object, incase the result will be provided by a thread executing a method within the same object. Correctexecution in accordance with the semantics of Dependency requires that any locks remain inplace until the top level invocation completes. Three possible alternate implementations thereforepresent themselves:(1) The system does not release any locks when a leave is executed and theobject is in a Dependent chain. This would require the programmer to ensurethat the result statement is executed from a separate object.(2) The system refuses to assign an object to an instance variable markeddependent when one of the object’s methods contains a leave. A runtime error would instead be generated.(3) The system suspends the current locks, but does not allow any invocation onthe object to fully complete until the suspended thread is resumed. A secondthread which accessed the object while the original thread was suspendedwould itself be suspended until the original thread completed the top levelinvocation of its Dependent chain. If the original thread did not execute arestore statement, the second thread would be resumed normally. If however the original thread executed a restore, the second thread would needto be aborted in some manner. The exact semantics and implementation ofthis scheme would need to be carefully worked out to ensure that orthogonality between the Recoverable and Controlled properties was maintained.CHAPTER 5— Discussion and Future Work 88Of these options, number (2) is the most consistent with the current state of the implementation. Since Dependent chains (and therefore transactions) are restricted to a single thread, the system should not allow a second thread to essentially become part of the transaction by providing areturn value for an invocation.Perhaps the most debatable implementation detail is the use of cluster locks for Part-Of clusters. Using cluster locks allows the runtime system to make assumptions about the states of theobjects in a cluster, but impacts the user by increasing the overhead associated with every implementation on an object in a cluster. Cluster locks are useful to enforce the consistency of a clusterwhen the cluster is to be migrated or stored to disk, but are not required for these purposes (e.g.,keeping cached versions of the objects in a cluster allows consistent object states to be written todisk). If cluster locks are to remain a part of the implementation, future enhancements to the runtime system should focus on improving the performance of invocations on Part-Of clusters bykeeping the amount of locking performed to a minimum. This can be accomplished by bypassingany local concurrency control lock for objects in a cluster, and bypassing the local and clusterlocks when one object in the cluster invokes a method on another object in the cluster.5.3 Object StorageThe object storage system provides reliable storage of objects to disk. Since TDBM was designedto provide efficient atomic storage, supplanting TDBM with a Raven-specific atomic storagescheme is unnecessary. There is currently no mechanism to perform garbage collection on theobject store; however the system does provide an “1 s”-like function to list the GIDs and classnames of all the objects in the store as a potential aid to a human user in cleaning out persistentgarbage. A mechanism for collecting distributed, persistent garbage created by Raven applications needs to be developed.CHAPTER 5— Discussion and Future Work 89To allow all the objects in a cluster to be loaded from disk into memory together, there is aclose relationship between Part-Of clusters and the object storage scheme. This is accomplishedby storing all the objects in the cluster together. However, some pieces of a Part-Of cluster may berather large, in which case the system will perform several large memory-to-memory copies anddisk transfers which could be unnecessary if the large object wasn’t the piece which was modified. Storing the objects together facilitates the retrieval of the entire cluster from disk, but it is notrequired. An alternate implementation is for the system to store each of the objects in a Part-Ofcluster separately on disk, but load all of the objects when any one object is fetched. This schemehas a further advantage in that it allows the user thread to begin execution inside the first fetchedobject, while the system fetches the remaining objects of the Part-Of cluster in parallel.In the current implementation of the storage model, an object’s Storage Manager is responsible for creating the full encoding of the object (adding the object’s capability information to theswizzled instance data) during object storage, while the GlDmanager extracts the capability information when the object is loaded in from disk. This requires that the GlDmanager and the StorageManagers agree on the general format of the encoded data, so that the GlDmanager can extract theinformation encoded by a Storage Manager. This is a potential liability, since any change in theencoding format must be reflected in two class implementations. An alternate implementation isfor the Storage Managers to pass the swizzled data to the GlDmanager for encoding instead ofperforming the encoding themselves. This problem is also addressed if the system is modified sothat the capability information is moved into the instance data, as the process of swizzling willproduce the full object encoding for extraction by the unswizzle routines.The implementation of Persistent property improves performance by performing the storagein parallel with the execution of the user thread. Performance could be improved significantly ifthe system could delay the parallel writes, allowing the object state to be updated many times inmemory before actually performing the storage. This could be accomplished by having an activeCHAPTER 5— Discussion and Future Work 90thread inside of every Storage Manager. When an invocation on a storable object finished, thecached version of the object would be updated in the Storage Manager and a boolean flag wouldbe set. The active thread would sleep a specified period of time, then awaken and check the flag tosee if the caches were modified, and write them to disk if they were. It would then go back tosleep for its time-out period.In the current implementation, the system makes a distinction between the case when a single object is stored or a cluster of objects are stored together: in the first case, the encoded data ispassed around in a single TDBMDatum object; in the latter, an array of TDBMDatum objects isused. The implementation could be simplified if the system were changed to always use an arrayof TDBMDatum objects when passing the encoded object data to and from the TDBMmanager. Ifonly one object is to be stored, the array would simply contain one TDBMDatum object. The format of object storage on disk could also be simplified by eliminating the format used by the special case of only a single object being stored to disk (see Figure 16).5.4 The Raven Collection ClassesProblems with the storage of Collection class objects were discussed in Section 4.5. Once amechanism for storing all the Collection classes is standardized (such as providing specializedswizzle and unswizzle methods for each class) one other issue becomes apparent: the Collec—t ion classes are not designed to allow the items actually in the collection to be considered Part-Of the Collection class object. When items are placed in a Set object, for example, there is nomechanism by which they can be described as being Part-Of the Set. This means that if the Setitself is Part-Of some other object, the items in the Set will not be part of the Part-Of cluster. Similarly, there is no mechanism to specify that the items in a collection should inherit properties orbe in a Dependent relationship. Property inheritance, Dependency, and Part-Of clustering stop atthe Collection class objects. One obvious example of where it would be useful to allowCHAPTER 5— Discussion and Future Work 91objects inside a collection to inherit properties is the implementation of a Name Server. The NameServer can be implemented using a Persistent Set. If the items in the Set could be Part-Of the Set,string names can be placed in the Set and become Persistent for the duration of the time they areentries in the Name Server.This issue can be addressed in one of several ways. The system can provide multiple versions of each of the Collection classes. For example, there can be a regular Set class, aSetPartOf class, a Setlnherits class, and a SetDependent class. These classes woulddiffer only in the how objects inside the collection would be treated. A second solution is to provide an extra parameter to the constructor methods of the Collection classes. Thisparameter would mirror the compiler keywords used to specify Part-Of, Inherits, and Dependent,and would indicate how the items in the collection should be viewed:• partof: The items in the collection should be Part-Of the collection.• inherits: The items in the collection should inherit the properties of theCollection class object.• dependent: The items in the collection should be Dependent upon the Collection class object.A third solution is for the system to treat the objects inside a collection in the same way the Cal —1ec t ion class instance is used. If the collection object is Part-Of another object, the objects inthe collection will be Part-Of the collection. If the collection object is invoked upon as part of aDependent chain, the objects in the collection will become part of the same chain. If the collectionobject inherits properties, then the objects in the collection will inherit properties as well.CHAPTER 6 Related Work6.1 Object-oriented SystemsThe problem of providing system services in object-oriented systems is not new, and manysolutions have been implemented. One scheme is to map traditional services into object representations. These system objects are crafted to integrate into the object model provided by theirruntime systems. Another scheme is to provide direct runtime support for various services toobjects in the system. There are many object-oriented languages which simply give the userobjects, without any real runtime system support. In such systems the user relies on the underlying system (Unix, etc.) for services as they would in a non-object-oriented language. Sometimesobjects can be exploited to make access to some services, such as persistence, more automatic.6.1.1 C++Several different approaches have been proposed for adding persistence to C++ objects [12],including some which even allow the incremental loading of object data [22]. This has the benefit92CHAPTER 6— Related Work 93of allowing C++ objects existing in any operating system to be persistent, but the consequence isthat no general operating system support can be assumed. These approaches rely on overloadingthe “>>“ and “<<“ operators to write the object data into streams to which files have beenattached. The basic mechanism is for a persistent class to write out a typed stream which includesa class identifier followed by the instance data. These schemes do not provide general persistencefor all objects, but provide mechanisms which programmers can use to make specific classes persistent. Since C++ classes aren’t real objects, there is no mechanism by which the system canautomatically traverse the instance data. Instead, the programmer is responsible for writing theload and store functions for each class by hand (although tools for generating these functionsautomatically could potentially be developed at an unknown cost). These schemes further requirethe user to manage a unique identifier (either a class name or numerical id) for each class which isto be persistent, and to develop a mechanism (such as a simple switch or jump table) to allow thecreation of new classes given the name or identity.6.1.2 ArjunaThe Arjuna system ([18], [23]) was designed to provide a C++ class library and system tosupport the building of robust distributed systems through the use of atomic transactions and persistent objects. Arjuna supplies the system support for atomic transactions (serialized concurrencycontrol and recoverability) and persistent objects through specific C++ classes organized into aclass or type hierarchy. Arjuna is currently designed to run on top of Unix. Unlike Raven, multipleversions of what are essentially the same class are required if one version is to make use of thesystem services for atomic transactions and persistence. Additionally the support for these services is not transparent to the programmer like it is in Raven. The use of transactions, for example, requires the programmer to explicitly instantiate an atomic transaction object and then usemethods of the atomic transaction object to start, end or abort the transaction within the object thetransaction is to affect. Because services are provided through methods inherited from systemCHAPTER 6— Related Work 94classes, the programmer does have the opportunity to subclass these system supplied classes inorder to customize the way they system handles persistence, recoverability, and concurrency control.6.1.3 NEXTSTEPPerhaps the most widely used object-oriented system is NEXTSTEP [17], which runs onhardware developed by NeXT Inc. as well as Intel 486 and Pentium platforms. NEXTSTEP is nota true object-oriented operating system, but provides a runtime system for Objective-C objectswhich sits on top of Mach and Unix. Programmers are required to manage the use of system services themselves. The programmer can make use of the traditional Unix system calls, but the recommended method for managing object archiving is through the use of special C functionsprovided in NEXTSTEP. These functions support the archiving and retrieval of objects to specially typed streams by writing to the stream the object class and it’s instance data. These functions can ensure that objects are only encoded once inside of each stream. By using thesefunctions, the programmer can read and write objects and object references without having towrite special functions for each class. Concurrent programming is possible in NEXTSTEP usingMach threads or the cthreads package. No system support for concurrency control is provided,however. It is the programmers responsibility to create mutex locks and manage their use amongany cooperating threads.6.1.4 ArgusThe Argus system [13] was designed specifically for use for developing applications thatrequire stable data storage in a distributed environment (such as banking systems). Argus provides special objects called guardians which effectively encapsulate data with a well definedinterface, and can also shield the data from the effects of network and host failures. Special atomicobjects, which contain locks to control against concurrent accesses, are used to synchronizeCHAPTER 6— Related Work 95accesses to guardians. Persistence is achieved by explicitly declaring part (or all) of the data keptby a guardian to be stable when the guardian is designed. Once the programmer has specifiedatomic and stable objects, the Argus system itself provides serializability and persistence withoutthe programmer having to explicitly make calls to acquire locks or write the data to storage. Othertypes of system services are not available, as the designers of Argus focused primarily on providing persistent, distributed atomic transactions, and developed special language and runtime system features to support such transactions.6.1.5 CronusCronus [5] is an object-oriented distributed computing environment developed by BBNLaboratories Inc., that is a capable of connecting groups of heterogenous computers. Among itsgoals are providing typical operating system services to a distributed environment, simplifyingthe task of writing distributed programs, building highly available systems, building scalable systems and integrating local and remote resources. To accomplish these goals Cronus employs theactive object model with access to objects managed by an object manager. Each machine has oneobject manager per object type and the object performs pre and post method processing and determines the method to execute. Although there are some routines that can be used to control theexecution of an object manager, these techniques apply to the whole collection of objects and notto individual objects. Raven provides a similar type of system control only it is on a per objectbasis. Cronus does provide a mechanism to allow individual objects to be customized. Eachobject has methods to allow user specific data to be attached to an object. The interpretation anduse of this data, however, is the responsibility of the application using the object. It is essentiallyadvisory information attached to the object that only has a meaning if the user of the objectchooses to examine the data and follow any usage guidelines associated with the data.CHAPTER 6— Related Work 966.1.6 GuideLike Raven, Guide [4] consists of both a programming language and a runtime system.Guide is designed for a multi-threaded environment with persistent synchronized objects whichsupport atomic transactions in a distributed environment. In contrast with Raven, all objects inGuide are persistent. Guide also has support for an atomic property for objects, but Guide requiresall updates to atomic objects to be within the confines of a transaction. Furthermore, atomicitymust be specified at object creation time, and cannot be changed afterwards. Invocations in Guideare accomplished by using the ObjectCall system primitive. This does allow the system to catchinvocations on objects, and potentially insert additional code before and after the method execution to provide services in a manner similar to Raven.6.1.7 SpringSpring [15] is a new object-oriented distributed operating system developed by Sun Microsystems, Inc. It uses objects to provide strong interfaces to data and services. Although one of theprimary motivations for Spring objects is the transparency they provide during distributed computations, Spring objects can also be used within a local address space. One of the key componentsof a Spring object is its subcontract [9], which defines the communications mechanisms the objectshould use at runtime. Different subcontracts can be created to provide different services. Forexample, the architects of Spring have developed subcontracts to provide object replication, caching, and crash recovery, among others. Subcontracts provide a powerful mechanism for customizing the way invocations are made on objects. However, they have some limitations as the basis fora general service providing scheme like Raven properties. First, subcontracts are not generallyused for local (same address space) invocations, as Spring’s Interface Definition Language (IDL)compiler will transform method invocations into calls on the object’s regular method table,bypassing the subcontract, when it can access the object directly. Second, subcontracts cannot beassigned to an object dynamically, to allow the object to change the services it receives; a particuCHAPTER 6— Related Work 97lar subcontract is used when the object is created and is thereafter used by the object. This alsocan lead to a “subcontract explosion” similar to the class explosion problem, as an object couldnot have both the replicated and crash recoverable subcontracts, for example, but would needsome subcontract that combined both services if both were desired. An intriguing notion would beto devise some mechanism to expand the abilities of subcontracts so that they could be composedtogether and dynamically changed at runtime ala Raven properties.6.1.8 COOLCOOL [8] is a distributed object-oriented layer developed for the Chorus system [21].Object descriptors in COOL include an attributes field, which is similar to the properties field ofthe Raven capability structure. COOL attributes can specify various properties of the object, suchas whether the object is persistent or has an active thread. If an object is persistent, then the entirecontext (address space) in which the object resides is also persistent, and the system will saveobjects and threads in the context at shutdown time (and checkpoint them during execution) forautomatic restart when the system reboots. COOL objects must have a special attribute to be globally known, otherwise they are accessible only from within their context. One main differencebetween COOL attributes and Raven properties is that attributes are assigned only at object creation time.6.2 SummaryRaven differs significantly from many of the languages and systems discussed in this sectionin that it avoids a class explosion when classes differ only in the underlying system support thatthey require. For example, an object of an existing class can be made persistent, recoverable andcontrolled simply by instantiating a new instance of that class with the desired properties insteadof programming a new class.CHAPTER 6— Related Work 98Unlike several of the systems described in this section, Raven’s support for system servicesis largely transparent to the programmer and requires little effort on the programmer’s part to utilize. Because services are provided automatically by the system, the programmer does not have tomanage their use. Raven avoids some of the performance problems inherent in other systemswhich provide services transparently, because Raven allows objects to be assigned properties on aper-instance basis. Objects only incur performance overhead for services they actually use.CHAPTER 7 ConclusionThis thesis has presented a new technique for providing system services to objects in an object-oriented system. This technique associates each system service with a property, which whenassigned to an object will allow the object to receive the associated service. It also allows the programmer to describe inter-object relationships, to provide object clustering and serialize invocations on objects.The design and implementation of the property scheme for Raven has shown that it is possible for an object-oriented system to provide services to objects:• transparently, without the need for the programmer to manage the use of theservices, and• on a per-instance basis, so invocation performance is directly related to thenumber of services the object receives.99CHAPTER 7— Conclusion 100The property scheme also provides atomicity of method invocations through the use of Dependentrelationships.Three aspects of the property scheme stand out above the others: Inherits references, Dependent references, and user properties. These features not only contribute to the uniqueness of theRaven property scheme, they are enabling features which vastly extend the flexibility and usability of the system, providing basic capabilities which can be built upon to achieve desired results.Bibliography[1] Donald Acton. Unified Language and Operating Systems Support for Parallel Processing. Ph.D. Thesis PHDO94-ACTO, Department of Computer Science, University of British Columbia, Vancouver,British Columbia, 1994.[2] Donald Acton, Terry Coatta, and Gerald Neufeld. The Raven System. Technical Report TR92-15,Department of Computer Science, University of British Columbia, Vancouver, British Columbia,1992.[3] Donald Acton and Gerald Neufeld. Controlling Concurrent Access to Objects in the Raven System. In1992 International Workshop on Object-Orientation in Operating Systems, IW000S ‘92. IEEEComputer Society Technical Committee on Operating Systems, September 24-25 1992.[4] R. Balter et al. Architecture and Implementation ofGuide, an Object-OrientedDistributed System. InComputing Systems, 4, 1991.[5] James C. Berets, Natasha Cherniak, and Richard M. Sands. Introduction to Cronus. Technical Report6986, BBN Systems and Technologies, Cambridge, MA, January 1993.[6] Barry Brachman and Gerald Neufeld. TDBM: A DBM Library with Atomic Transactions. Proceedings of the USENIX Summer Technical Conference, June, 1992, pp. 63-80.[7] Terry Coatta. Configuration Management Using Objects and Constraints. PhD Thesis PHDO94-COAT, Department of Computer Science, University of British Columbia, Vancouver, BritishColumbia, 1994.[8] Sabine Habert and Laurence Mosseri. COOL: Kernel Support for Object-Oriented Environments.Proceedings of ECOOP/OOPSLA 1990, October 21-25 1990,pp.269-77.[9] Graham Hamilton, Michael L. Powell, and James G. Mitchell. Subcontract: A Flexible Base for Distributed Programming. Proceedings of the 14th Symposium on Operating Systems Principles,Asheville, NC, December 1993.[10] Norm Hutchinson. Generalized Table Routines (unpublished).[11] The Institute of Electrical and Electronic Engineers. Information Technology—Portable OperatingSystem Interface (POSIX) Part 1: System Application Program Interface. IEEE Standard 1003.1-1990 (also available as International Standard ISO/IEC 9945-1, 1990).[12] Philippe Laurent and Nino Silverio. Persistence in C++. Journal of Object-Oriented Programming,Vol. 6, No. 6, October 1993, pp. 41-46.[13] Barbara Liskov. Distributed Programming In Argus. Communications of the ACM, Vol. 32, No. 3,March 1988, pp. 300-312.101102[14] Mary E.S. Loomis. The ODMG Object Model. Journal of Object-Oriented Programming, Vol. 6, No.3, June 1993, pp.64-9.[15] James G. Mitchell et al. An Overview of the Spring System. Proceedings of Compcon Spring 1994,February 1994.[161 Gerald W. Neufeld, Murry W. Goldberg, and Barry J. Brachman. The UBC OS! DistributedApplication Programming Environment. Technical Report 90-37, Department of Computer Science, University of British Columbia, Vancouver, British Columbia, January 1991.[17] NeXT, Inc. NeXTStep Reference. Addison-Wesley Publishing Company, 1991.[18] Graham D. Parrington. Reliable Distributed Programming in C++: The Arjuna Approach. Technicalreport, COmputing Laboratory, University of Newcastle upon Tyne, UK.[19] Stuart Ritchie. The Raven Kernel: a Microkemelfor Shared Memory Multiprocessors. Masters’ Thesis, Department of Computer Science, University of British Columbia, Vancouver, British Columbia,April 1993.[20] Mendel Rosenblum and John Ousterhout. The Design and Implementation ofa Log-Structured FileSystem. In Proc. ACM Symposium on Operating Systems Principles, pages 1-15, October 1991.121] M. Rozier et al. Chorus Distributed Operating Systems. Computing Systems, l(4):305-367, 1988.[22] John J. Shilling. How to Roll Your Own Persistent Objects in C++. Journal of Object-Oriented Programming, Vol. 7, No. 4, July-August 1994, pp. 25-32.[23] Santosh K. Shrivastava, Graeme N. Dixon, and Graham D. Parrington. An Overview of the ArjunaDistributed Programming System. Technical report, Computing Laboratory, University of Newcastleupon Tyne, UK.[24] Soley, R.M., Ed. Object Management Architecture Guide, Rev. 2.0, 2nd Ed. 0MG TC Document92.11.1, Object Management Group, 1992.[25] Sun Microsystems Inc.. XDR: External Data Representation Standard (RFC 1014). Network Information Center, SRI International, June 1987.103Appendix: Table of ContentsAppendix A. Data ‘I’ypes ............................................................................... 105A. 1 Capability Structure 105A.2 Property Values 107A.2. 1 Property Masks 107A.2.2 System Supported Properties 108A.3 Structures for Supporting the Recoverable Property 108A.3. 1 Shadow Structure 108A.4 Structures for Supporting the Controlled Property 109A.4. 1 Lock Status Values 109A.4.2 LockTypes 110A.4.3 Lock Structure 110A.4.4 Lock Information Structure 111A.5 Structures for Supporting Object Storage 112A.5. 1 Storage Information Structure 112A.5.2 Object List Entry Structure 113A.6 Unique Identification Structures 113A.6.1 GID Structure 114A.6.2 Location Information GID Structure 114A.6.3 Unique Identifier Structure 115A.7 Compiler Types 115A.7. 1 Property Set 115A.7.2 Variable Attributes 116A.8 Other Data Types 116A.8.1 Instance Variable Modifier Bits 116A.8.2 Defined Values for Object Storage 117A.8.3 Environment Variables 117Appendix B Class Definitions •..........................................fl.. ...........fl.....fl. 118B.1 Thread Class 118B.1.1 Public Interface 118B. 1.2 Private Interface 120B.2 StorageManager Class 120B.2.1 Public Interface 120B .2.2 Private Interface 120B.3 SMEntryClass 121B.4 GlDManager Class 121B.4.1 Public Interface 121B.4.2 Private Interface 122B.5 TDBMManager Class 122B .5.1 Public Interface 122B .5.2 Private Interface 123104B.6 TDBMDatum Class .123B.6.1 Public Interface 123B .6.2 Private Interface 124B.7 New Basic Methods 124Appendix A Data TypesThe implementations of the property scheme and of object storage required modifications toexisting data types used by the Raven runtime as well as the development of new data structures. What follows is an exhaustive list of all modified and new data structures used by theruntime, including those already presented in the thesis.Many of these data types and structures rely upon definitions of other data types andstructures. This additional definitions are generally not provided here.Al Capability StructureThis structure is also described in Figure 6.struct capability{Euncptr invoke;invoke is a pointer to the current invocation function to use.105Appendix A: Data Types 106cap id;id points to the current capability structure. It is useful when debugging asa sanity check for a capability pointer.cap is_a;is_a points to the Class object which this object is an instance of.cap parent;parent points to the object from which this object inherits properties. parent points to the nil object if we do not inherit properties.cap inh_root;inh_root points to the object which lies at the top of our current inheritence chain. This pointer points to ourself if we do not inherit properties.This allows us to detect inheritance cycles, such as attempting to inheritproperties from ourself.cap storage_manager;storage_manager points to our current Storage Manager object, or tonil if we do not have the Persistent or Durable properties.method_type method_type_to_use;method_type_to_use is used by the runtime system to determine if alocal version of a method exists. Some invocations on remote objects can(and should) be handled locally.struct gid *gid;gid points to a global identification structure (see Section A.6). In generalthis will point to NULL unless the object requires such a structure.voidp rw_lock;rw_lock is a pointer to the object’s concurrency control lock, or to NULLif the object is not Controlled. The structure of this lock is shown inSection A.4.voidp cluster_lock;cluster_lock is a pointer to the object’s cluster lock, or to NULL if theobject is not part of a Part-Of cluster.properties obj ect_properties;obj ect_properties contains the current property set of the object.u_char *data;Appendix A: Data Types 107data is a pointer to the instance data for the object.}A.2 ProperLy Valuestypedef u_long properties;A.2.1 Property Masks#define default_size OxlO#define inherited_mask Oxffff0000#define default_mask Ox0000ffff#define no_properties Oxffffffff#define basic no_properties#define persistent Oxfffffffe#define inherited_persistent Oxfffeffff#define durable Oxfffffffd#define inherited_durable Oxfffdffff#define recoverable Oxfffffffb#define inherited_recoverable Oxfffbffff#define controlled Oxfffffff7#define inherited_controlled Oxfff7ffff#define immutable Oxffffffef#define inherited_immutable Oxffefffff#define immobile Oxffffffdf#define inherited_immobile Oxffdfffff#define replicated Oxffffffbf#define inherited_replicated Oxffbfffff#define test_prop Oxffffff7f#define inherited_test_prop Oxff7fffff#define u_prop_i Oxfffffeff#define inherited_u_prop_i OxfeffffffAppendix A: Data Types 108#define u_prop_2 Oxfffffdff#define inherited_u_prop_2 Oxfdffffff#define u_prop_3 Oxfffffbff#define inherited_u_prop_3 Oxfbfffftt#define u_prop_4 Oxfffff7ff#define inherited_u_prop_4 Oxf7ffffffA.2.2 System Supported Propertiestypedef enum{LOCKING 0,PERSISTENCE,DURABLE,RECOVERABILITY,IMMUTABILITY,REPLICATION,IMMOBILITY,NUN_PROPERTIES} property_categories;A.3 Structures for Supporting the Recoverable PropertyRecoverability is accomplished by creating shadow copies of the object instance data prior toexecuting the method code. The format of the shadow structure has been modified to supportDependency.A.3.1 Shadow Structuretypedef struct ShadowStruct{struct ShadowStruct*next;next points to the next Shadow structure in the chained list of shadows.Appendix A: Data Types 109struct ShadowStruct *prevjous;previous points to the previous Shadow structure in the chained list ofshadows.struct capability *object;obj ec t is a pointer to the object for which this is a Shadow structure.u_long methodHash;methodHash is used for debugging purposes when dumping out theshadow list.mt depth;depth is the current call depth in the shadow chain.char * image;image is a pointer to the copy of the instance data of the object.mt invokeDepth;invokeDepth is incremented once for each invocation made on a Recoverable object in the current Dependent calling chain.mt dependentlD;dependent ID is the ID of the current Dependent calling chain.} Shadow;A.4 Structures for Supporting the Controlled PropertyEach controlled object has an associated concurrency control lock. Objects which are in a Part-Of cluster have a seperate cluster lock. Each thread maintains a list of the locks which it hasaquired.A.4.1 Lock Status ValuesEach lock which a thread holds (or is attempting to aquire) has an associated status.typedef enum{GRANTED = 1,Appendix A: Data Types 110Indicates the lock has been granted to the thread.WAITING,Indicates the thread is waiting to aquire the lock.SUSPENDED,Indicates the thread has been suspended and the lock temporarily relinquished by the thread due to a delayed result.WAITING_REACQUIRE,Indicates the thread is waiting to reaquire a lock that had been suspended.RETRY,Indicates that the thread should attempt to aquire the lock again. This willgenerally involve the thread reexecuting the locking portions of the propertypre-handlers.DELETED,Indicates that the specified lock was deleted, either becuase the object nolonger is Controlled or is no longer in a Part-Of cluster.LOCKING_ERROR,Not currently used in the implementation.LOCK_TIMED_OUTIndicates the lock could not be granted before the timeout timer expired. Apossible indication of deadlock.} LOCK_STATUS;A.4.2 Lock Typestypedef enuin{CLUSTER_LOCK = 1,INSTANCE_LOCK} LOCK_FAMILIES;A.4.3 Lock StructureThe concurrency control and cluster locks have the following structure.Appendix A: Data Types 111typedef struct LOCK{LIST granted;The list of threads which have been granted the lock.LIST waiting;The list of threads which are waiting for the lock.LIST suspended;The list of threads which have temporarily released this lock due to adelayed result.LIST reacquire_list;The list of threads which had temporarily released the lock and now wish toaquire it again. They are given preferrential access to the lock over threadswhich are simply on the waiting list.OSSemaphore semaphore;The semaphore which ensures that only one thread is manipulating the lockdata structures at a time.} LOCK;A.4.4 Lock Information StructureEach entry on any of the lock lists is a LOCK_INFO structure. Threads maintain a chain ofthese structures, one structure for each lock they have aquired, are waiting for, or are suspendedin.typedef struct LOCK_INFO{struct LOCK_INFO *next;Used to point to the next structure in the list (granted, waiting, etc.) we arecurrently on.struct LOCK_INFO *previous;Used to point to the previous structure in the list (granted, waiting, etc.) weare currently on.struct LOCK_INFO *sessionchajn_ptr;Appendix A: Data Types 112The next structure in the chain of LOCK_INFO structures held by the thread.struct LOCK *lock_ptr;A pointer to the lock.void *waiting thread;If the thread is currently suspended, it’s position is recorded here.behaviorLockType lock_type;The type of lock (read, write) we are holding/wish to hold.mt lock_holder;The P1D of the process.cap objectlD;The object which was was invoked upon.mt session_id;The identifier of the current session (unique for each thread).mt lock_depth;The current depth in the locking chain.LOCK_STATUS lock_status;The status of our attempt to aquire a lock will be placed here.mt dependentlD;The id of the current dependent chain.} LOCK_INFO;A.5 Structures for Supporting Object StorageEach thread maintains a list of Storage Managers for the objects that have been invoked uponin a Dependent calling chain. The entries of this list are of type struct STORAGE_INFO.A.5.1 Storage Information Structuretypedef struct STORAGE_INFO{Appendix A: Data Types 113struct STORAGE_INFO *next;The next entry on the list of Storage Managers.struct STORAGE_INFO *prevjous;The previous entry on the list of Storage Managers.mt dependentlD;The identifier of the current Dependent calling chain.cap manager;The Storage Manager object.LIST *objects;A list of objects managed by the Storage Manager which may have beenmodified during the current Dependent invocation chain. Each entry is oftype STOREL1ST_ENTRY, which is shown below.} STORAGE_INFO;A.5.2 Object List Entry Structuretypedef struct STORELIST_ENTRYstruct STORELIST_ENTRY *next;The next entry in this list.struct STORELIST_ENTRY *prevjous;The previous entry in this list.cap object;The object, managed by the Storage Manager, which was invoked upon.} STORELIST_ENTRY;A..6 Unique Identification StructuresAn object’s unique identifier is stored in three levels. This is partly a historical artifact, due tothoughts about how Raven would handle gids. Raven’s initial use of the term “gid” is somewhat of a misnomer, since it was simply used to describe object location information (which,Appendix A: Data Types 114prior to object storage, was sufficient to uniquely identify an object). The capability structureof an object contains a pointer to a struct gid.A.6.1 OlD Structurestruct gid(struct u_gid u_gid;The structure which actually contains the location information and uniqueidentification information.mt gid_len;Unused. Originally designed to hold the length of the encoded gid.char * encoded_gid;Unused. Originally designed to hold a pointer to an encoded version of thegid.A.6.2 Location Information OlD Structurestruct u_gidu_long hid;The P address of the host on which this object currently resides.u_long lid;The port number of the Raven World on which the object currently resides.struct unique_id uid;The unique identifier of the object.d_cap capability;A pointer to the capability for the object, i.e., the object’s location in memory on the Raven World specified by the hid and lid fields.char *class nameThe class name which this object is an instance of.Appendix A: Data Types 115A.6.3 Unique Identifier Structurestruct unique_id{u_long creator;The IP address of the machine on which the object was created.u_long world;The port number to which the Raven World on which the object was createdwas bound.u_long generation;A counter which is incremented once for each incarnation of a Raven World.u_long name;A counter which is incremented once for each gid which is assigned by anincarnation of a Raven World.A7 Compiler TypesA.7.1 Property Settypedef enum{persistent = 0,durable,recoverable,controlled,immutable,immobile,replicated,test_prop,u_prop_i,Appendix A: Data Types 116u_prop_2,u_prop_3,u_prop_4,phaseout,lastProperty} Properties;The phaseout property is used to warn the user that he has selected a property whichis no longer supported by the system.A.7.2 Variable Attributestypedef enum{stat=O,meta,copy,partof,inherits,dependent,indirect,public,las tVarAttribute} VariableAttributes;A8 Other Data TypesA.8.1 Instance Variable Modifier Bits#define PT_DEPENDENT 0x8#define PT_INHERITS OxlOAppendix A: Data Types 117#define PT_INDIRECT 0x20#define PARTOF_MASK_VAL 0x40#define PT_PARTOF (PT_DEPENDENT I PT_INHERITS IPARTOF_MASK_VAL)A.8.2 Defined Values for Object Storage#define GENERATIONSTRING “.sysGENERATION”#define GENERATIONSTRINGLEN 15#define DBMPATH “/raven/export r/gener±c/storage”A.8.3 Environment VariablesRVSTORAGEPATH Directory into which TDBM will store objectsRAVENWORLD Port number to bind to when starting RavenAppendix B Class DefinitionsMany new classes were created during the implementation of the object property scheme.Additionally, many existing classes were modified to support the new property scheme. Theseclasses are presented here.Some of the interfaces listed here as private interfaces are private simply in that they arenot to be known by the general programmer. They are not necessarily private in that they arefunctions which are only used from within an instance of that class. Many “private” behaviorsare invoked by the runtime system, or from other objects which are used to provide support forproperties.B.1 Thread ClassB.1.1 Public Interfaceclass Thread uncontrolled{118Appendix B: Class Definitions 119pid, stack_size : Int;name, instance: Cap;method : String;prio : Int;session_id, session_chain, lock_depth : Int;shadows, callDepth : Int;function_chain : Int;storage_chain : Int;remoteResumeStatus : Int;constructor (pprio: Int);behaviour starter(...);behaviour start(...) : Int;behaviour startAsSystemProc(...) : Int;behaviour attach(obj:Cap) : Int;behaviour getPid() : Int;behaviour threadRunnable() : Int;behaviour kill() : Int;behaviour threadName() : String;behaviour resume() : Int;behaviour stackSize() : Int;behaviour suspend;behavior sleep(duration:Int);behavior startNetwork;behavior monitorLocks ;behav traceEnable(minSize: Int);behav traceDisable ;behav traceStackOnly;behav traceDumpOnFill 0;behav traceDumpOnExit 0;behav traceDurnp 0;}Appendix B: Class Definitions 120B.1.2 Private Interfaceclass Thread{behavior rernoteDependentWorker(handler : mt1resumeStatus : Int);behavior remoteRestoreO;behavior remoteRestoreFunctions 0;}B.2 storageManager ClassB.2.1 Public Interfaceclass StorageManager controlled{$objects : F±xedArray[cap];$size : Int;$entries : Int;constructor();behav updateCacheOfObject(obj : cap, doWrite: mt1now : Int) writelock;behav manageObj ect (obj cap);behav uninanageObj ect (obj : cap);behav writeToStorage(writeNow : mt1 id : Int);}B.2.2 Private Interfaceclass StorageManager{behav loadDataFromCache () readlock;behav setCacheValue(datum : cap) writelock;Appendix B: Class Definitions 121behav privateWrite(id : Int) private;behav getCap(uidPtr : Int) : cap private;behav privateDelete(entry SMEntry) private;behav setUpEntry(obj : cap, entry cap) private;behav entriesHaveSameValue(el : cap, e2 : cap) : mt private;}B.3 SMEntry ClassThis class is used only internally by the Storage Manger. Its interface is not visible to any otherobject.class SMEntry <- Object{$dataPtr : mt public;$dataLen : mt public;$objCap : cap public;behav loadData() private;}B.4 GlDManager ClassB.4.1 Public Interfaceclass GlDManager controlled{table Int;nameList : cap;creator : Int;world Int;generation : Int;name Int;Appendix B: Class Definitions 122constructor();behav getGID(obj : cap);behav fetch(obj : cap) : mt writelock;behav becomeVolatile(obj cap) writelock;behav listNaines() readlock;behav findNaine(name : String) : cap writelock;behav adc3Name(name : String, obj : cap) : mt writelock;behav deleteName(name : String) : mt writelock;}B.4.2 Private Interfaceclass GlDManager{behav capFromGlD(uID : Int) : cap writelock;behav findForRernote(uID : Int) cap writelock;}B.5 TDB1anager ClassB.5.1 Public Interfaceclass TDBMItanager controlled{dbm : Int;namedbm : Int;recovery : Int;constructor ;behav shutdown;behav getGeneration() : mt writelock;Appendix B: Class Definitions 123behav getTID() : mt readlock;behav preComrnit(id : Int) writelock;behav commit(id : Int) writelock;behav store(datum cap) writelock;behav storeForTransaction(id : mt1 datum : cap) writelock;behav fetch(datum : cap) : cap readlock;behav delete(datum : TDBMDatum) : mt writelock;behav dumpObjects() readlock;behav storename(datum : TDBMDatum) writelock;behav fetchname(datum : T]DBMDatum) : cap readlock;behav deletename(datum : TDBMDatum) : mt writelock;behav dumpnames() readlock;}B.5.2 Private Interfaceclass TDBM4anager{behav privateStore(translD : mt1 datum : cap) nolock;}B.6 TDBMDatuin ClassB.6.1 Public Interfaceclass TDBMlDatuin{keydptr : Int;keydsize : Int;valuedptr : Int;valuedsize : Int;behav setKey(dptr : mt1 dsize : Int);Appendix B: Class Definitions 124behav setValue(dptr : mt1 dsize : Int);behav getKeyPtr() : Int;behav getValuePtr() : Int;behav getValueSize() : Int;}B.6.2 Private InterfaceThere are no additional methods or instance variables beyond what is specified in the publicinterface.B.7 New Basic MethodsThe Obj ect class was extended to include several new methods to do the following:• Assign the object a GID.• Swizzle and unswizzle the instance data.• Provide support for the user defined properties.These methods were added to the list of basic methods supported by the Obj ect class. Assuch, they do not appear in the interface definition of Obj ect.behavior assignGID;behavior sWizzleData() : Int;behavior unsWizzle]Data(data : Int);behavior preUserl(dependentlnvoke : Int);behavior postUserl(dependentlnvoke : Int, isDependentRoot : mt1hasProp : Int);behavior preUser2 (dependentlnvoke : Int);behavior postUser2(dependentlnvoke : mt1 isDependentRoot mt1hasProp : Int);behavior preUser3 (dependentlnvoke : Int);Appendix B: Class Definitions 125behavior postUser3 (dependentlnvoke : mt1 isDependentRoot : Int,hasProp : Int);behavior preUser4(dependentlnvoke : Int);behavior postUser4(dependentlnvoke : mt1 isDependentRoot : mt1hasProp : Int);

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052087/manifest

Comment

Related Items