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

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata


ubc_1994-0496.pdf [ 2.36MB ]
JSON: 1.0052087.json
JSON-LD: 1.0052087+ld.json
RDF/XML (Pretty): 1.0052087.xml
RDF/JSON: 1.0052087+rdf.json
Turtle: 1.0052087+rdf-turtle.txt
N-Triples: 1.0052087+rdf-ntriples.txt
Original Record: 1.0052087 +original-record.json
Full Text

Full Text

ObjectProperties: A MechanismforProviding RuntimeServices to Objects in a Distributed SystembyDavidFinkeisteinB.S. (MathematicalandComputationalSciences) StanfordUniversity, 1986A THESIS SUBMITTEDINPARTIALFULFILLMENT OFTHEREQUIREMENTFORTHEDEGREEOFMASTEROF SCIENCEinTHEFACULTY OF GRADUATESTUDIESCOMPUTERSCIENCEWe acceptthis thesis as conformingto the required standardTHEUNIVERSITY OFBRITISH COLUMBIAOctober 1994© DavidFinkelstein, 1994In presenting this thesis in partialfulfilment of the requirementsfor an advanceddegree at the University of BritishColumbia, I agree thatthe Library shall make itfreely available for reference andstudy. I further agree thatpermission for extensivecopying of this thesis forscholarly purposes maybe granted by the head of mydepartment or by his or herrepresentatives. It is understoodthat copying orpublication of this thesis forfinancial gain shall notbe allowed without my writtenpermission.Department ofCocu—r-2.cicJC.GThe University of BritishColumbiaVancouver, CanadaDate QcçZ V2DE-6 (2/88)AbstractObject-oriented systems are increasinglyused as a means to develop distributedapplications.Objectsprovide a natural unitofencapsulationforremote data, and the systemcanmakeremote invocations transparent to localusers. Generally the underlying systemprovides avariety ofservices to objects in the system,such aspersistence orconcurrencycontrol, whichare usedby developers ofdistributed applications.There are problems with existingmechanisms forproviding suchservices, however:they may requiretheprogrammerto design adifferent subclass ofeach userclassforevery service available, limit the choicesofservicesavailable, or inhibit performanceby providing services to all objects evenwhen not everysevice is needed. The work in this thesisattempts to solve these problems througha newmechanism forproviding servicesto objects calledproperties. Properties allowservices to bedeliveredtransparently to objectson an as-requestedbasis. Additionally,a mechanism fordescribinginter-objectrelationshipshasbeenincorporatedintothepropertyscheme, allowingpropertiestobeusedtoprovidecomplexservices such as atomic transactions.Propertiesweredeveloped forthe Raven distributedsystem and language developedin the DepartmentofComputer Science at the UniversityofBritish Columbia.11Table ofContentsAbstract.iiTable ofContentsiiiListofFiguresvAcknowledgmentviChapter 1 Introduction11.1 The SystemInterface Problem11.2 Providing Services in Object-orientedSystems 21.3 Thesis Statement41.4 Outline5Chapter 2 Design ofthe Object Property Scheme72.1 Introduction to the Raven System72.2 Property Scheme Design Goals82.3 Selecting Services viaProperties122.4 Property Behavior Semantics162.5 Assigning Properties to Instances202.6 Inter-Object Relationships222.7 CombiningProperties29Chapter 3 Implementation ofthe Object Property Scheme313.1 Data Structures forProperty Support313.2 Providing System Services ThroughProperties 343.3 Dependent Invocations373.4 Property Inheritance423.5 Part-OfClusters473.6 Self-Invokes513.7 Parallel Invocations and PropertySupport 533.8 User Properties573.9 Status ofthe Implementation ofProperties59Chapter 4 Object Storage: Detailsofthe Durable and PersistentProperties604.1 Object Storage Overview604.2 Storage Model634.3 Implementation Details674.4 Dependent Invocations on StorableObjects764.5 Storage ofCollection ClassObjects784.6 ObjectName Service80Chapter 5 Discussion and FutureWork815.1 Property Scheme Design815.2 Implementation ofPropertySupport855.3 Object Storage885.4 The.Raven Collection Classes90111Chapter 6 RelatedWork926.1 Object-orientedSystems926.2 Sunnary97Chapter 7 Conclusion99Bibliography101ivListofFiguresFIGURE 1. Assigning properties in the class definition21FIGURE 2. Assigning propertiesby usingpnew 22FIGURE 3. Class definition withinstance variablesshowing inter-objectrelationships.23FIGURE4. Some ofthe objects comprisingamail message,justpriorto beingassignedto the MAIL MESSAGE object.26FIGURE 5. After assignment, objects have newproperties and behaveaccordingly.27FIGURE 6. Object capability structure32FIGURE7. An Example ofRecoveringa Property Inheritance Assignment 44FIGURE 8. Objects in aPart-OfCluster48FIGURE9. GID Structure62FIGURE 10. Object StorageModel63FIGURE 11. Storage ManagerRole64FIGURE 12. TDBM ManagerRole65FIGURE 13. Gifi ManagerRole66FIGURE 14. Formatofencodedbufferin memory 68FIGURE 15. Formatofa fully encoded object71FIGURE 16. Formats ofdata storageon disk73FIGURE 17. FormatofstructSTORAGE_INFOdata structure 77FIGURE 18. Multiple TransactionsModifying a Single Object82vAcknowledgmentFirst, I’dlike to thank my family, especiallymy parents, for the support (both financialandotherwise) they’ve given me these pastthreeyears.I’dlike to thankDonActon andTerry Coatta,my Partners in Crime (orRaven, as it were) forall the assistance they’ve provided me, from simply kickingaround ideas to help in trackingdown those elusive bugs. Withoutyou two around, Ihad no other option but to graduatemyself. I’d also liketo thank my supervisors, NormHutchinsonand GeraldNeufeld, notsimply because you’re supposed to do that sort ofthing inyourAcknowledgment, but fortheguidance they’ve given me especially during thoselong meetings where I’d come up withstrange scenarios involving objectrelationships. Thanksalso to thosewhohelped during theredesign ofRaven, by contributing their ideasand providing me with feedback on mine:StephanMueller, RaymondNg, andJimThornton. Andaspecialthanks to SteveLoving,whohelped encourage me in my dreamto returnto school.viCHAPTER 1Introduction1.1 The System Interface ProblemComputer operating systems are designed to presenta virtual machine to the programmers andusers ofthe computer. The operating systemprovidesan interfacethroughwhich applicationscanmake requests to and receive services from the operatingsystem. For example, operating systemsusually provide a file service. By calling operatingsystem routines, applicationscan find, read,and write files in the system. Many modern operatingsystems have a microkernel architecture,where the actual set ofservicesprovided by the operating system kernelitselfare small. Instead,special servers provide the additional functionalityof file service, networking, etc. Althoughtheimplementation is different, the basicmodel presented to the programmeris thesame as thatprovidedby more monolithic operating systems.Unfortunately for developers ofdistributed systems, particularly systemsdesigned formulti-threaded environments, the operatingsystem interfaces can vary widely betweendifferent1CHAPTER 1 — Introduction2operating systems. Forexample, the interfaceusedbyBSD Unix (or systemsbasedonBSD Unix,such as SunOS) differs from that ofUnix SVR4. Anyone who hasattempted to port applicationsfrom one environment to the other can attest to the problems whichcan arise due to the differences in system calls. The interfaces to Mach and OS/2 are similarlyincompatible with those ofthe other operating systems mentioned. These differences makethe development of distributedapplications more difficult. Attempts have been made to createa standardized interface for Unixsystems. Forexample, manyUnix systems supportthe POSIX applicationprograminterface [11],although most applications are still not written to this standard.Anothermechanism forproviding a standardizedinterface is to usean object-orientedenvironment. Object-oriented systems allow the applications programmersto use a standardizedinterface to the object system. Since objects interfaces provide strict, well-structuredaccesses to theobjects, theymake a naturalchoice forproviding thebasis ofauniformsysteminterface. Itis necessary to port the object environment to each different platform, but once thishas been accomplished, all user applications should be portable between platformswith a simple recompilation.Common object models have also been proposed and developed,primarily for the needs ofobject-orienteddevelopers [14], [24].1.2 Providing Services in Object-orientedSystemsProgramming to a common object environmentsimplifies the development of applications inadistributed system. However, there remainsthe issue ofexactly how user objects in the environment will receive system services. Thisis not a trivial question, as objects can require numerousservices ranging frompersistenceto concurrency control to recoverability.CHAPTER 1 — Introduction3One mechanism is for the system to simply provide“system call” methods. In this scheme,object methods replace the system calls foundin other operating systems such as Unix.This canbe accomplishedin one oftwo differentways:(1) The system includes systemobjects which are responsibleforproviding services to userlevel objects. Forexample, objectswhichrequire concurrencycontrol can invoke methods on aobjectwhich coordinateslocking (e.g., aLockManagerobject):LockNanager.lockMe(self);would ask the LockManagerto lock the currentobject.(2) The systemprovides classes fromwhichobjectscan inheritbehaviors whichcorrespondto the services the object needs.For example, objects whichrequire persistence can inheritmethods froma Storageclass:self . storeMeToDisk;would store the contents ofthe object to disk.One system which uses this technique is Arjuna([23], see Section 6.1.2). This system callmechanismhas the advantage thatobjectscanbe tailoredto receive only those servicesthey need.However, it suffers froma number ofproblems. First, it requires the programmerto manage theuse ofthe services. The programmermust invoke the appropriate methodsto acquire and releaselocks, store the object to disk,etc. Although it’s notnecessarily abadthing to make programmersresponsible formanaging the services theyuse, it does increase the likelihood oferrorsdue to theprogrammerneglecting to releaselocks and from similarmistakes.This mechanism can also leadto the problem ofclass explosion:since the system provides multiple services,multiple versionsofeach userclass mightbe required[1].Anothermechanismforprovidingservices to objects in an object-orientedsystem is toprovide a set ofservices automaticallyto all objects. In such a system, every objectwould be persistent, controlled againstconcurrent accesses, etc. This schemehas the advantage that theCHAPTER 1 — Introduction 4programmerdoesn’thave tobe concernedwithmanagingthe use ofsystemservices, they areprovided transparently by the system. For example, the Guide system ([4}, see Section 6.1.6) provides persistence to every object in the system. The majordrawbackofthis approach is a lack ofperformance. Since every object receives services, the system must devote time and resourcesupon every objectinvocation.Programmers and users ideally require a system which combines the best features of bothmechanisms described above. Users ofclasses need to create instances that can receive any combination ofsystem services, yet class designers shouldn’tbe required to include support for everypossible service ausermightdesireinthe class implementation, norshouldthereneedto existdifferent versions ofeach class for every combination ofservices 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 controlledagainstconcurrentaccesses, orpossiblyboth, yetobjects whichdo notreceive services shouldnotsuffer any undue performance penalty. Additionally, such a system should be complete enough tosupport distributed atomic transactions, arigorous measure oftheusability ofa system.1.3 Thesis StatementAn object-oriented operating system can associate each system service with aproperty, 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 oftheobject’s property set. The researchpresented in this thesis attempts to show that:It is possible to identify and support a set ofsystem services through object propertiessuch that:the semanticsofthe system servicesprovidedare independentfrom the others;CHAPTER 1 — Introduction5• services areprovidedon an instance-by-instancebasis;• services areprovidedautomaticallyto an instance upon each invocation, without requiring any code in the class to use theservice;• the setofservicesprovided to an instancecan change dynamically throughoutthe lifetime ofthe object;• the usercan augmentthe setofservices available;• inter-object relationships can be described,allowing the system to providecomplexservices thatspan invocations on multipleobjects;• the services available, togetherwith inter-object relationships, is sufficientlycomplete to supportdistributed atomic transactions yetdoes not limit the system to supportonlysuch transactions.1.4 OutlineA descriptionofthe objectproperty scheme, including semanticsfor each systemsupportedproperty, is found in Chapter 2. This chapterincludes ageneral overviewofRaven, theobject-oriented operating system the property scheme wasdeveloped for, and discusses how the propertyscheme is used by Raven to provide servicesto objects. This chapter also discusses other aspectsofthe property scheme, such as the various inter-objectrelationships thatwere developed.Details ofthe implementation of theproperty scheme are given in Chapter 3.This chapterdescribes how services are provided toobjects via properties. Certain issuesand problemsencountered during the implementationare also discussed.Chapter 4 describes the basic objectstorage service which was developed.It discusses thevarious issues confronted when designingthe service, andprovides details oftheimplementation.A discussion ofadditional issues, andthe future work which canbe done to address them,can be found in Chapter 5. Many ofthe issues discussed in this chapterdid not become apparentuntillaterstages ofthe implementationorduring testing.CHAPTER 1 — Introduction6Examples ofotherobject-oriented systems, and themechanisms they use for providingservices to objects, are presented in Chapter 6.Conclusions arepresented in Chapter 7. A listofthedatastructures usedby the runtimesystem to support properties is given in Appendix A. Class definitionsfor the various classes whichwere developed or modified in the course ofimplementingthis thesis are given in AppendixB.DesignoftheObjectPropertyScheme2.1 Introduction tothe 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 environmentfor exploring issuessurrounding distributed andparallel applications onbothmultiprocessorand distributedprocessorplatforms. The development of the Raven system isan on-going project in the DepartmentofComputerScience atthe University ofBritish Columbia.In addition to the workdescribed inthisthesis, Raven has been primarily used to investigateissues in parallel and concurrentprogramming [3] and to explore issues in configurationmanagement ofdistributed systems[7].The Raven language is an object-oriented languagewith a syntax similar to that of C. Thelanguage contains specialized constructsto directly support parallel executionofmethod invocations, some of which have repercussionsfor the various properties, as discussed in Section3.7.The Raven runtime system providessupport for objects written in the Raven language.Though7CHAPTER 2— Design oftheOblectPropertyScheme8the syntax ofthe language is stable, significant enhancementsto 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 inC. Raven currently runs in itsthreads environment under Unix on Sun and MIPS workstationsin a distributed environment.Raven is also running in a parallel environment under Mach3.0 on a 20-processor Sequentmachine. A microkernel running on multiprocessor MC88100 workstations isbeing developed tosupport the Raven system in a native environment [19]. A detailed overviewofRaven, includinga description ofthe language semantics, can be found in [1].Eachincarnation ofthe Raven environmentis defined as aRavenWorld.EachRavenWorldhas a corresponding UDP port number on the machine it is runningthrough which it communicates withotherWorlds. A RavenWorld is uniquely identifiedby itshostidentifier and portnumber. Different Raven Worlds, even those on the same local machine,are normally isolated fromeach other until the Worlds are informed ofeach other’s existence.2.2 Property Scheme Design GoalsThe property scheme was designed witha number of goals in mind. The primary goal ofthescheme is to provide a mechanism by whichservices can be provided transparentlyto objects onan instance-by-instance basis, in a flexibleyet powerful way that does not limit the systemor theprogrammer to a small set ofpossibleservices. The scheme was designed witheach ofthe goalsoutlinedbelow in mind.CHAPTER 2— Design ofthe ObjectPropertyScheme92.2.1 Orthogonality of Property SemanticsWhenproperties are designed so thattheirsemantics are independent fromeach other, the properties are defined to be orthogonal to one another. The necessary strictnessofthe semantics has significant impact on the implementation ofproperties:properties can be designed, developed, andtested separately, and then added to the system without any concernthat they might cause sideeffects. This is true whether the property being added is new, or simplya new implementation ofan existing property.Orthogonality is primarily useful because it makes the semantics easierto understand. Theprogrammer doesn’t have to be concerned with any changes to thesemantics due to propertyinteractions. When property semantics are independent, programmers canspecify any combinationofproperties for an object with the knowledge that the object’s behaviorwith respectto eachpropertywill always be correct. It is also an enabling feature; that is, whenproperties areorthogonal, it allows many other features to be included in the system, such asdynamic property assignment.2.2.2 PropertiesAssignable DynamicallytoAny InstanceTo combat the problem of class explosion, the schemewas designed to allow properties to beassigned on aper-instance basis. In this way, sub-classesdo notneed to be created simply to gainthe benefit of additional property behaviors.By allowing objects to receive services ona perinstance basis, performance can be improved:objects can receive only those services whichtheyneed, and so suffer no performance overhead relatedto services (such as persistence or concurrency control) whichthey may notrequire.To further enhance the usefulnessof the system, another goal of the design was toallowproperties to be assigned dynamicallyto objects, even after the object had been created.Sinceproperties are orthogonal, adding new propertiesto an object after instantiation can’tcreateCHAPTER 2— Design ofthe ObjectPropertyScheme10unwanted side-effects. Dynamic property assignmentcan be useful especially in a client-serversystem. Consider an object server which creates objectsfor use by various clients. Different clients may require objects with different setsofproperties. With dynamic property assignment,theproperty set desired doesn’t needto be passedto theserver. Also considerthe situationwhereoneapplication creates an object, a second applicationwantsto use the object, butthe second application needs the object to haveproperties whichweren’trequiredby the first application. Forexample, an objectrepresenting ablockoftextcreatedbyatexteditorcanbe referencedby thebodyofa mail message. Although the text editor may not have createdthe text object with the persistentproperty, the mail handler can ensure that the objectis persistent by dynamically assigning itthatproperty.2.2.3 Transparency of UseTransparency implies that aprogrammercan implementclasses withoutincluding special code touse properties. By placing all support for properties intothe runtime system, the programmer isfreed fromtheresponsibilityofasking forsystemserviceseachtime they are needed. This declarative model has advantages over the procedural model.The possibility of program errors withregards to receiving services fromthe system is greatly reduced, since the programmerdoes nothave tobe concernedwithacquiring andreleasinglocks, writingobject stateto disk,etc., ordetermining when such events should occur.Additionally, even though the user ofa class can assignany properties to instances ofthe class, theprogrammer doesn’t have to be concerned withsupporting all the properties in the method code(an unrealistic expectation, especiallygiven that theproperties available may changeover time). This ties in well with orthogonality:a user ofa classcancreate an instance ofthatclass withany desired setofproperties, withoutworryingabout sideeffects between the properties desired orbetween those desired by the user andany additionalproperties specified by the class designer.CHAPTER 2 — Design oftheOblectPropertyScheme112.2.4 Supportfor Atomic TransactionsOne primary goal of the system is for theproperty scheme to be powerfulenough to supportatomic transactions. It was a furthergoal that this could be accomplishedwithout having todevelop a special service devotedspecifically to serializing invocations,but instead build theatomic transaction supportusing moregeneral services.2.2.5 Additional Supportfor DistributedComputingSupporting atomic transactionsallows the developmentofdistributed databasesand other robustapplications. More simple applications, suchas mail agents, do not requirethe same level ofsystem support as a database. Other applications,such as name services, could benefit fromsystemservices which allow them to be highly available(e.g., some mechanism by which they could bereplicated). As the property schemewasbeing designed, one ofthe goals wasto provide sufficientservices so that a wide varietyof applications could be built. Additionally,the system needed tocontinue to supportthe experimentsbeingconducted in the areas ofconcurrentprogrammingandconfiguration management.2.26 User ExtensibilityTo this point, properties have been describedas a means ofproviding system-supportedservicesto objects. The logical extensionofthis design is to extend properties so theycan be used toprovide objects with user-supported services.Such an extension allows usersto develop their ownservices withoutthe needto modifythe runtime systemto support them.This is extremely important, because the system propertiescould never provide all the servicesdesired by users. It alsoallows potentially new systemservices to be designed andtested at the user level beforebeingincorporatedinto the runtimesystem.CHAPTER 2— Design ofthe ObjectPropertyScheme122.3 Selecting Services via PropertiesEach of the goals enumerated above are importantfeatures for inclusion in Raven.To be trulyuseful, however, theproperties shouldprovidedesirablebehaviorswhenusedin combination,andnot simply in isolation. On the surface, this goal mayappear to be incompatible with the goaloforthogonality. However, useful behaviorscan be viewed as being composed of other, simplerbehaviors. For example, an atomic invocationon an object requires recoverability, concurrencycontrol, and persistence ofthe object state. Atomic transactionsinvolve invocations on multipleobjects and place additional requirements on the system,but it was a primary goal to design aproperty scheme that allowed atomic invocations tobe performed by combining several properties together. If a new property had to be created foreach desired behavior (e.g., if the systemneeded to support recoverability, concurrency control,persistence, and an “atomic invocation”property), then the number of properties could quicklygrow to an unmanageable number (anundesirable property explosion, although growth wouldbe linear and not exponential, as in classexplosion), with a corresponding increase in the likelihoodthat the property semantics could notbedesignedin anorthogonal manner. Forthesereasons,considerabletimewas spent selecting theproperties and developing their semantics.The process ofproperty selectionbeganwithan examinationofa atomic transactions, toseeifthey could be supported by composingseveral services together. Fundamentally,atomic transactions can be broken downinto three components:• Serializability of invocations: If multipletransactions invoke methodson thesame objects, there mustbe some serial orderingofinvocations so thatto eachtransaction it appears that it has exclusiveaccess to the objects forthe durationofthe transaction.• Recoverability: In the eventof abnormal method termination (orpossibly atthe user’s discretion) the systemneeds to be able to undo all the work thathasbeen done so far.CHAPTER 2— Design oftheObjectPropertyScheme13Persistence ofdata: Once a transaction commits,any changes thatit performedmust be permanent.Attentionwas furtherfocusedto investigatethe services which a single objectwouldrequirefor an atomic method invocation. Recoverabilityandpersistencemap directlyas servicesrequiredfor an atomic invocation. The single-invocation analogue for serializabilityis concurrency control: since Raven is multi-threaded, objects must be protected againstconcurrent accesses. Thisprovides a serial ordering of the invocations on the object. Consequently,the first three serviceschosen were concurrencycontrol, recoverability, and persistence.The semantics of persistence which are required in order to support atomictransactionsmustinclude strong guarantees about writing the object state to storage: oncethe method invocation finishes, the object state must be updated before control isreturned 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 compromisebetweenpersistence andperformance to delay writing the datato disk for a number ofseconds sothe application can return from each invocation ona persistent object without blocking first.Machines and disks are generally reliable, so the chancesof losing data by delaying the write asmall number of seconds is extremely small. Many modernfile systems, such as LFS [20], willbuffer sequences ofdiskwrites to memory in orderto performone largerdiskwrite as opposed tomany smaller writes. For objects which are beingfrequently modified, buffering writes in memory and only updating the version in non-volatilestorage periodically canprovide adesirableperformance improvement. For these reasons,the system needs to support two types ofpersistence:one which provides a strong guarantee aboutwhen object state is written to disk, and one whichprovides greaterperformance by delayingupdates.In a distributedenvironment it isoften advantageous to replicate data(such as name serviceinformation) on many different sites.This allows both an increase in performance (sinceclientsCHAPTER 2— Design ofthe ObjectPropertyScheme14can access servers which are the mostlocal) andavailability(sincethe systemis notdependent onthe status ofa single node). To support the developmentofhighly available applications, amechanism by which the system can make and maintainreplicas of objects is required. Providingobjectreplication was thereforechosen as anothersystem service to support throughproperties.To round out Raven’s support for distributed computing, twoother system services werechosen. First, since Raven’s design allowed objectsto be migrated between machines, somemechanism by which objects could be fixed to theircurrent host (most likely their host ofcreation) was desired. Second, there are often objects which,once instantiated to a particular state,should not be modified. An example of such objects arethose which comprise a mail message:once the message hasbeencomposed and sent,the objects shouldbe consideredto be “read only”and not modifiable. Systemsupport forcreating immutable objectswas therefore also desired.In all, seven system services were chosen for support: concurrency control,recoverability,persistence with both strong and weak guaranteesabout storage updates, replication, immobility,and immutability. Security was notchosenas aservice toprovide for severalreasons. First,Ravenhas no notion of a user, simply ofthe local Raven World;this precludes the use ofaccess controllists or other mechanisms which provide accessto objects on a peruser basis. Second, the implementationofRaven allows only one capability structureforeach object; this precludes the use ofmultiple capabilities, each with potentially differentaccess rights. Third, little thought had beengiven to security during the initial development ofRaven. Developing a notion of securityforRaven is beyond the scope ofthis thesis,so all issues involving system supportof security wereleftunresolved.CHAPTER 2— Design ofthe ObjectPropertyScheme15To correspond to the services provided, seven propertieswerechosen:(1) Controlled(2) Recoverable(3) Durable(4) Persistent(5) Replicated(6) Immobile(7) ImmutableThe Durable property corresponds to persistence witha strong guarantee that object statewillbe updated to storage, while the Persistentproperty correspondsto the weaker, more efficientnotion ofpersistence. To receivea service from the system, an object needs only to be given thecorrespondingproperty.By default, objects are created “plain”, that is, without anyproperties. The Raven systemhandlesplain objects in the following way:• The objectexists only in RAM. Therefore, the objectdoes not survivebetweenreboots ofthe system.• No system control exists to preventmultiple threads from executing methodswithin the object simultaneously.• The object canmigrate frommachineto machine, either at the discretion ofthesystemorwhen the object is explicitly askedto move itself.• Any changes made to the object’sinstance data are immediately availableandare not recoverable.Forthe vastmajority ofobjects createdandusedin the system, these semanticsshouldbe allthat are needed. Most objects will be createdfor short-term use and will not require anyspecialCHAPTER 2— Design oftheOblectPropertyScheme16systemproperties. When an object is assignedone ofthe properties, the systemhandlesthe objectdifferently; it is providedwith the servicewhich is associatedwiththat property.2.4 Property BehaviorSemanticsOne of the first questions encountered whendeciding upon the semanticsof property behaviorwas deciding at what level the properties wouldoperate: should property behavior be limitedto asingle object invocation, or should it affectan entire invocation chain whenthe objects in thechain all have the same property?Eachofthesesemantics has distinctadvantagesandlimitations.Limiting the scope to a single invocation isa very convenient notion: properties can bedescribedby how they effect one object, and can be viewedfromthe perspectiveofa single object. Limitedscope is desirable in the general case forconcurrency control: since locks are freedafter eachinvocation, there is more concurrency and less potentialfordeadlock. However, itgreatly complicates the issue ofproviding support for transactions,as a two-phase locking protocol cannotbeused, and some othermethod mustbe usedto enforce serializability. It would also requirethat thesystembe able to abort transactions at will: Considera transaction Ti which invokes a methodonobject 0. After the invocation, a secondtransaction T2 also invokes on object0. If Ti aborts,then T2must also be aborted. Extending thescope to encompass all invocations is desirablein thegeneral case for recoverability: ifat some level the invocation can’t continue,all the work so farshould be aborted. If recovery simplyrestores the current object’sstate, programmers maybecome loathe to programusing manysmall objects andinsteadencapsulatedata into largerunits.But extending the scope can alsolead to programmer confusion,since it can quickly becomeunclear exactly how far upthe calling chain each ofthe propertiesmay be propagated. Furthermore, extending the scopedoes not eliminate the problemofproviding semantics conducivetocreating transactions.CHAPTER 2— Design oftheOblectPropertyScheme 17The semantics decided upon came with the realization that thereare two distinct concernsinvolved. The firstinvolves objects and the systemservices they require, and the necessity toprovide these services in auniformmanner. By viewing servicesfromthe point ofview ofthe object,it becomes the natural choice to have limit the effectsofproperties to a single object invocation.The second concern is the understanding that objects are often placedin a relationship with eachother, so that what happens to one object is predicated on what happensto the other. To providefor this, the property scheme requires a mechanism for describing inter-objectrelationships thatallow the scope to be extended in the calling chain. This is described inSection 2.6.For each ofthe properties, the semantics ofbehavior are described below. Since propertiesare orthogonal, the system will handle any object with anyone of these properties in the sameway, regardless ofhow many other properties the object has. Althoughit may appear on the surface that some of these properties are not orthogonal, that isnot the case. Recoverable, Controlled, etc. provide only the semantics described, and do notattempt to provide more complexbehaviors, such as serializedaccess or atomic invocations.2.4.1 ControlledAn object given the Controlled property is protectedagainst concurrent accesses by multiplethreads which may modify its instance data. Multiplereaders, but only a single writer are allowedaccess to the instance data. Threads which cannot begranted the access they require (e.g., theywish to write to the instance datawhile someone elseis reading) are blockeduntil the request canbe satisfied.2.4.2 RecoverableAn object given the Recoverable propertyhas the “all-or-nothing”property. Only when a methodterminates normally are any changes madeto the object’s instance variables made permanent.IfCHAPTER 2— Design ofthe ObjectPropertyScheme18the method terminates abnormally, the stateofthe instance variables is reset to the state they hadjustbefore the method started.The Raven programming language includes a restorestatement. Ifthe current object isRecoverable, executing a restore will restore theobject’s instance variables to the state theywere in before the method started. If the object isnot Recoverable the restore statement isignored. Execution continues with the next statement after therestore. Control is notreturnedto 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 dataofaDurable object are writtento non-volatilestorage beforethemethod returns control to the caller. Furthermore, the systemensuresthatthe entire object stateiswritten atomically—only consistent, complete objects are written. It wouldbe disastrous if onlyhalfthe object state were written to storage, since upon restart theobject image loaded in wouldbe inconsistent. Return of control to the caller implies thatthe object state has been updated instorage. A Durable object’s capability also survivessystemfailure or restart. These semantics arenecessary for the correct support ofatomic transactionsand database applications.2.4.4 PersistentThe Persistent property is similar to theDurable property, except that no guarantee is made astowhen the stored instance data will beupdated. Although the in-RAM copy will be markedto bewritten to storage whenevera method modifies the object’s instance data, Persistentobjects areonly written out periodically by the systemto improve performance by reducing 110 traffic andincreasing parallelism. It is not guaranteedthat the current state ofthe object willbe in storage atthe time ofa system failure, but the versionin storage will be complete and consistent.CHAPTER 2— Design ofthe ObjectPropertyScheme19The semantics ofPersistent are similarto those offeredby the traditional Unix file systems,however Unix system semantics make no guarantee thatthe file will be written in a consistentstate (i.e., some dirty pages may get written while othersmay not).Although Durable and Persistent are very similarproperties, the semantics of the two aredifferent. Orthogonality still holds: if an object is both Durable and Persistentit properly obeysboth semantics, since the semantics of Durable subsumes the semanticsof 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 differentmachines. The decision toreplicate is made by the runtime system in an effort to improveefficiency (for example, when anobjectis heavily accessedby processes on two differentmachines). Replicated objectshave weakconsistency: the system does not ensure that all copies ofthe object always havethe same state.Replication is especially useful for improving performance and building highly availableapplications, such as name servers.2.4.6 ImmobileAn object given the Immobile property cannot be migratedbetweenmachines, and remains fixedon its current host. Immobility is desirablefor objects which implement machine specific tasks,such as support for specializeddevices orservers.2.4.7 ImmutableThe Immutable property preventsan 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 anImmutableobject, aruntimeerror is generated.CHAPTER 2— Design ofthe ObjectPropertyScheme20Properties take effect only after theobject has been created and its instancevariables havebeen initialized. This permits an object which is createdwith the Immutable propertyto bebrought into a usable state before the systemprevents any accesses which couldmodify theinstance data.2.4.8 User-Defined PropertiesThe seven system properties described above areeach implemented directly bythe system.Althoughit is notpossible for aprogrammerto modify the implementationofany oftheseproperties, programmers can define semanticsfor and create implementations of their ownproperties.The user-definedproperties are assignable in exactlythe same ways as are systemproperties.User-defined properties, by their nature, can onlyaffect data in user space; that is, theireffects are identical to invoking methodson objects. Iftheprogrammerdefines several properties,itbecomesthe programmer’s responsibilityto maintain the orthogonality ofthe properties.2.5 Assigning PropertiestoInstancesSinceobjects inthe Raven systemcan have any combinationofproperties,aprogrammerneeds tospecify whichproperties an objectwillhave. The Raven languageprovideskeywords for specifying the differentproperties:• Controlledproperty: controlled• Recoverable property: recoverable• Durable property:durable• Persistentproperty:persistent• Replicated property: replicated• Immobile property: immobile• Immutable property: immutableCHAPTER 2— Design ofthe ObjectPropertyScheme21• Testproperty: test_prop• User properties: u_prop_i,u_prop_2,u_prop_3,u_prop_4Objectproperty specificationcanbe done in two ways:(1) The class designercan specifythat all instancesoftheclass will havecertainproperties. The class designer does not needto write any code to support theproperties, sincethey are all supportedby the system.As an example, consider the code fragment froma class definition shown in Figure 1. Allinstances ofthe class HappyObjects wouldbe giventhe Controlled and Recoverableproperties.class HappyObjects controlled recoverable{somelnt : Int;behav doSomething0;}FIGURE 1. Assigning properties inthe class definition.(2) At objectcreation time, theprogrammercan specify a listofpropertiesforthe object. Objects in Raven arecreatedusing one oftwo different methods.Thenewmethodreturns aninstanceofthe class, which will have onlythoseproperties specifiedby theclass designer.The secondcreation method ispnew, whichtakes alist ofadditionalproperties to assign to the instance asone ofits arguments.CHAPTER 2— Design oftheOblectPropertyScheme 22Consider the code fragment shown in Figure 2, whichshows an assignment to the instancevariable someObject. Since someObject is ofclass HappyObjects, itwill have the Controlled andRecoverable properties, as well as the Persistentpropertyand a user-definedproperty.behavior someBehavior{someObject = HappyObjects.pnew(persistent & U_prop_i,argi,...);)FIGURE 2. Assigning propertiesby usingpnew.Although the runtime system supports dynamic propertyremoval (since it must be able toremove properties from an object when the object nolonger inherits them) there is no syntax intheprogramming languageto allow programmersto dynamicallyremoveproperties fromobjects.2.6 Inter-Object RelationshipsAs described in Section 2.4, property semantics weredeveloped by viewing propertiesasthey applied to a single level invocationon an object. But objects do notexist simplyin isolation,and therefore some mechanism bywhich the relationships between objectscan be described isnecessary in order to provide supportfor more complex behaviors like atomic transactions.Inaddition, to achievethe goalofdynamicproperty assignment, some mechanismmustalso existbyCHAPTER 2— Design oftheOblectPropertyScheme 23which objects canbeplacedin some relationshipthatprovidesthedynamic assignmentofproperties fromone object to the other. Towards these ends theRaven language was modified to providethree methods ofdescribing relationships between objects:Dependent references, Inherits references, and Part-Ofreferences. When the designerof a class wishes to describe an inter-objectrelationship, a class instance variable can be marked as eitherdependent, inherits, orpartof. Consider the class definition shown in Figure3. In this example, firstlnstanceVar is a Dependent reference, secondlnstanceVaris an Inherits reference,andthirdlnstanceVaris aPart-Ofreference.class ExampleClass{aFirstlnstance : cap dependent;aSecondlnstance cap inherits;aThirdlnstance : cap partof;)FIGURE 3. Class definition withinstance variablesshowing inter-objectrelationships.2.6.1 Dependent ReferencesDependent references are the tool by whichthe scope of a property is extended beyond a singleinvocation to encompass a calling chain.A Dependent reference is defined as follows. Whenanobject Phas a reference to another objectCwhich is markeddependent (they canbe thoughtCHAPTER 2— Design ofthe ObjectPropertyScheme24of as Parent and Child objects), C is said to be Dependent on P. Thedependency refers topropertydependency: the propertiesofthe child are dependenton those oftheparent. Whentheparentinvokes a method on the child, state information associated withtheproperties is passed upwardsto theparent whenthemethodreturns. Any actionsthatwould normallybe takenbeforethereturnfromthe childbecome dependent uponthe parent.Dependency has meaning only for properties; as such, it does not affectplain objects. In thecurrent design of Raven, the semantics for Dependent referencesaffect only the Controlled,Recoverable, and Durable properties. It makes little senseto 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 asto wheninstancedatawill be writtento storage, no semantics forDependentReplicated orDependentPersistenthave currently been devised.As examples ofhow Dependency works, considerthe following situations, wherethe objectPhas aDependent reference to an object C, and Pinvokes a methodon C:• If Pand Care both Controlled, then the access privileges (read or write privileges) associated with the invocation on C are retained by the threadwhichmade the invocation and are passed back to P Other threadsare still blockedfrom accessing C. Sincethe thread now inPstillholds accessprivileges, itcanmake subsequent invocations onC with impunity (assuming that the accessrights held are sufficient for the invocations—ifthe initial invocation onlyrequired read privileges, the firstfuture invocation that requires write privileges willblockifotherreaders arepresent). Thethreadrelinquishes control ofthe object Cwhen its invocation on Preturns,at which time the thread’s control ofPis also relinquished.• IfPand Care both Recoverable, then any changesmade to Care notcommitted until the changes made to Parecommitted (i.e., the invocation on Preturnsnormally). IfPreturns abnormally,or anrestorestatement is executed,thenCHAPTER 2— Design ofthe ObjectPropertyScheme25both Pand Care restored to the statesthey were in before the invocation on Pbegan.• If P and Care both Durable, then any changesmade to C are not written todisk until the changes made toP are written. The invocation on P will notreturn until both P and C have been written. Sincethe Durable propertyassures that objects are written in their entirety, it is guaranteedthatboth PandCwill be written in an atomic fashion.IfPis a dependent child ofa third object G, then thestate information forthe properties ofC and P are passed to G. State information about aproperty is kept by the thread, and passedback from a child to a parent until the top level oftheDependent chain is reached. Raven placesno limit on the numberofDependentreferences that mayexist to an object.2.6.2 Property InheritanceSection 2.5 described how properties are assigned at the timeof object creation. An additionalway in which an object canreceivepropertiesis dynamically at runtime throughproperty inheritance. When an object is assigned to an instance variablewhich hasbeen marked inherits,theobjectis then assigned all the propertiesofthe objectholding the reference. Since the objectbeingassigned can also have instance variableswhich are marked as inherits, the runtime systemmust compute the transitive closureof all the references which are marked inheritsandupdate the properties of all the objects so referenced.The complete set ofproperties of anobjectare those assigned at creation time plus thoseit inherits from another object. In the currentdesignofRaven, an object can inherit propertiesfrom at most one other object, and there is noway to“mask out” certain properties, i.e., tospecify that an object should not inherit a property dynamically. The design also does not includea mechanism by which objects can be preventedfromacquiring properties dynamically, nora mechanism by which the class designer can specifythatinstances ofthe class should neverbe given certain properties.CHAPTER 2— Design ofthe ObjectPropertyScheme26SETProperties: [None]Item: <Inherits>Item: <Inherits>Item: <Inherits>..___ø.FIGURE4. Some ofthe objects comprisinga mail message,justpriorto being assigned to the MAILMESSAGEAs an example ofthe use ofproperty inheritance,consider a mail message. All the objectswhich make up the mail message(e.g. the To: and Subject: fields) needto be Persistent.However, it is sufficient to simply createthe main mail message object as Persistent,and haveeach ofthe sub-objects inherit Persistence fromthe main object. The advantage ofsuch a schemeis obvious whenyou considerthatobjectsthatcomprisethemailmessage,such as Sets or Strings,may have been created by otherapplications (such as an editor) and maynot have been createdwiththe Persistentproperty.(See Figure 4 and Figure 5.)The ability to dynamically assignproperties to an object is importantin client-server systems where servers create objectsfor use by different clients. With dynamicallyassignable properties, clients can be assured thatthe objects they use will have thoseproperties they need. Thebehaviorofthe object canbe specifiedby the userofthe object, andthe creatorneed notknow inadvance whichproperties 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 ofthe ObjectPropertyScheme27FIGURE 5. After assignment, objects have new properties andbehave accordingly.Property inheritance should in no way be confused with the traditionalnotion ofinheritancewhich describes the inheritance of methods and behaviorsby one class from another. Propertyinheritance is a relationship between twoobjects, indicating that additional system servicesshouldbebequeathedto an object. Objects can inheritproperties fromother objects ofany class.2.6.3 Part-Of ReferencesDependency describes a relation betweenobjects which affects how the system handlesobjectswith properties. In object-orientedsystems, objects are often bound closely together.Consideragain a mail message object. The mailmessage is composed of many other objects: a From:field, aTo: field, etc., eachofwhichare themselves often composedofmanyotherobjects—e.g.,the To: field could be a Set or a Listorjust a simple String object. In such circumstances,thesub-objects makelittle sense in an isolatedcontext.They are intrinsicallypartofthe mail messageobject. This relationship goes beyond simpleDependency;the objects are tightly coupledtogetherrSETProperties: PersistentItem: <Inherits>Item: <Inherits>Item: <Inherits>MAILMESSAGE/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 ofthe ObjectPropertyScheme28by the relationship the programmer has createdbetween them. To describe such a relationshipbetween objects, Raven allows class instance variablesto be markedpartof.By specifying a reference as partof, the referenceis considered to be marked as bothinherits and dependent. For the programmer,there is no semantic difference betweenspecifying a reference aspartof and specifying it as bothinheritsand dependent.The system interprets Part-Of to imply a tight coupling betweenthe objects. As such, theRaven runtime system can make special use ofPart-Ofrelationships. Considera chain ofobjects,A—>B--->C, where Cis Part-Of B and B is Part-OfA. Together,A, B, and Ccan be viewed as asingle clusterby the Raven system. Since the objects in a clusterare tightly coupled, objectclusters canbe usedby the Raven systemin a variety ofways:• Object clusters can be written to disk as a single unit, even ifthey arenotcontiguous in memory. Similarly, when the root object of an objectcluster isloaded in from disk, the entire cluster is loaded, sinceit is probable that manyofthe objects in the clusterwill soonbe needed.• Object clusters can be migrated togetherbetween machines.Simply migratingthe root object of a cluster would be inefficient,since any invocations by thecluster root object on other objects in the cluster willeither have to be remote(i.e., across machine boundaries), or cause additionalobject migrations (withtheir associated overhead).Clusters are an efficiency mechanism forthe runtime system and do not alter the semanticsfor the programmer. Because objects caninherit properties from at most oneother object, anobject can be Part-Of at most one otherobject. The Raven system does not limit thenumber ofreferences thatcan existto an objectthatis Part-Ofanother.As a possible use ofPart-Of, consideragain the mail message objects ofFigure4, only thistime with instance variables markedpartofinstead of inherits. Performancewould sufferCHAPTER 2— Design ofthe ObjectPropertyScheme29greatly if the system only loaded in the root objectfrom disk when the mail messagewasaccessed, or only migrated the root objectto another machine; in a very short time, the otherpieces ofthe objectwill need to be accessed.By logically clustering the objects togetherthe overall performance ofthe systemcanbe improved.It shouldbeemphasizedthatPart-Ofis usedby the runtimeto provides performanceoptimizations only, and is otherwise no differentthan specifying inheritsanddependent.2.7 Combining PropertiesSinceproperties in the Raven systemare orthogonal, theycanbe easily combined. No side effectsresultfromadding properties to objects; instead,the systemsimplyprovides the new functionalityofthe added property. Properties can be combined to produce theexact behavior required, whileinvocations on the objectdo notincur any overheadforsystem servicesnot used.Although manyobjects will haveonly a singleproperty(e.g. Controlledor Persistent), morecomplex applications and objects require several properties. Onenaturalpairing is Immutable andReplicated. Since an linmutable objectcannotbe modified,itcan be replicatedon many machines(or even in several places on the same machine) withoutany concern formaintaining consistencybetween copies.Different applications will require different pairingsofproperties. Consider a name service.The name servicemust supportconcurrentlookupsby multipleusers, provide afacilityforaddingand removing names, while maintainingthe integrity of the service across system reboots.Theobjects which comprise the name server need to beboth Controlled and Persistent, otherwise thename serverwill not functionproperly.CHAPTER 2— Design ofthe ObjectPropertyScheme302.7.1 Supporting AtomicTransactionsMore complex systems require more properties. Bycombining Raven properties and placingobjects in aDependentrelationship, it is possible to createdatabasesystems whichsupport atomictransactions. Objects in the database need to be Controlled,Recoverable, and Durable. By puttingthe objects in a Dependent relationship, the invokingthread has exclusive access to the objectsuntil the transaction returns, as the thread will retainall the concurrency control locks for theobjects touched. New locks can be acquired, but old locks will notbe released until the top levelinvocationreturns. Thisbehavior is analogous to atwo-phase locking protocol, andthereforeprovides the serializability required for atomic transactions. Sincethe objects are Recoverable, anyabnormal termination or if a restore statementis executed will restore the state of all theobjects touched to the values they had before the transactionbegan. Finally, the new state of allthe objects will be written to storage at the same time, in an atomicfashion, prior to the returnfrom the top level invocation. As such, in the eventof a system failure, either all the objects areupdated in storage, or none ofthem are.CHAPTER 3 ImplementationoftheObjectProperty SchemeIn order to test the ideas developed in the previous chapter, corefeatures ofthe property schemewere implemented andintegrated into the Ravenruntime system.3.1 Data Structuresfor Property SupportAn object in Raven is referenced usinga capability pointer to the object. These pointers are normal 32-bitintegerpointers to memory.Capability pointerspoint to ablockofmemory whichcontains a capability structure. These structures containthe data, or pointers to the data,used by theruntimesystemforthemanagementoftheobject, as well as apointerto ablockofmemorywhichcontains the object’s actual instance data. The capabilitystructure is shown in Figure6.An object’sproperty set is storedas an integervalue inside the capability structure. This 32-bit value is divided intotwo 16-bit words. The first word is used tostore the set ofproperties theobject was assigned at creation, whilethe second stores the currently inheritedproperties. This31CHAPTER 3—Implementation ofthe ObjectPropertyScheme32struct 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 object_properties;u_char*data;invoke: Pointerto the invocation functionto useid: Pointerto this structure,for sanity checkingis_a: Capabilityofclass object which we are an instance ofparent: Capability ofobject we inheritpropertiesfrominh_root: Root object ofinheritance treestorage_manager: Capability ofobject which manages ourstoragemethod_type_to_use: Indicates ifaremote invocationis neededgid: Pointer to objectglobal identifierrw_lock: Pointer to objectconcurrencycontrol lockcluster_lock: Pointer to objectcluster lockobject_properties: Objectpropertysetdata: Pointer to object instancedataFIGURE 6. Objectcapability structure.design limits the number ofproperties thatthe system can support to 16—each bit position indicateswhethertheobjecthas aparticularpropertyor not. In additionto the seven systempropertiesandthe fouruserproperties, Raven providesa“test” property thatwasusedextensivelyduring thetesting ofproperty inheritanceand dependent invocations. The test propertycan also be used asthe basis fortesting new systempropertiesbefore modifying the compilerandthe runtime systemCHAPTER 3— Implementationofthe ObjectPropertyScheme33to supportthe new property name. In total 12 bits ofeachword are accounted for, allowing uptofour more to be addedbeforethese fields would needto be widened.As described in Section 2.5, a programmer can specify new propertiesfor an instance byproviding a list ofproperties as an argument to thepnewmethod. It is a natural convention to listthesepropertiesusing an “&“ operator, as inpnew(prop& prop & prop. .. ): when aprogrammer wants an object to have “concurrency controland recoverability” it can simply be written as “controlled & recoverable”. To facilitatethis, each of the Raven properties isrepresented as a bitmask of all is, with a 0 in theposition corresponding to that property. Theobjects property maskis then createdby performing abitwise-andofthe properties the objectwasgiven. Ifan object is created with aparticularproperty, it will havea 0 in the correspondingposition ofthe first word of its property mask; if it inheritsa property, it will have a 0 in the correspondingposition ofthe second word ofits property mask.By storing properties as bitmasks, theruntime systemcaneasily detectwhen an object has aparticularproperty. The bitmasks are givenin Appendix A.2. Simple macros have been written to test and setthe appropriatebitpositions foreachofthe properties.The otherpieces ofthe capability structure usedbythe runtime systemto supportpropertiesare:• The parent capability: Pointsto the capability structure of the object fromwhich properties are inherited.If no properties are currently beinginherited,this value points to thenilobject.• The inh_root capability: Pointstotherootobjectofthepropertyinheritancetree. Note that not all inheritedproperties may be from the root object;somemay be from an intermediate object.• The storage_manager capability:Points to the object which manages thestorage ofthis object to disk(see Chapter4).CHAPTER 3— Implementation ofthe ObjectPropertyScheme34• The gid pointer: Points to a data structure containingthe object’s globallyunique identifier (see Chapter4).• The rw_lock pointer: Points toa lock data structure used for concurrencycontrol, or NULLifthe object is not Controlled.• The cluster_lockpointer: Points to a lockdata structure used for Part-Ofcluster locking (see Section 3.5).3.2 Providing System ServicesThroughPropertiesThe purpose ofproperties is to allow system services to be provided transparentlyto objects. Services are provided whenever a method is invoked on an object.To accomplish this, the runtimesystem uses a series ofpre- and post-invocation functions, with oneset of functions for each ofthe properties. Immediately priorto the methodinvocation, the propertyset ofthe objectis examined. For each property the object has, the appropriatepre-invocation function(termed apre-handier) is executed. When the necessary pre-handlers have been executed,the method code itself isexecuted. Afterthe method returns, priorto returning control to thecalling object, the appropriatepost-handlers are executed.The order in which the pre- and post-handlers are executed is veryimportant to ensurecorrectness. Forexample, it is necessary that locksnotbe released until afterthe Durable and Recoverable post-handlers have executed, since these functionsmay need to read or write the instancedata ofthe object; it would be disastrous ifanotherthread began modifying the object’s instancedata while the Durable post-handler wasattempting to write the data to disk. Correctness placesseveral restraints on the ordering that canbe used, the primary one being thatconcurrency controllocks mustbe acquiredbefore any otherworkis done and releasedonly after all other workisfinished. Correctness also requires that theRecovery post-handler execute first, since itmay restorethe object state. They system must notpropagate an incorrect state to replicasof the object, orstore an incorrectstate to disk.CHAPTER 3—Implementation oftheObjectPropertyScheme35The current ordering ofthepre-handlers isas follows:(1) Controlled(2) Durable(3) Persistent(4) Replicated(5) Testproperty(6) Recoverable(7) Userproperties (u_prop_i through u_prop_4)The post-handler orderis the exactinverseofthe pre-handlerorder.There are no pre- and post-handlers forthe Immutableand Immobile properties. To supportthe Immutable property, the runtime system checks the methodtype 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 determinationof the method type is done by theRaven compiler through an analysis ofthestatements in the method. Although the compilercanbe fooled and generate an incorrectmethod type,and some invocations ofwrite methods may notin fact modify the instance data, this implementationis extremely simple, and providesareasonable implementation. The Raven runtime systemdoes not currently implement object migration,and as such, the Immobileproperty is notused. However, when migrationis implemented,immobility will still not need apre- or post-handler,as it will simply be checked forjustprior to objectmigration.Since theproperty setofan objectcanchange dynamically, it’s possibleforone thread to bereadingtheproperty set as itbeginsan invocationwhile a secondthreadis modifyingthepropertyset as the result ofits own invocation. This problemis addressed by several features ofthe runtime. First, the property set is stored as aninteger value. It can be assumed thatthe hardware canCHAPTER 3—Implementation oftheObjectPropertyScheme36read and write integer valuesto memory atomically;as such, athreadreading theproperty setwillnot see a partially updated property set that is beingwritten by another thread. Second, athreadmust have the object’s concurrency control lockin order to modify the property set; ifno lockexists, then that thread can be assumed to have exclusiveaccess 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 ofan objectwill remain stable for a thread after it isgranted the lock (unless the thread modifies the property setitself). If the property set waschanged while threads are waiting to he grantedthe object’s concurrency control lock, they arerestarted, object immutability is rechecked, and the threads onceagain begin the process ofexecuting thepre-handlers.One alternative to using a careful ordering ofthepre- and post-handlers is to have the handlers executed atomically—that is, require that noother threads be allowed to execute while onethread is inside the set of pre- or post-handlers. Usinga careful ordering provides better performance, but it also precludes the use of user-definedproperties for providing alternate forms ofsome ofthe system services, particularly concurrencycontrol, since no ordering could allow bothsystem-supportedconcurrency control and user-supportedconcurrency control to be the firstprehandler executed. However, if the handlers were executedatomically, some mechanism wouldstill be required to deal with the problem ofdynamicallychanging property sets, and potentiallyundoing work done in a pre-handler fora property which the object will not have whenthemethod is actually executed.An examination of the pre- and post-handlershelps demonstrate the orthogonality oftheproperties. The handler code foreach ofthe implemented properties makes no referencesto anyother property, nor does the code accessdata structures used by the pre- and post-handlersoftheother properties. The exception to this ruleis the handlers for the Durable and Persistentproperties, which perform almost identicaltasks. Although separate implementationscould have beenCHAPTER 3—Implementation oftheObfectPropertyScheme37made, it would have required an almost complete duplicationofthe existing data structures andcode. Itwas thereforedecidedto combinethe implementationsand allowthemto sharedatastructures and supporting objects (see Chapter 4).3.3 Dependent InvocationsWhenever a method is invoked on an object which isreferenced via an instance variable whichhas been marked dependent, the runtime system must keep trackof state information associated with the properties. This is accomplished by maintainingthis state information in the thread.Currently, the runtime system uses the thread to threadkeep track of information for the Controlled, Recoverable, Persistent, and Durable properties; theseproperties therefore supportDependent invocations. Each thread has associatedwith it a corresponding thread object (aninstance ofthe Raven Thread class). Thread objects include amongtheir instance variables thefollowing:• session_chain: An integervalue which isused by theruntime system as apointerto alist oflock structures currently heldby the thread.• lock_depth: The integer value ofthe currentdepth in the invocation chain,starting at thetop-most Controlledobject andcounting only Controlled objectsin the chain, lock_depth is basically thecount ofthe number oflocks heldby the thread.• shadows: An integer value which is used by theruntime system as a pointerto a list of object shadow copies, i.e., copies of objectinstance data. Theseshadow copies are created for Recoverableobjects and are used to restoreobject state.• callDepth: The integer valueof the current depth in the invocation chain,starting at the top-most Recoverableobject and counting only Recoverableobjects in the chain.CHAPTER 3—Implementation ofthe ObjectPropertyScheme38• function_chain: Aninteger value whichis used by the runtime system asa pointer to a list offunctions that need to be executedat some later time. Theuse offunction_chainis discussed in Section 3.4.1and Section 3.5.3.• storage_chain: An integer value which isused by the runtime system asa pointer to a list of objects which need to be writtento storage. storage_chainis discussed in Section4.4.Each Dependent invocation has associated withit a corresponding identifier. A chain ofDependent invocations all use the same identifier, which is set tothe id (integer value of thecapability pointer) ofthe rootobject ofthe Dependent chain.When an invocation is made in Raven, aparameterstructure is passedto the invoke routine.This parameter structure contains data used in the courseofthe invocation, such as the methodname, and the actual parameters used by the method. These parameter structuresare 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 traceupwards through the parameterstructures for previous invocations. The parameter structure containsa boolean flag, dependentInvoke, that indicates if the currentinvoke is Dependent or not. The Raven compilerchecks each invocation to see ifthe invokee is Dependent upon the invoker; if so, the compileremits code to set this flag to TRUE (apredefinedboolean value usedby the runtime). This allowsthe runtime system to know when a Dependent invokeis occurring. Details about invocations inRaven, including the use ofparameter structures, canbe found in [1].The parameterstructure contains anotherflag, isDependentRoot, which is normallysetto FALSE, as well as an integerfield for the Dependent invocation identifier,dependentID.Whentheruntime finds thedependentInvoke flag set, itexamines theparameterstructurefortheprevious invocation. Ifthis structurehas anon-zero valueforitsdependentlD,this value isused as the Dependent invoke identifier ofthe current invocation. Ifthis value is zero,then theCHAPTER 3—Implementation ofthe ObjectPropertyScheme39invoker must be the root object ofthe Dependentinvocation. The isDependentRootflag isset to TRUE in the invoker’s parameter structure, and the localdependentID is setto the Idofthe invoker.Normally, post-handlers are executedonly for properties which anobjecthas. However, it ispossible that the root object of a Dependent invocationchain does not have the Controlled,Recoverable, or Durable properties, yet objects withthese properties were invoked somewhere inthe chain. The post-handlers for these properties must therefore be executedwhen the invocationon the root object has completed. Ifthe isDependentRoot flag isset, these post-handlers areexecuted. The post-handlers check the value of this flag, and performthe necessary work ifDependent invocations were made on objects with the correspondingproperty (see Section3.3.1,Section 3.3.2, and Section4.4).A Dependent invocation chain only includes objects which are Dependentupon their callers. Ifan invocation is made on a non-Dependent object, then any further invocationsmade fromthatobjectwillbe partofanew, separate Dependentchain.Forexample, consider achain ofinvocations, A—>B--->C--*D-—*E, where Eis Dependent on Dand B is Dependent on A. Both the invocation on A and on D are considered to be rootsof Dependent invocations, and will have theirisDependentRoot flags set. Properties which supportDependency need to keep track oftheIdofthe currentDependent chain, to ensure thatthepost-handlerdoes not do work prematurely:using the above example, when the invocation on 0terminates the Durable post-handler needs towrite 0and Eto storage, but notAand B.3.3.1 Dependent Invocations on ControlledObjectsEachinvocation on aControlledobjecthasan associated lockdepth, which is basicallya countofthe number oflocks the thread currentlyholds. An initial invocation on a Controlledobject has alockdepth ofone; an invocation itmakes on a Controlled object would havea lock depth oftwo,CHAPTER 3—Implementation oftheObjectPropertyScheme40etc. The lock depth is unaffected by invocations madeon objects which do not have locks: ifAinvokes on Bwhich invokes on C, and only A and Care Controlled, the lockdepth ofthe invocation on C will be two. The locks held by the threadare kept in a list referenced by thesession_chaininstance variable ofthe thread object.To support Dependent invocations, thelock information data structure described in [1] was augmentedto include a field forthe value ofthecurrentDependentinvocation identifier; this field isalso calleddependentID. The value ofthis field is set by the Controlled pre-handlerto the currentvalueofdependentID found in theparameter structure.When a method terminates, the post-handler checks the dependentInvokeflag. Ifit isset, then the handler simply returns without releasing any locks; ifnot, then locks are released upto the current lock depth. If the isDependentRootflag is set, then the post-handler mustrelease all locks thatwere acquiredduringthe Dependentinvocations.Ifthe currentobjectis Controlled, all locks with a lock depth greater than the current depth arereleased, since all the locksacquired afterthe currentlock will have a lock depthgreater than the current lock depth. Ifhowever the current object is not Controlled, then the session_chainis traversed starting fromthe mostrecently granted lock. IfthedependentlDofthe lockinformation structure is equaltothe idofthe current object, the lock is released, andthe next lock in the chain is examined. Thisprocess continues until no locks remain inthe chain, or a lock information structure has adependentID not equal to the idofthe currentobject.3.3.2 Dependent Invocations on RecoverableObjectsWhen Recoverable objects are part of a Dependentcalling chain, the shadow copies of theobjects’ instance data must be retained bythe thread until the top level invocationin the Dependent chain terminates. The thread also keepstrack of the current depth in the invocationchainusing the instance variablecallDepth.CHAPTER 3—Implementation ofthe ObjectPropertyScheme41Each time an invocation is made on a Recoverable objectwithin a Dependentcalling chain,a shadow copy ofthe object is made andplaced onthe shadows listkeptby the thread. Thecurrent value ofthe callDepth is then set for thisinvocation, and stored with the shadow. Whenthe top level invocationterminates, the shadow copiesare simply discarded, as they are no longerneeded. However, if a restore statementis encountered, then the list of shadows is traversedand all objects whose shadows have a higher call depththan that ofthe 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 threadis destroyed after the method finishes executing. However, since property state informationis kept in the thread, remote Dependent invocations mustbetreated in a special manner. Additionalproblems arise due to the natureofthe implementationofproperties: since mostofthedatastructures used are regular C structuresand pointers, references to the state information cannotbe easily passed back to the originalmachine. Propagating the state data back canbe expensive, and troublesome to maintain, aschanges are made to the data structures orsupport for Dependency is added to additional properties. To address these concerns the followingsolution to the problem ofremote Dependentinvocations was adopted.Every remote invocation now includes anadditional integer parameter in which the ID ofthe current Dependent calling chain ispassed (or zero if the invocation is not Dependent).Apotential problemcan occur, however,since DependentIDs arejustthe locationin memory oftheroot object of the Dependent chain,and there may be an object at that locationon the remotemachine which gets invoked as partofthe remote invocation. Therefore, theactual ID passed is(<real Dependent ID>1), as no object could ever resideat an odd memory address.CHAPTER 3—Implementation oftheObjectPropertyScheme42When the remote thread finishes execution of a Dependentinvocation, in addition to any returnvalue it also passes back the globally uniqueID (GID, see 4.1.1) corresponding to the Threadobjectofthe remote thread. The remote thread thensuspends itself, so theThreadobject and itsassociated data structures are not destroyed.ThegidoftheremoteThreadobjectis storedwiththe stateinformation foreachpropertyin the local thread. When the invocation on the rootobjectofthe Dependent invocation chainfinishes, the property post-handlers are executed. As the post-handlerstraverse their state data, if areference to a remote Thread object is encounteredthen a remote invocation is made on thatobject (see Appendix B.1). The remote workerwhich is createddoesnotawakenthe original, suspendedworker; instead, it simply uses the worker’s instance datato performthe appropriate worknecessary for the specific post-handler. This is possiblebecause all remote worker threads of anoriginal thread have the same session identifier as theoriginal thread, and this session identifier issupposed to be unique for all threads in the system. Once all thepost-handlers have executed, theoriginal workeris awakened and is then destroyed.Currently, the system stores the remote Thread objectgid in the state information ofevery property, even if no objects with that propertywere invoked upon by the remote thread.Therefore, remote Dependent invocationswill require one additional remote invocation for everyproperty which supports Dependency.3.4 Property InheritanceIn the general case, supportingproperty inheritance is fairly straightforward.The Raven compilerdetects any assignments which are madeto a class instance variable which ismarked with theinherits keyword, and emits codeto call a special runtime routine, UpdatelnheritsQ,which does the work of“disinheriting”properties from the old object whichhad been referencedCHAPTER 3—Implementation ofthe ObjectPropertyScheme43by the instance variable and “bequeathing” propertiesto the new object assigned to the instancevariable.The basic steps taken in disinheriting properties from and bequeathingproperties to a targetobject (i.e., an object which has been de-assigned from or assignedto an instance variable whichprovides property inheritance) are the same. When bequeathingproperties, two additional stepsmust be taken: first, the system must ensure that the target objectis in the same Raven World asthebequeathing object; and second, the systemmustcheckto see thatapropertyinheritancecycleis not being created, by checking to see if the target object isthe root object from which thebequeathing objectinherits properties.The system first computes the transitive closure ofall objects which inherit properties fromthe target object. These objects are then locked to prevent any concurrent accessesto themwhiletheir properties arebeing updated. Next, the property maskmaintainedin eachobject’s capabilitystructure (see Figure 6) is recomputed, and any work associated withthe gaining or losing ofproperties (e.g., creating or destroying locks used by the Controlledproperty) is performed. Thevalue ofinh_root stored in each object’s capability structureis also updated accordingly. Thispointerpointsto theroot objectoftheproperty inheritance tree; anobjectwhichno longerinheritsany properties has its inh_root set to point to itself. The valueoftheparent pointer for thetarget object must also be updated; this is either the objectfrom which properties are directlyinherited, ornilifno properties are inherited. Finally,the locks on the objects are released.Currently, the system does not do anyperformance optimizations, such as checking to seeifdisinheriting or bequeathing propertiesactually affects the property sets of all the objectsin thetransitive closure, and then omitting theunaffected objects from the set of objects that needtohave their property masks updated.CHAPTER 3—Implementation ofthe ObjectPropertyScheme443.4.1 Recovering Property InheritanceAssignmentsAlthough providing property inheritance is straightforwardin the general case, it becomes muchmore complicated when the assignment which providedproperty inheritance can be recovered.Consider the example shown in Figure 7, where anlnstanceprovides property inheritance.behavior doSomething(){if (anlnstance == oldObject)anlnstance = newObject;restore;}FIGURE 7. An Example ofRecoveringa Property Inheritance Assignment.The original object (oldObject) whichhad been referenced by anlnstanceand all objectswhichinheritpropertiesfromoldObject willhave theirproperty masks changed, andnewObject and all objects which inherit from newObjectwill have their property masks changed.Furthermore, these objects mustbehave as ifthey have (or don’t have) theappropriate properties;ifnewObject was uncontrolled before,but has the Controlled property now, itmustbe given alock. However, once the restore statementis executed, all the work which was doneto disinheritoldObject and bequeath propertiesto newObject mustbe undone.Since the data structuresCHAPTER 3— Implementationofthe ObjectPropertyScheme45used by the runtime system to supportproperties are mostly C structures, and sincethe propertyinformation is stored in the capability structureand not in the object instancedata itself, theshadow structures used by the Recoverableproperty cannot be used to recover all thestate thatexistedpriorto the method invocation.To solve this problem, recoverable assignments whichprovide property inheritance aretreated in a special way. When the assignment is made,only the minimal amount ofworknecessary to provide correct functionality is performed, andthe remaining work is delayed until recoverable invocationterminatesnormally (or, inthecaseofa Dependentinvocationon aRecoverableobject, when the top-level invocation returns). Thisminimal amountofwork involves modifyingthe property masks, and creating the datastructures needed for any properties newly inheritedbyan object (e.g., creating locks for newly Controlledobjects), but does not include destroying thedata structures used by properties forany objects which were disinherited. Therefore, the locks,storage managers, shadow copies, etc. of objects whichhave been disinherited will be retained.Furthermore, the objects in the transitiveclosures will remain locked until thestatus ofthe invocation has been determined, as theobjects mustbeprotectedagainstconcurrentaccesses throughout the time thattheirproperty sets mightchange.One oftwo scenarios will now occur: eitherthe invocationwill terminatenormally, orwill itwill be rolled back. After the minimalwork described above is performed,a special function isqueued up tobe executedwhen it is knownwhich ofthese two situations has occurred.Thisfunction is added to a list ofsimilarfunctions kept by the Threadobjectin its function_chaininstance variable. Onefunctionexists to handle theworkassociatedwithdisinheriting objects andanotherto handle theworkofbequeathingproperties to objects. Withthe function, alistofparameters (whichinclude the set ofobjectsin the transitiveclosure) is kept, as wellas the currentlevelofthe invoke depth (correspondingto the invoke depth ofthe current shadowcopy). The execuCHAPTER 3—Implementation oftheOblectPropertyScheme 46tionofthe functions in the function_chainis performedby the post-handlerfortheRecoverableproperty and by the code which implements therestorestatement.Ifthe method terminates normally, the function_chainis traversed in the order it wascreated, and each function is executedin sequence. Ifa restore statement is encountered,thefunction_chain is traversed in the reverse orderofits creation until the invoke depth ofthefunctions in the chain are ofa higher levelthan the invoke depth ofthe current recoveryshadow.The functions take as one argumentaboolean flag indicatingthe status ofthemethodtermination.This allows them to either complete the workbegun when the assignment was made, or roll itbackto the previous state it was in.An alternate scheme to performing the minimal worknecessary when a recoverable assignment is made is to make the optimistic assumptionthat the method will terminate normally,anddo all the workassociatedwithdisinheriting andbequeathingpropertiesaccordingly. It is notpossible to do a “pessimistic” assumption,since the object assigned to the instance variablemustreceive the services associated with the properties it inheritedas a result ofthe assignment. However, this scheme will be very expensive inthe case where the assignment is recovered,since allnew data structures forthedisinheritedobjectwillneed tobe created (which, in the caseofPersistent or Durable objects, will require coordinationwith the on-disk storage; furthermore, thesystemmustnot in any case delete any on-diskversions until it is absolutelysure thatthe object is nolonger Persistent or Durable). Delayingmost ofthe work until later does not increasethe amountofworkthat needs to be done.Furthermore, at least some work mustbe done even in the optimistic case, since all the objects in the transitiveclosure must be unlocked. Sincethe locks wereacquired directly and notas the result of an invocation, it cannotbe assumed that they will bereleasedby the Concurrencypost-handler,since thepost-handler may neverbe executed.CHAPTER 3—Implementation ofthe ObjectPropertyScheme473.5 Part-OfClustersThepartof keyword also provides propertyinheritance, and therefore muchofits implementation is similar to that described in Section3.4. When the compiler detectsan assignment to aninstance variable markedpartof, a specialruntime function, UpdatePartOf( ),is executed.As withproperty inheritance, this functionand its supportfunctions musttreatrecoverableassignments to Part-Ofinstance variables ina special manner, as described in Section3.5.3.In addition to providing property inheritance and dependency,thepartofkeywordis usedby the runtime system to provide a logicalclustering of objects. The transitive closureof allobjects which can be accessed from a root object (i.e.,an object which is not Part-Of any otherobject) using Part-Ofreferences comprises the Part-Ofcluster. This clustering information is currently usedby the Durable and Persistentpre- andpost-handlers to store andretrieveall objects inaclusterto andfrom disk as asingleunit (see Section4.3). Once objectmigrationis implemented,clustering informationcan also be used to migrateentire clustersbetween disks. How objectsareremoved from and added to Part-Of clustersis described below. The effects of such changes toPart-Ofclusters on object storage are discussedin Section 4.4.There is one potential problem with usingPart-Of clustering information in the mannersdescribedabove. Considerthe situation showninFigure 6, wheretwo objects form aPart-Ofcluster. One thread (Ti) invokes amethod on one object of the cluster, whileanother thread (T2)invokes a method on the other.If Ti is a worker thread for a remoterequest the system maydecide to migrate the cluster. However,leafObject may be in an inconsistentstate becausethread T2 is invoking on it.Ifthe objects in the cluster are Controlled,the system can acquire allthe locks before doing the migration;however, there is no guaranteethateither rootObject orleafObject have concurrencycontrol locks (and indeed, sinceonly one thread is accessingeachobject at atime, neitherobjectmay needtobe Controlled). The systemhas no mechanismbyCHAPTER 3—Implementation ofthe ObjectPropertyScheme48FIGURE 8. Objects in aPart-OfCluster.whichitcandetectthatuncontrolledobjects inaclusterare in aconsistentstate, yetitmay needtomake acopy ofthe instance dataofthese objects forthe purposes ofmigration or object storage.To solve this problem, and to more rigorously enforcethe notion ofclustering, a new concurrency control lock is added to eachPart-Ofcluster.This lock is shared among all the objects inthe cluster, and any access to any objectsin the cluster must first acquire this lockbeforeacquiring any concurrency control lockson the objects in the cluster. Althoughthis clusterlock rendersany local object locks superfluous, thecurrent implementation does not perform any optimizingand all locks are still acquired.TiT2CHAPTER 3—Implementation oftheOblectPropertyScheme 49By placing aclusterlockon all the objects in acluster,the system is effectivelycreating 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 thisscheme does solve the problem describedabove, adding the concurrency control lockwill degradeperformanceslightly. Treating the objectclusters as single objects has one additional drawback: itis notpossible for a threadto spawnparallel invocations on the individual objects ofacluster, as deadlockwill result.The Part-Ofclusterlockis acquiredduringtheexecutionofthe propertypre-handlers, andisreleased during the execution ofthe post-handlers. Thecluster lock is acquiredjust prior to andreleasedjust after any local concurrency control lock is acquiredorreleased.3.5.1 Removing Objects from a Part-OfClusterWhen an object is de-assigned from an instance variable whichis markedpartof, the systemmust firstdetermine ifthe object is a singleobject orhaspart0f referencesofits own. Thetransitive closure of all objects which inherit properties fromthe removed object is computed, andthese objects are tagged to indicate if they simply inherit propertiesfrom the removed object orare Part-Ofthe removed object. These objects are locked, and theproperties ofthe objects in thetransitive closure are updated in the same fashionas described in Section 3.4. If the object hasPart-Of references, then the removed object will formthe root of a new Part-Of cluster. A newclusterlockis createdandassignedto all the objectsinthe transitiveclosure which are Part-Oftherootobject.Since Part-Of clusters have cluster locks, it’s possiblethat a thread waiting on the clusterlock was attempting to invoke on the removedobject (or, ifthe removed object is now the rootofits own Part-Ofcluster, one ofthe objectsin the new cluster). Therefore, witheachqueued threadthe identity ofthe target object ofthe threadis stored. When objects are removedfrom a Part-Ofcluster, the cluster lock waiting listis examined, and any thread which is waitingto invoke on anCHAPTER 3—Implementation oftheObjectPropertyScheme50object no longer in thatclusterwillbe moved to the new cluster lock (ifone exists),orrestartedifthe removed object is no longer partofacluster.3.5.2 Adding Objectsto a Part-Of ClusterWhen adding an object to a Part-Ofcluster, the system first ensures that theobject is in the sameaddress space as the cluster. As with removing an object from a Part-Ofcluster,when adding anobject the runtime system must determine ifthe object is the root objectofits own cluster. If so,the objects in the old cluster must have their cluster lock pointersreset to point to the lock oftheclusterto whichthey arebeing added. The threads waitingonthe nowunusedclusterlockmustbetransferred to the new clusterlock. Ifthe objectbeing added is asingle object (i.e., it has no Part-Ofreferences) then any threads waiting on its local concurrency controllock (ifone exists) arerestarted. Thesethreads are not allowed to beginexecution ofthe method code, however; instead,they are required to begin the process of executing the property pre-handlercode again. Thisforces them to acquire the new cluster lock before they are allowed to acquire the localconcurrency control lock, for which they had been previously waiting.An alternate scheme to forcing athreadrestartis to move all the threads queuedon the local concurrencycontrol lockto the clusterlock. The current implementation of locking makes this difficult, however, sincethe lock depthwill notbe correctly updated.3.5.3 Recovering Part-OfAssignmentsBecause instance variables marked partof provideproperty inheritance, recoverable assignments to Part-Ofinstance variables are handled in the mannerdescribed in Section 3.4.1. As withany recoverable assignment that can affect multipleobjects, the primary concern is that theobjects be kept in a consistent state throughout thelife ofthe invocation. Only a minimal amountofwork is done when an object isadded or removed from a cluster, and functions arequeued upCHAPTER 3— Implementation oftheObiectPropertyScheme 51on the Threadobject’s function_chainto finishthe work begun, or undo the work started,when the status ofthe invocationis determined.When a recoverable assignment is made, any objects removedfrom the Part-Of clusterretain their cluster lock. This allows them to remainprotected against concurrent accesses whiletheir status is in doubt. Dropping the cluster lock (or creatinga new one ifthe removed object isthe root of a new cluster) must be done anyway, and delaying thiswork until it is known that theassignment is permanent makes recovery easier,since any threads queued on the original clusterlockcan be leftuntouched. Ifan existing Part-Ofcluster is addedto aPart-Ofcluster, the existingclusterretains its cluster lockuntil the status ofthe invocationis determined. This lock is heldbythe thread which is performing the recoverableinvocation, 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 oneoftwoways, eachwith its own advantages anddisadvantages:(1) Self-invokes areconsideredto be “sub-invocations”ofthe initial objectinvocation. As such, no systemservices needtobeprovidedfortheinvocation: allnecessary pre-handlers were already executedbefore the initial invocation,and the post-handlers will be executed oncethe initial invocation finishes.(2) Self-invokes are normal invocations, and aretreated no differently than anyotherinvocation. Allthe propertypre- and post-handlers are executed forself-invocations.If selfinvocations are viewed as sub-invocations,then the runtime can execute themmoreefficiently (since it does not needto check for object properties). Furthermore,the object can becontinually modified by sub-invocations,butnothing will be written to disk until theinitial invoCHAPTER 3—Implementation ofthe ObjectPropertyScheme52cation returns. Any restore statement encounteredwill restore the instance data to the state itwas in priorto the initial invocation; all work done insidethe objectto this pointwillbe lost. Thisprevents an object from executing a transaction upon itself. It also raises thequestion ofwhetheronly invocations explicitly made on the objectself shouldbe considered sub-invocations,or ifinvocations on an instance variable which was set to self shouldalso be sub-invocations. Theruntime system has no mechanism by which it can determine whichofthese scenarios occurred,although the compiler could be modified to emit special code in the event ofan invocation onself.If self-invokes are classified as normal invocations, then redundant work willbe done insome ofthe pre-handlers (e.g., the local concurrency control lock is obviouslyalready heldby thethread). Although some efficiency is lost, programmers are presentedwith a single, uniformmodel ofobject invocation, and they can view self-invocations as ifthey wereany other invocation. A further question arises, and that is whether self-invocations shouldbe considered Dependent or not. If they are considered Dependent, then the efficiency ofthe system can be furthercompromised, as extra work for Dependency mustbe performed; however, it does imply thatwrites will be delayed until the initial invoke returns. If self-invokesare not considered Dependent, then all invocations following the self-invocation wouldconsider the self-invocation to bethe root oftheirDependent chain; this wouldprecludehaving self-invokes inside oftransactions.In thecurrentimplementation, all self-invocationsare treated as normalinvocations, and arefurthermore considered to be Dependent invocations.Although the dependentInvoke flag isnot set by the compiler in this case, the runtimesystem checks to see ifthe method invoker andinvokee are the same object, and sets thisflag if they are. Although this scheme is not the mostefficient, it provides the most consistentsupport for Dependent invocations, and helps provideauniformprogramming model.CHAPTER 3— Implementation oftheObjectPropertyScheme533.7 Parallel Invocations and Property SupportAs mentioned in Section 2.1, the Raven language contains specialconstructs to facilitate user-directedparallelprogramming. There arethreeprimary forms ofparallelismprovided: companioninvocations, early replies, and delayed results. The work on parallelismfocused only on the Controlledproperty, in anenvironmentthatpre-datedDependency. Mostofthe thought givento thesefeatures was therefore directed towards their impact on concurrencycontrol [2]. Integrating thenew property scheme (especially the notion ofDependency)with Raven’s support for user-levelparallelism has presented several challenges, many of whichare yet to be fully resolved. For afurther discussion ofthese issues, and alternate implementations to thosechosen, see Chapter 5.Property informationis keptby the thread, so it is notpossible toperforma Dependentinvocationusing aparallel threadofexecution.There is nofacility by whichproperty informationkeptby onethread canbepropagatedto anotherthread, although some schemesuch as the one usedforremoteinvocations (see Section 3.3.3) couldpotentiallybe adapted. Consequently, multi-threadedtransactions are currently not supported.3.7.1 Companion InvocationsCompanioninvocations are invocations which are startedfromandexecutedin parallelwiththe currentthread ofexecution. In the Raven language, executingthe statement{ someobject.someMethod() } .startO;creates a companion thread whichwill invoke the someMethodmethod on someObject. Thetarget ofthe invocation (in this example, someObject) is treated as ifit were not Dependent,even ifthe reference to the object is marked Dependent.Ifthis object makes subsequentinvocations on Dependent objects, they will form their ownDependent chain, and the target object thecompanion thread invoked on willbe the root ofthechain.CHAPTER 3—Implementation ofthe ObjectPropertyScheme54Another way to achieve parallel execution in a mannersimilarto a companion thread is forthe user to simply create a new instance ofthe Threadclassand have it invoke a method on anobject. As with a companion thread, the initial invocationofthis thread is treatedas ifit were notaDependent invocation.3.7.2 Early ReplyEarlyreply is amechanismby which amethodcanreturn aresult to its invokerbutcontinueexecuting inside the method. The statementresult (value);will returnvalue to the caller, and a new thread will be created at this pointto 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 objectin which anearly reply is done. The initial invoker must give up the lock it acquired, andthe spawned threadmust acquire the lock. The question arises as to what happens if the objectis in a Dependentchain. The invoking thread will not give up its lock, but the spawned thread willneed to acquirethe lockbefore it can do any work. Consider also a Recoverable object in whichan early reply isdone. It is unclearwhat should happen ifarestore statement isencountered by the new threadexecuting after the result has been returned: should the objectbe restored to the state it was inwhentheresultstatementwas executed, ortothe stateithadprior tothe initial methodinvocation? What ifthe object is part ofa Dependentchain, and an object above it in the chain executesa restore? How can work done by the spawnedthread be restored properly, especially if thethread is still executing inside the object? Similarproblems relate to the Durable and Persistentproperties: should the object state be writtento disk at the point of the result, when thespawned thread terminates, or both? Ifonly atthe point of the result, then changes madeby theCHAPTER 3— Implementation oftheObjectPropertyScheme55spawned thread could be lost; butiftheobject is Durable and part ofa Dependentchain, then theobject state cannotbe writtenby the spawnedthreadwhen it terminates, since theobject statecanonlybe written along withthe objects comprisingthe initial Dependent chain.Rather than attempt to resolve all theseissues, and to simplify the implementation,earlyreplies are ignored in some circumstances.Ifthe object is part of a Dependent chain,or has theRecoverable, Durable, or Persistent properties,then the result statement will simplysave thevalue to be returned to the caller and use itas the return valuewhenthe method terminates(ignoring any subsequent value specified by areturnstatement as the result to return). A newthreadis not created; instead, the current thread continuesexecution, and control is not returned tothecalleruntil an actualreturnstatement is encounteredor execution ofthe method finishes.Thischoice decreases the parallelismof the system, but ensures its correct operation whenan earlyreply is encountered.3.7.3 Delayed ResultDelayed result allows the execution of a methodto finish with the expectation thata differentthread will actually provide the result to returnto the caller. The statementleave;acts like a return statement, except thevalue to be returned to the caller is not taken fromthebody ofthe method but is insteadsent to the current thread by another thread.Ifthis value hasn’tyetbeen sent, the currentthread blocks(and control is not returned tothe caller) until the value isreceived. A thread sends a return value toanotherthreadusing theresult statement:result thread value;sendsvalue as the value to return tothe thread thread.CHAPTER 3—Implementation ofthe ObjectPropertyScheme56To properly implement delayed result, any locks heldon the object (both concurrency control locks and cluster locks) must be released whenthe leave statement is executed. Thisisbecause it maybe necessary foranotherthreadto enterthe objectin orderto performtheresultwhich will send the value to the waitingthread. However, ifthe object is in aDependent chain,locks are not supposed to be releaseduntilthe top-level invocation completes. IftherequirementsofDependency are maintained, then using a delayedresult may bring the system intoa state ofdeadlock; iflocks are freed, then the semanticsofDependency are not preserved.Since delayedresultprovides programmer-specifiedparallelism,thecurrentimplementationwill release any local locks when a leavestatementis executed, even ifthe objectis inaDependent chain. It is assumed that the programmerwill take into account that locks willbe releasedwhen writing code that executes a leave,and will not attempt to use such objects in transactions, since a significantconsequence ofreleasingthe locks is that serializability will be lostwhenanothertransaction invokes on the objectwhileathread is suspendedwaiting for aresult.Releasing local locks whena leave is encountered creates the potentialfor an additionalproblem. Consider athread Twhichissuspendedin an object0waitingfor aresultto return to itscaller. It’s possible for another thread T’ to acquirethe locks on 0and assign 0toan instancevariable marked inherits, or de-assign0 from such an instance variable.When Tresumes, theproperties of 0 have changedfrom what they were when the invocationon 0began. Propertypost-handlers are executed aftera suspendedthread resumes, creatingapotential mismatch in theexecution by Tofthe property pre-and post-handlers. The current implementationthereforegenerates a runtime error if an objectwhich contains suspended threadsis assigned to an instancevariable marked inheritsorpartof.CHAPTER 3— Implementation ofthe ObjectPropertyScheme573.8 UserPropertiesUser properties are supported in the same way as thesystemproperties, through the execution ofpre- and post-handlers. The invoke routines and the system pre- andpost-handlers are all writtenin C. Allowing programmers to write their pre- and post-handlers inC as well is possible, but isfraughtwithproblems. Ifusers are allowedto write in C, theycan become tempted to modify system data structures. Furthermore, programmers would need to know detailsofthe Raven implementation in orderto access object instance data; however, these detailsmay change, introducingbugs into the user code.Giventhese considerations, user pre- and post-handlers are therefore supportedby performing invocations on the object. The basic Object class supports four(empty) pre-methods andtheir correspondingpost-methods:behavior preUserN(dependentlnvoke: Int);behavior postUserN(dependentlnvoke: mt1 isDependentRoot:Int, hasProp: Int);WhereNcan be either 1, 2, 3, or 4.The integerparameterdependentInvoke which is passed to theuserpre- and post-handlers is set to either True or False (predefinedboolean values supported by the Raven language) depending upon whether the current object is Dependentupon its invoker. Similarly, theparameter isDependentRoot will beTrue or False depending upon whether the currentobject is the rootobjectofaDependentinvocation chain.This information is providedto theprogrammer so thatuserproperties can alsobe designed to take advantageofDependentinvocations.In such circumstances, the programmer mayneed to subclass the Thread class so thatstateinformationforthe userproperty canbe keptin thethread alongwiththe informationfortheControlled, Recoverable, and Durable properties. Theinteger parameterhasProp is set to True orFalsedepending on whether the currentobject actually has theuserproperty. This flag isnecesCHAPTER 3—Implementation oftheObjectPropertyScheme58sary since the post-methods will be executed whenisDependentRoot is True, even whenthe object does not have that property. Without thisflag, the programmer would have no way ofdetermining ifthe root object of a Dependent invocationchain actually had one ofthe userproperties.The pre- and post-methods will be invoked on an instance whichhas user properties. Whena programmer wishes to implement a user property fora class, the programmer must overridethese methods in the class. The invocations ofthe pre-methods must be done in such a way thatthey do notresult in a continual recursive executionofthe pre-methods; similarly, the post-methods mustbe executed in suchaway that they don’tcause the pre-methodsto execute. This is doneby calling themethodcode directly, bypassing the property supportroutines. The pre-handlers areonly executed on the machine where the object resides, so thereis no worry that the object datawill notbe local.Although self-invokes are normally considered dependent invocations,the pre- and post-methods are not considered dependentinvokes. Since theuser pre-methods are executed after theRecoverability pre-handler, anyrestore statementexecuted inside the object methodcode willrestore the object to the state it was in prior to theexecution ofthe pre-methods. This may createsome difficulties, since the current implementationdoes not re-execute the pre-methods (and thepost-methods will be executed when the objectinvocation finishes). The issues surroundinguserproperties are furtherexplored in Chapter5.Since thepre- andpost-handlers arewrittenby theuser, the systemcannotmake any guarantees about the orthogonality ofuser properties.No tools havebeen written to test for suchorthogonality.CHAPTER 3—Implementation ofthe ObjectPropertyScheme593.9 Status ofthe 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 thereare properties. The properties whicharecurrently implemented are the following:• Controlled• Recoverable• Persistent• Durable• Immutable• User properties (as describedin Section 3.8)Details ofthe implementation ofthe Controlled property canbe found in [1]. Details oftheimplementation ofthe Recoverable property canbe found in[71.Details ofthe implementation ofthe Persistent and Durable properties can be found inChapter4.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 Persistentinvocations (Section2.6.1), the implementation treats them inthesame manner as objects which are Durable.Dynamic property inheritance, through boththeinherits and partof keywords, isfully supported. This includes the case whenthe assignmentto an instance variable markedinheritsorpartof is recoverable: ifarestorestatement is encountered in the current Dependentcalling chain, the object property setswill becorrectly restored, and all data structures(such as lock structures) used in the implementationofsystem properties will be correctlyupdated. However, the system only allowsproperty inheritance from local objects (i.e. objects whichare in the same address space).Object Storage: Details ofthe Durable andPersistentProperties4.1 ObjectStorage OverviewObjects in Raven are normally volatile; they exist only in memory,and persistonly as long as theactive process which created them (or until they aregarbage collected [1]). When an object isgiven either the Persistent or Durable properties, theRaven system will ensure that a copy oftheobject’s instance datawill be written to disk. Since the Persistentand Durable properties functionin almost identical ways (see Section 2.4 fora 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 storableare meant to be those which have either the Persistent or Durable properties.The object storage systemprovidesthe following features:60CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties61• Reference swizzling: All referencesto other objects are capability pointers,which point to the location in memory wherethe object’s capability structureresides. All references toan object must be converted to unique identifierswhich correspond to the object. This allowsthe system to reload the object atany position in memory, as the unique identifierscan be translated back to thenew capability pointer.• Whole object storage: Objects must be storedin their entirety in an atomicfashion. Ifthe object’s stateisn’twritten atomically todisk, afailure duringthediskwrite couldresult in an inconsistentversionoftheobjecton disk, and subsequently an inconsistentversion ofthe object will be loadedinto memory.• Lazy loading ofobject data: When a reference to an object is unswizzled,ifthat object is not currently in memory, the runtimesystem will not fetch theobject data immediately. The object’s instance data willbe fetched only whenit is actually needed, i.e. when an invocation is made on the object.• Object clustering in storage: Objects which comprisea Part-Of cluster arestoredtogetheron disk, and loadedtogetherfromdisk.Although the Raven runtime system provides garbage collectionfor in-memory objects, nogarbage collection is currently provided for objects instorage. 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 whenit no longer inherits that property it will be removedfromdisk storage).4.1.1 Globally Unique IdentifiersTo implement reference swizzling,the system must provide a globally unique identifier,or GID,forevery storable object. GID5 arealso useful for accessing remote objects,but in the absence ofobject mobility and persistence the object’slocation information can be usedto provide a uniqueidentifier. The original version of Ravenused location information as the globalidentifier, andwas therefore unsuitable as atrueglobally unique identifier.CHAPTER 4— ObfectStorage: DetailsoftheDurableandPersistentProperties 62The actual GID of an object is a 128-bit value composedoffour distinct 32-bit fields (seeFigure 9). The first field containsthe IP address ofthe machine on which the objectwas created.The secondfieldcontains theportnumberto whichtheRavenWorldwhichcreatedthe objectwasattached. The third and fourth fields are incrementalcounters. The third field is incremented onceupon each startup ofa RavenWorld, and the fourth isincremented once foreachGID assignedbythe World. The fourth counteris resetto zero upon eachstartup ofa World.{u_long creator;u_long world;u_long generation;u_long name;creator: IF address ofcreatormachineworld: Port number ofRaven Worldgeneration: Raven World incarnationcountername: Per-incarnation GID assignment counterFIGURE 9. GID Structure.A GID is assigned to every storable object. Anobject which is referenced from anotherRavenWorld(i.e., forwhich aProxyobject [1] exists in the otherWorld) is alsoassignedaGID.GID5 are not normally assignedat object creation time unless the object is storable.The object’scapability structure (see Figure6) contains apointerto a structurewhichinturncontains apointerto the GID structure (see AppendixA.6). If the object does not havea GID, the pointer in thecapability structure will point to NULL.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties634.2 Storage ModelThe basic storage model used is outlined in Figure 10. At the highest level are the Raven objectsthemselves, which existin main memory. Each storableobjecthas an associatedStorageManagerobject (seeFigure 11), which is an instanceofthe StorageManagerclass (see Appendix B.2).The storage manager is responsibleforoverseeingthe storage ofthe object’s instancedatato disk,as well as converting storeddatainto user objects.Storable Objects in MemoryStorage ManagersTDBM ManagerLocal DiskFIGURE 10. Object Storage Model.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties64ObjectsStorage________SwizzledManager DataFIGURE 11. StorageManager 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 storeskey!value pairs. TDBM will ensure that all the datapresented to it is written in an atomic fashionto 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 oftheTDBMIanager class (see Appendix B.5). The TDBMmanager object is accessible insideRavenapplications as the global objectidentifierTDBMrnanager. The TDBMmanager objectwritesthedata for all the objects in the Raven World to a file specific to that World.Ifthe Raven World isshut down and a new instance of Raven is launched with the same World identifier(i.e., on thesamemachine using the sameport number as the previousWorld), it isconsideredthe sameWorldand will use the same file.TDBM cannot guarantee atomic updates of data ifthe databasefile is located across NFS.Object storage should therefore be done on a diskphysically mounted on the same machine onwhich the Raven World is running, or the systemwill be vulnerable to NFS failures. The localdirectory under whichTDBM should store its files is determinedat startup time by examining theenvironmentvariable RVSTORAGEPATH. Ifno such environmentvariable exists, a default valueis used; however, this default value is not guaranteedto exist on any particularhost.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties65Encoded TDBM_______DiskData ManagerFIGURE 12. TDBM ManagerRole.Each Raven World has an associated GlDmanager object (seeFigure 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 memoryof the capabilitystructure forthe object. This map is necessary during unswizzling,when GDsmustbe converted to capability pointers.• Itcreates capability structures for objects loadedin fromdisk.• Itintercepts invocations made onobjects currently notin memory and interactswiththe TDBMmanagerto fetchthe objects fromdisk.4.2.1 Object Storage EventsAfter an invocation which modifies theinstance data of a storable object completes,the object’sinstance datamustbewrittento disk.This involves the following actions:(1) The object’s storage manager isnotified that an invocationoccurredon theCHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties66Fetch ObjectRequestsLoadFromDisk RequestsAssign GID RequestsDecode DataRequestsFIGURE 13. GIl) ManagerRole.object.(2) The storage manager instructsthe object to encode its instance data.(3) The storage manager adds the information in the object’s capability structureto the encoded data.(4) Theencoded datais passedto the TDBMmanager along withtheGDoftheobject, which is used as the key underwhichthe data is stored.(5) TheTDBMmanagerwrites the data to disk.4.2.2 Object Loading EventsWhen an invocation is made on an object which is not in RAM,the objectmustbe loaded in fromdisk. The capability structure used forobjectsnot in RAM is a “skeleton” capability structure: theonly fields ofthe structure which are filled in arethe GID and the invoke routine (see Figure 6).The invoke routine used by skeletoncapabilities is a special routine called Fetchlnvoke.Fetchlnvokeensures the object datais loaded into disk and that the skeleton capability strucCHAPTER 4—OblectStorage: DetailsoftheDurableandPersistentProperties 67ture is filled in before allowing the invocation to proceed. The exactsequence ofevents involvesthe following actions:(1) TheFetchlnvokeroutinecalls the GlDmanager, and asks itto load in thedataforthe object with the GID found in the skeleton capability structure.(2) The GlDmanagerpassesthe GID ofthe objectto the TDBMmanager.(3) The TDBMmanager fetches theencoded data stored underthatGD fromdisk.(4) TheGlDmanagerextractsthe capability information and fillsin the skeletoncapability structure, including replacing theFetchlnvoke function withthe appropriate invoke function for the object.(5) The GlDmanagercreates a storage managerforthe object, and passes theencoded data to the storage manager.(6) The storagemanagercreates an objectofthe appropriateclass, andhasitloadits instance data using the encoded data.(7) During decoding, all GIDs are passed to the GlDmanager to be unswizzledand turned into capability pointers. Ifno capabilityexists fortheGID, theGlDmanagercreates a skeleton capability structure for the object.4.3 Implementation DetailsThe StorageManagerobjects, GlDmanager, andTDBMmanagerare all Raven objects andinteractwith each other using normal object invocations. Muchof the implementation of these objects,however, is directly in C, although the Raven languagehas been used where possible. As anobject’s instance data is encoded and the capabilityinformation added to form the completeencoding of the object, Raven Integersare used to hold pointers to the data for passingbetween a StorageManager, the TDBMmanager,and the GlDmanager.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties 684.3.1 Object EncodingWhen a Storage Managerneeds to get the encoded formofan object, it asks the object to encodeitself and return the encoded data. Similarly, a Storage Manager will providean object with apointer to encoded data, and have the object load its instance datausing the encoded data. TheObject class provides two basic methods:• behav enCodeData() : mtThis method traverses the object’s instance data and writes an encoded versionof the data intomemory, swizzling all object references and encoding primitive integers andfloating point numbers (see below). A pointer to the location ofthe data is returned.• behav deCodeData(data:Int);This method replaces the object’s current instance data with the data obtained by decodingthedata pointerpassed in.The formatofabuffercontainingencodeddatainmemory is shown in Figure14. Thebufferbegins with an integerrepresenting the total length in bytesofthe buffer (including the fourbytesneededforthe integer), followedby the encoded instance data.Total Length DataFIGURE 14. Formatofencodedbuffer in memory.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties69Raven currently supports three different types of instance variables: mt (simpleinteger),Float (floating point number), and cap (object reference). While encoding(or decoding) anobject, the type of instance variable is determined by examining the definitionof the object’sclass.Ints are stored as instance variables in their (usually) 32-bitmachine-dependentrepresentation [1]. This allows integer operations to be efficient. They are encoded by simply copyingthem directly into the encoded buffer. Conversion into an external representation (suchas thatobtained using XDR [25], which is currentlyused to encode requests and replies forremoteinvocations) 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 ofa 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 numberinto the encodedbuffer.Object references are swizzled by writing out the GID ofthe object to the encoded buffer.Upon decoding, the GID is converted to alocalcapability by the GlDmanager. Ifthe objectreferenced is not storable, zero values are written to the encodedbufferin place ofthe actual fields ofthe GID (which may noteven existfor anon-storableobject).Since anon-storable object will notsurvive systemrestarts,ifan actual GIlD were storedtheencodedobjectwould contain areferenceto an objectwhichno longerexists. Upon decoding, azero-valuedGID istreated as areference tothenil object. This practice precludes the use ofthe object storage system as a mechanism forproviding objectpaging.The currentimplementationrelies upon the fact thateachofthe values storedin the encodedbuffer are amultipleoffourbytes. Iftheencoded bufferitselfis allocatedon afourbyteboundary(true for the current implementationofthe RavenMALLOC()macro), then the values (especiallyCHAPTER 4—OblectStorage:DetailsoftheDurableandPersistentProperties 70integers and floating point numbers) can be easily written to and extracted from the buffer. Sinceclass definitions can vary widely, the size and format ofdifferent encoded buffers is highly variable, and the object class mustbe 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 inheritancerootmust alsobe stored. Storing this information allows the capability structure to be rebuilt upon object loading, and provides the class informationnecessary for decoding the data. Figure 15 shows the layout ofthe 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 alongwithits length. Ifnecessary, padding is added afterthe 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 propertymaskto be stored mustbe calculatedby traversing up the inheritancetree until the top-moststorable 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 ofthe encodedbuffer shown in Figure 14. A final pad, ifneeded,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 offour bytes, and the class name with its pad will be amultiple offourbytes, there shouldnever actually be aneed for atrailing pad.The process ofadding 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— ObjectStorage: DetailsoftheDurableandPersistentProperties 71NameParent Inh_rootThClass Name Pad Properties DataPadingGID GIDFIGURE 15. Format ofafully encoded object.4.3.2 Storage Manager ImplementationObjects maintain apointer to their storage manager insidetheircapability structure. When a storable object is created, or when an object inherits the Persistentor Durable properties, the objectwill be assigned a Storage Manager. All ofthe storable objects ina Part-Ofcluster each use thesame StorageManager.Storage Managers maintain a “cached” version ofthe encodings forevery object they manage. These caches serve twopurposes:(1) They allow theStorage Managertocomparetheobject’scurrentstatewithitsprevious state, to determineifthe object state has actuallychanged. Iftheobject is unchanged, there is no need to write theobjectto disk, thus savingsignificantperformance overhead.(2) They allow the StorageManagerto submit all the objects in aPart-Ofclusterto the TDBMmanager for storage at once.Ifthe Storage Managerdidn’tmaintain cachedversions, itwould haveto encode and encode eachobject inthe clusterevery time it neededto write the clusterto disk. Furthermore, ifthe Part-Ofclusterlock is ever abandoned,alack ofcachedversions couldforce the StorageManager toacquire a lockon every object in the clusterbefore encoding each object. No clusterlockimplies multiple threadscouldbe inside the cluster, so the ClusterManagermay have to wait a significantamount oftime in additionto increasing the likelihoodofdeadlock.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties 72The encoded data of an object is kept by a Storage Manager insidean object ofthe SMEntry class (see Appendix B.3). An SMEntry object containsthe object capability pointer, apointer to the object’s encoded data, and the length of the encodeddata. If a Storage Managermanages multiple objects, it keeps the SMEntry objects in adynamically sizeable array. TheSMEntry forthe rootobject ofthe Part-Ofcluster is always thefirstobject in the array.4.3.3 TDBMmanager ImplementationA Storage Manager presents the encoded data streams to the TDBMmanager forwriting to disk.The encoded data is packaged into an object which is an instanceofthe class TDBMDatum (seeAppendix B.6). A TDBMDatum object is an object encapsulation containingtwo of theTDBMDatumStruct data structures used by the TDBM library. It containsfour integer values:one integer value used as a pointer to the data, a second holds the datalength, a third is used as apointer to the key under which the data is to be stored, and the fourth containsthe length ofthekey. A TDBMDatumStruct also requires alignment information, butdata and keys are alwaysassumed to be aligned on a fourbyte boundary. When a Storage Managerinvokes on the TDBMmanager, it creates a TDBMDatum object and sets the datapointer to point to the encoded datastored in the SMEntry object. A pointer tothe object’s GIJD is used as the key under which theobject is to be stored. If the Storage Manager manages multipleobjects, it passes an array ofTDBMDatum objects to the TDBMmanager. Each TDBMDatumobject occupies the same position in the array passed to the TDBMmanager as the SMEntryobject from which the TDBMDaturn was formed occupies in the array kept by theStorage Manager. As such, the TDBMDatumobjectcontainingthe encoded dataforthe root objectofthe Part-Ofclusterwill be the first objectin the array passed to the TDBMmanager.The TDBMmanager stores data to disk inone ofthree formats, which are shown in Figure16. Thebasic structure ofall three formatsis count data,where count specifiesthe numberofobjects stored in thedata. The keyunderwhich the datais stored is an objectGID.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties 731•(EncodedObjecGIDJGIlD1DataGIDD3:(GIDnD0 GID1FIGURE 16. Formats ofdatastorage on disk.Formattype 1 is the mostbasic, and shows how a single TDBMDatumobject which is presented to the TDBMmanager will be stored. Thecount field is one, since only one object isstored. Thedatafield contains theencodeddatathatwaspassed intheTDBMDatumobject. Thekey under which this data is stored is the key containedin the TDBMDatum object, which is theGIlD ofthe object.When the TDBMmanager is presented with an arrayofTDBMDatum objects, it stores allthe objects together on disk in onecontinuous block, as shown in format type 2. In thiscase,count contains a count ofthe number ofencoded objectsstored in the block, which is equal toKey2:(1 Encoded ObjectCount GIlD1 Size Data GID Size Data)CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties 74the number ofTDBMDatum objects in the array. Itis followed by <count> tuples consistingofthe key under which the object was to be stored, thesize of the object’s encoded data, andtheencodeddataitself. Theentire blockis stored using the key foundin the firstTDBMDatumobjectofthe array, which will be the GID ofthe root object ofthe Part-Ofcluster which is being stored.Storing the size of the encoded data allows the TDBMmanager to quicklytransform a block ofclusteredobjects into individual TDBMDatumobjects, one for each storedobject, without havingto know the format ofthe encoded data.When an array of TDBMDatum objects are to be stored, all the encoded objects willbestored using the GID ofthe root object as the key. To allowthe system to locate the other objectsin the cluster, the TDBMmanager stores a data block of format type3 under the GID of theseobjects. The count field is set to zero, indicating that the data is the actual key underwhich theobject’s data is stored.When an object is to be loaded in from disk, the TDBMmanageris presented with aTDBMDatum object with only the instance variables corresponding tothe key set. The TDBMmanager uses the key information to load in the associateddata from disk. The data is examinedto determine which format it is in. Ifthe data block is offormat type3, the TDBMmanager usesthe storedkey to fetchthe actual data. Ifonly asingleobjectwas storedunderthe key, theTDBMmanagerreturns the passed in TDBMDatum objectwiththe integersforthe valuepointerand sizeset to the encoded data. If multiple objects werestored in a cluster under the key, an array ofTDBMDatum objects is returned. Ifno object isstored under the key presented, the TDBMmanagerreturns thenilobject.Because Raven is multi-threaded, the TDBMmanagerhas the Controlledproperty to ensurethat accesses to the disk are serializedand that the whole system does not enter a blockedstatewhen aparticularthread is blockedwaitingfor a lockfromTDBM itself.CHAPTER 4— ObjectStorage:DetailsoftheDurableandPersistentProperties754.3.4 GiDmanager ImplementationThe GlDmanager interacts with the TDBMmanagerto load encoded objects from disk. If theTDBMmanager returns nil to the GiDmanager, the GlDmanagerattempts to find the objectsomewhere on the network. The creator andworldfields ofthe object’s GID are examined,and a remote invocation is made on the GlDmanager ofthe Raven World at that location in anattempt to find the object. When object migration is implementedin Raven, a broadcast or othermechanism will be needed to find the actual location ofthe object,since there will be no guarantee that an objectwillremain in the World in which it was created.Ifthe TDBMmanager returns encoded data to the GlDmanager,the GlDmanager begins theprocess of unencoding the object data. First, it createsa Storage Manager object to manage thestorage of the object (or objects, if a cluster of objects were returnedby the TDBMmanager).Next, it fills in the capability information for each object, creating acapability structure first ifnecessary. Any necessary locks (including a cluster lock)are created. The encoded data is thenpassed to the StorageManager so the object instance datacan be decoded.As described in Section 4.2.2, capability structures that existfor objects not currently inRAM use a special invoke routine calledFetchlnvoke.When aFetchlnvokeis performed,the first action ofthe GlDmanager is to ensurethatthe object datahas not already been loaded in.Although the GlDmanager is controlled against concurrentaccesses, multiple Fetchlnvokescould be performed on an object before thefirst has completed. The final action ofthe GIDmanager is to set the invoke routineto the normal invoke to be used forthe object.The GlDmanageralsomaintains amappingofGIDs to capabilities. This allows it tofindthelocal capability pointer for any object basedupon its GID. The map is simply a hashtable thatassociates the four integer fields ofthe GIDwith the capability pointer ofthe object.IIIIISc[10], a table package which performs{4 integer)—>{1 integer) mappings, is used to managetheCHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties76hashtable. Ifthe GlDmanager is asked forthe capabilitypointerfor aparticularGID, and no suchcapability currently exists, the GlDmanager createsa skeleton capability structure whose invokeroutine is Fetchlnvoke; it then returns a pointerto this structure. The GlDmanager willturnthis capability structure into a Proxy object ifthe object cannotbe found on the local machinewhen the GlDmanager attempts to load the instancedataofthe object.4.3.5 Implementation Differences Between the Persistentand Durable PropertiesIn the current implementation, the Durable and Persistent propertyhandlers are almost entirelyidentical. Objects have only one Storage Manager, which actsforeither the Durable or Persistentproperties (or both, if an object actually had both properties). In the caseofDependent invocations, bothproperties are handled in the same way, and conformto the Durablenotion ofstorage:control will not be returned to the caller until all the objects have been writtento disk. The onlycurrent difference between the implementation ofthe two propertiesis that in the case ofPersistent objects, a new thread is spawned to perform the workof storing the object to disk, allowingthe original thread to return immediately. This does providefaster performance for the user, butdoes notprovide any 110 optimizations that mightbe availableby delaying writes to disk, such asallowing some updates to be done only in RAM. Thiscan be accomplished with an active threadinside each Storage Managerwhichperiodically writesthe cached data to disk.4.4 Dependent Invocations onStorableObjectsWhen storable objects are part of a Dependentchain, the Raven system must delay writing theobjects to disk until the top-level invocationcompletes. Furthermore, the objects mustbe writtenatomically; i.e., either all the objectsget written to disk, or none ofthem do.To supportDependentinvocationson storable objects, eachThreadobjectkeeps alistoftheStorage Managers for the storable objectsit invokes upon in a Dependent chain.A pointerto thisCHAPTER 4— OblectStorage: DetailsoftheDurableandPersistentProperties77list is kept in the Thread’s storage_chaininstance variable. Eachentry in the storage_chain(seeFigure 17) is a structurewhichincludes thedependentlDoftheDependentchain,thecapofthe Storage Manager, and a list ofthe objects which are managed by that Managerand whichhave been invokedupon during the current Dependentinvocation chain. The DurableandPersistent post-handlers append the current invokee’s Storage Manager to this chain. IftheManager isalready on the chain, the current invokee is appended to the list of modifiedobjects kept for theManager.struct STORAGE_INFOstruct STORAGE_INFO*next;struct STORAGE_INFO*previous;mt dependentlD;cap manager;LIST*objects;FIGURE 17. Formatofstruct STORAGE_INFO data structure.Normally, the TDBMmanager expects to perform the storage fora single Storage Manageras one transaction. In a Dependent chain, however, multiple Storage Managers musthave theirdata stored by the TDBMmanager using the same transaction identifier.To accomplish this, thefollowing steps are taken whenthe top-level invocation ofthe Dependentchain completes:(1) A transaction identifieris acquired fromthe TDBMmanager.(2) Forevery StorageManagerinthestorage_chain,thelocalcacheofeachobject in the objects list forthat Storage Managerisupdated.(3) The StorageManageris directed to writethelistofcachedobjectsto storage,CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties78using the transaction identifier acquiredin step 1.(4) The TDBMmanageris directedto committhe transactionassociatedwiththetransaction identifier.4.4.1 Remote Dependent Invocations on StorableObjectsThe semantics for Dependency specify that all the objects in the Dependentchain will be storedtogether. This requires that when Durable objects in a Dependent chainare in different RavenWorlds, a two-phase commit protocol (or similar protocol) be used to ensure thatall the objectsarewritten to diskatomically.In the current implementation, a two-phase commit protocol is not implemented,as it isbeyond the scope ofthis thesis. Instead, each ofthe Raven Worlds involved ina distributedtransaction will write their data separately from the other Worlds, although atomically withineachWorld.4.5 Storage of Collection Class ObjectsThe Raven class library supports avariety ofclasses which are collectionsofother objects. Theseclasses all inherit from theCollectionclass, and include theArray,MemoryArray,List,Set, and String classes (see [1] for a full description ofthe Raven class library,including theCollectionclasses). The implementations ofthese classes oftenrely upon other classes (usually an instance ofMemoryArray at the lowest level). Forexample, the String class uses anMemoryArrayobject to store the actual charactersofthe string.This implementation presents a problem for objectstorage. Consider a Persistent Stringobject. Ifthis object is encoded normally, the actual charactersof the string will neverbe stored,as these actually reside in the MemoryArray inside theString. In fact, althoughthe String itselfisPersistent, the MemoryArray is not, andso the encoded data will contain a reference to thenilCHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties 79objectand noteven totheMemoryArray whichcontains the characters.Similarproblems existforthe other Collection classes. MemoryArray hasits own storage problem: its implementation is done directly at the C level, so normal Raven statementscannot be used to swizzle aninstance ofMemoryArray.One solutionis to attempt to use the Part-OforInheritsreferenceswhendesigning theCol-lection classes. For example, the String class can indicate thatthe MemoryArray objectshould be Part-Of the String, so if the String is Persistent then the MemoryArraywill be also.There are several problems with this approach, however. If Part-Of isused, then the Collectionclass object will be given a concurrencycontrol lock, which will decrease theperformanceofoperations on the object. IfInherits is used instead, then the object willbe stored in pieces ondisk, and multiple fetches will be required to load it into RAM. A more fundamentalproblem isthat althoughthis schemewillworkfortheStringclass, itwill currentlynot workforanyoftheCollection classes which are implemented by composing multipleCollection classobjects together. The Array class, for example, is implementedas a multi-way tree, usingobjects ofthe class FixedArray. At any given level, aFixedArray may contain elementsoftheArray or another FixedArray. Although the top level FixedArray usedby theArrayclass can bespecified as being Part-Ofthe Array, there is no mechanismby which other FixedArrays placedinto the top level FixedArray can be declared as being Part-Ofalso. Therefore, the Part-Of treestops after one level, and parts ofthe Array will not be Persistent. Onesimple solution is to reimplementtheArrayclass (and the otherCollectionclasses) in such a way that Part-Ofcanbe used so all components ofthe class can inherit properties.Indeed, when a class is written allobjects which are used to implementthe class shouldbe defined as Part-Of. Another solution is touse the techniques described in Section 5.4 to implementtheCollectionclass objects, whichwould allow the Part-Ofrelationshipsto extend downward as many levels as necessary to includeall the component objects oftheCollectionclassobject.CHAPTER 4— ObjectStorage: DetailsoftheDurableandPersistentProperties80To allow String objects to be properly stored, theString and MemoryArrayclassesoverride the enCodeData and deCodeData methodsfound in the Object class with specialversions which will properly encode and decode thecontents ofa String or MemoryArray object.This scheme can be adopted for all the different Collectionclasses, although at present theenCodeData anddeCodeDatamethods have beenoverridden only in theStringandMemoryArrayclasses.4.6 Object Name ServiceOnce object storage has been implemented, some mechanismby which users can identifyand name objects mustbe provided, so that aftera systemreboot particularobjects thathavebeenstored to disk can be reloaded. Otherwise, the user willnever be able to find the objects stored todisk. Using ASCII (string) names is a natural convention fornamingobjects (as they are fornaming Unix files), and much less cumbersome forusers thanrequiringthatthey rememberthe GIDsofthe objects which they are interested in. A rudimentaryname server, which provides string toGID mappings, was developedto assist in the testingofthe objectstorage system. Ideally, Ravenshould support a well-known persistent object accessiblefrom the Raven System object whichprogrammers can use to provide their own nameservice.CHAPTER5 Discussion andFutureWorkThe design and developmentofthe Ravenproperty scheme is extensivebut far from complete. Inparticularthe implementation has brought to light many issues andpossible directions for futureresearch.5.1 Property Scheme DesignThe Raven system has experienced only limited use, which has been confinedto answering specific research questions. Until Raven is fully implementedand used as the basis for developingdistributed applications which rely on all aspects ofthe 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 inparticularthe usabilityofthe currentlyunimplementedproperties will notbe fullyknownuntil thesystem is extensively used. In the testing which hasbeen performed, the system behaves exactlyas specifiedin theproperty semantics. In particular,transactionalprocessing can be accomplished81CHAPTER 5— DiscussionandFuture Work82by providing objects with the Controlled, Recoverable,and Durable properties, and placing theobjects in Dependentrelationships.There is one problem with the current mechanism for providingtransactions, however. TheControlled property is designed to prevent concurrentaccess to an object by multiple threads.Now considerthe following scenario, as shown in Figure 18. ThreadT inside objectA, performsa Dependent invocation on object B. It then performsa non-Dependent invocation on object C,which then makes a Dependent invocation on object Bagain. The invocation from A—>B is onetransaction, while the invocation from C—*B is another (the invocationfrom A—>C is not part ofthe first transaction, since Cis not Dependent on A). The problem ariseswhen the invocation onCreturns: ifarestore statement is executedinsideA, theinstance dataof Bwillbe restoredtoa previous state as well. However, the state B will be restored to is inconsistentwith the transaction C—*B, since the state of C(which will not be restored) mayhave relied on the state B was inat the time ofthe transaction.TA— II,IiIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIuII,II — —Inon-DependentDependentCCDependent[liiiBFIGURE 18. Multiple Transactions Modifyinga Single Object.CHAPTER 5— DiscussionandFuture Work83This problem exists because ofthe particular interaction ofthe semantics ofDependent andControlled. The runtime system has a mechanism by which it candifferentiate between invocations on an object done by the same thread but as partofdifferent Dependent invocation chains,by using the Dependent id. to restrict access to the object. However,this does not solve theproblem ofthe semantics, which allow this situation to occur. A solutionis to introduce the semanticnotion ofa invocation identifier (or transaction identifier) whichis assigned to every invocation.Invocations in a Dependent chainwould all have the same invocationidentifier. The semantics ofthe Controlled property would then be modified to control accessto an object based upon theinvocation identifier, and not the thread. This isalso only a potential problem when the object Bhas the Recoverableproperty,butdue to the orthogonality ofthe propertiesthesystemcannot useits knowledge ofthe properties of B to allow the above situationto 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 newfeatures and capabilities. Potentialfuture features include:• Property masking: The ability to “maskout” certainproperties;that is, amechanism by which an instance can refuse to be assigneda property which wasspecified at creation time orinherited from another object.• Selective inheritance: The ability to selectivelybequeath a set ofproperties atruntime to an instance. Currently,property inheritance requires that all properties be inherited. An extensionofthis feature would allowany setofpropertiesto be dynamically assigned to an object, by specifyingthe properties when theinstance variable is declared in the class definition.• Alternatepolicies forsystemproperties: Theability forthe userto choose fromamong a set ofdifferent versions ofthesystem properties, which each providedifferent semantics. For example,the current semantics for Replicated onlyprovide weak consistency. Thesystem could instead provide both weakly andstrongly consistent Replication,and allow the user to choose either policy forCHAPTER 5— DiscussionandFuture Work84an object. Other possibilities include different storagepolicies for the Persistentproperty, each ofwhichtrade offbetween more immediateupdates to diskandproviding more updates in RAM.User specified property ordering: as mentioned inSection 3.2, the correctbehavior ofthe system relies upon a careful ordering ofthe property pre- andpost-handlers. Becauseofthis, it is notpossiblefor the user to createtheir ownversions of certain system properties, suchas Controlled, since the systemmust acquire locks before any other work is done and releasethem only afterall other work has completed. To allow users to writetheir own versions ofControlled, the system could allow the user to specifythe ordering ofthe preand post-handlers, thereby installing user written pre- and post-methodsas thefirstandlasthandlers tobe executed. A alternativeto this schemeisto continueto hide the actual ordering from the user, but allow the user toload 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 oftheirown, to install as theControlledhandler, the Persistenthandler,etc.5.1.1 Note on ReplicationWhen the Replicatedproperty is implemented, it willbecomenecessary to decide how Replicatedobjects shouldbe stored. ShouldPersistentorDurableReplicatedobjects be kept on the local diskofall machines where they are Replicated, or perhapsonly a subset ofthese machines? For correctness, the systemonly needs to keep one non-volatileversionofthe object, andrequiringeverynode to store the replicas wastes diskspace and adds to the system overhead. For a read-mostlydatabase system consisting ofone master anymany clones, storage is only required (and perhapsdesired) on the master node. There mayalso be situations where “diskiess Ravenstations”areused (machines whose only disk is usedfor swap space, as exist in current Unixsystems), inwhichcase it is notpossibleto do any localstorage. To providesuch an implementation,however,violates the orthogonality ofthe properties,whichrequires that each ofthe replicas behaveas ifithas all the properties of the original object(including Persistent or Durable, in whichcase theCHAPTER 5— DiscussionandFuture Work85object must be stored to local disk). Even ifthe user is allowedto select different policies for thebehavior of the Persistent or Durable properties, each replicashould use the same policy; theobjectwould notbe truly replicatedifeachreplicacoulduse differentpolicies.One option is to provide anew service, similarto Replication, whichkeeps the instancedataof a list ofobjects in synchronization with each other. As changeswere made to one object, theywould be propagated to the others. This would allow an objectto have many “replicas” each ofwhichcouldhave different properties orpolicies for their properties.5.2 Implementation of PropertySupportThe Raven runtime system is written primarily in C. This lack of reificationhas actually madeparts of the implementation somewhat difficult to accomplish: if anobject has the Recoverableproperty, the system must be able to restore the object’s capability information,which is kept inthe capability structure and not as partoftheinstance data. This complicatestherecoveryprocess,as the shadow copies used by Recoverable must be augmented witha mechanism to recompute(orsave andrestore) the capability structureentries. There is alsonotechnicalreasonwhyconcurrency control locks and shadow copies cannot be implemented usingRaven objects, except thatsuch an implementation would result in a drop in performance,as the overhead forperforming aninvocation is greaterthan thatofanormal C invocation(see[11).A possible future implementation is to movethe capability information into the instancedata. This wouldprovide several benefits:(1) The existing support for Recoverability couldbeused to provide recoverysupport when assigning objects to instance variableswhich are madepartof or inherits.(2) It would allow the useraccess tothe informationwhich is currently storedinthe capability structure, whichis currently unavailable forthe user’s inspecCHAPTER 5— DiscussionandFuture Work86tion. Raven wouldthereforebe more reflexive:the usercouldmodify thisinformation, changing the object’s behavior accordingly.Forexample, theusercould selectfromamong differentobjects to managean instance’s locking and storage, depending onthebehaviortheuserwishes the objecttohave,and set the appropriate instance variablesto referencethese objects. Propertybehaviorcouldthereforebefurther customizedon an instanceby instancebasis.User definedproperties are aparticularly valuable tool, andpresent a future direction forthedevelopment of all Raven properties: implementing allof the current system properties as userproperties. This would force reification ofthesystem properties, since they could no longer relyon C-level datastructures, although C datatypes would stillbe requiredto interface withTDBM.Sinceuserproperties are supportedthroughtheuse ofspecialpre- and post-methods, areification ofthe Raven systemproperties wouldrequirethat all propertiesbe supportedwith pre- andpost-methods. As with user properties currently, these methodswould need to be invoked in aspecial manner to ensure that they are not invoked recursively whenthe invocations on the handler methods are made.The current implementation of user properties doessuffer from a significant problem.Because the pre-methods for the user properties are executedafter the Recovery pre-handler hasexecuted, if a restore statement is executed then theinstance data used by the user propertieswill be reset to the state it was in prior to themethod invocation. However, the userpost-methodswill still be executed, and they may relyon information set by the pre-methods. The problemisfurther complicated by the mechanics ofthe restore statement: the invocation is notterminated, it instead continues on inside the method afterthe instance data has been restored. Asolution to this problem is to force the systemto return control to the caller when arestorestatement is executed. If all the Ravenproperties were implemented using Ravenobjects, thecomplete property state ofthe objectcouldthen be restored and the post-handlers would notneedCHAPTER 5— DiscussionandFuture Work87to be executed—it would be as ifthe invocationnever took place. (An exception to this schemewould be for the Controlled handlers: locks must alwaysbe acquired first, and if any wereacquired, they would need to be freed; as such, the Controlledpost-handler would still need to beexecuted.)The current implementationis alsodeficientin thatitdoes notcompletely obey the specifiedsemantics for Dependent invocations. As described in Section 3.7,when a leave statement isexecuted the system will temporarily release (suspend) any locksheld on the current object, incase theresultwillbeprovidedby athreadexecuting a methodwithinthe sameobject. Correctexecution in accordance with the semantics of Dependencyrequires that any locks remain inplaceuntil the top level invocation completes. Threepossible alternate implementationsthereforepresentthemselves:(1) The system does notrelease any locks when a leaveis executed and theobject is in aDependentchain. This would requiretheprogrammerto ensurethattheresult statementis executed froma separateobject.(2) The system refuses to assign an object to an instance variablemarkeddependent when one ofthe object’s methods containsa leave. Aruntime errorwouldinsteadbe generated.(3) The system suspends the currentlocks, but doesnotallow any invocationonthe object to fully complete until the suspendedthread is resumed. A secondthread which accessedthe objectwhile the originalthread was suspendedwould itselfbe suspendeduntil the originalthread completed the top levelinvocation ofits Dependent chain.Ifthe original threaddid not executearestorestatement, the second thread wouldbe resumed normally. Ifhoweverthe original threadexecutedarestore,the secondthread wouldneedto be aborted in some manner.The exact semantics and implementationofthis scheme wouldneed to be carefullyworked out to ensure thatorthogonality between the Recoverableand Controlledproperties was maintained.CHAPTER 5— DiscussionandFuture Work88Ofthese options,number (2) is the mostconsistentwiththe current state ofthe 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 ofthe transaction by providing areturn value for an invocation.Perhaps the mostdebatable implementationdetailis the use ofclusterlocksforPart-Ofclusters. Using cluster locks allows the runtime system to make assumptionsabout the states oftheobjects in a cluster, but impacts the user by increasing the overheadassociated with every implementation on an object in a cluster. Cluster locks are useful to enforce theconsistency ofa clusterwhen the cluster is to be migrated or stored to disk, but are not requiredfor these purposes (e.g.,keeping cached versions ofthe objects in a cluster allows consistent objectstates to be written todisk). Ifclusterlocks are to remain apartofthe implementation, future enhancementsto theruntime system should focus on improving the performance of invocationson Part-Of clusters bykeeping the amount oflocking performed to a minimum. This can beaccomplished by bypassingany local concurrency control lock for objects in a cluster, and bypassingthe local and clusterlocks when one object in the clusterinvokes a methodon anotherobjectin the cluster.5.3 ObjectStorageThe object storage systemprovides reliable storageofobjects to disk. SinceTDBMwas designedto provide efficient atomic storage, supplantingTDBM with a Raven-specific atomic storagescheme is unnecessary. There is currently no mechanismto perform garbage collection on theobject store; however the system does provide an“1s”-like function to list the GIDs and classnames ofall the objects inthe store as a potential aid to a human user in cleaningout persistentgarbage. A mechanism for collectingdistributed, persistent garbage created by Raven applications needs to be developed.CHAPTER 5— DiscussionandFuture Work89To allow all the objects in a cluster to be loadedfrom disk into memory together, thereis aclose relationship between Part-Ofclusters and theobject storage scheme. This is accomplishedby storing all the objects in the clustertogether. However,somepieces ofaPart-Ofclustermayberather large, in which case the system will performseveral large memory-to-memory copiesanddisk transfers which could be unnecessary ifthe large object wasn’t the piece which was modified. Storing the objectstogetherfacilitatesthe retrievalofthe entireclusterfromdisk, butitis notrequired. An alternate implementation is for the systemto store each ofthe objects in a Part-Ofcluster separately on disk, but load all ofthe objects whenany one object is fetched. This schemehas a further advantage in that it allows the user threadto begin execution inside the first fetchedobject, while the system fetches the remainingobjects ofthePart-Ofcluster in parallel.In the current implementation ofthe storage model, an object’s StorageManager is responsible for creating the full encoding ofthe object (addingthe object’s capability information to theswizzledinstancedata) during object storage, while the GlDmanagerextracts thecapability informationwhen the objectis loaded in fromdisk. This requiresthatthe GlDmanager and the StorageManagers agreeon the general formatofthe encodeddata, so thattheGlDmanagercan extracttheinformation encoded by a Storage Manager.This is a potential liability, since any change intheencoding format must be reflectedin two class implementations. An alternate implementationisfor the Storage Managers topass the swizzled data to the GlDmanager for encodinginstead ofperforming the encoding themselves. Thisproblem is also addressed ifthe system is modifiedsothat the capability information is movedinto the instance data, as the process ofswizzling willproduce the full objectencoding forextractionby the unswizzle routines.The implementation ofPersistent propertyimprovesperformanceby performingthe storagein parallel with the execution ofthe userthread. Performance could be improvedsignificantly ifthe system could delay theparallel writes, allowing the object stateto be updated many times inmemory before actually performing thestorage. This could be accomplishedby having an activeCHAPTER 5— DiscussionandFuture Work90thread inside of every Storage Manager. When an invocation on astorable object finished, thecached version ofthe object would be updated in the Storage Managerand a boolean flag wouldbe set. The active thread would sleep aspecifiedperiodoftime, thenawaken andcheckthe flag tosee if the caches were modified, and write them to disk if they were. It would thengo back tosleep forits time-outperiod.In the current implementation, the system makes a distinction between the case whena single object is stored or acluster ofobjects are stored together: in the firstcase, the encodeddata ispassed around in a single TDBMDatum object; in the latter, an array ofTDBMDatumobjects isused. The implementation could be simplified ifthe system were changed to alwaysuse an arrayofTDBMDatumobjects whenpassing the encodedobjectdatato andfromthe TDBMmanager. Ifonly one object is to be stored, the array would simply contain one TDBMDatumobject. Theformat ofobject storage on disk could also be simplified by eliminating the format used by the special case ofonly a single objectbeing stored to disk (seeFigure 16).5.4 The Raven Collection ClassesProblems with the storage ofCollectionclass objects were discussed in Section 4.5.Once amechanism for storing all the Collection classes is standardized (suchas providing specializedswizzle and unswizzle methods for each class) oneother issue becomes apparent: the Collec—tionclasses are not designed to allow theitems actually in the collection to be considered Part-OftheCollectionclass object. Whenitemsare placedin a Setobject, forexample, there is nomechanism by which they can be described as being Part-OftheSet. This means that ifthe Setitselfis Part-Ofsomeother object, the itemsin the Setwill notbe partofthe Part-Ofcluster. Similarly, there is no mechanism to specify thatthe items in a collection should inherit propertiesorbe in a Dependent relationship. Property inheritance,Dependency, and Part-Ofclusteringstop atthe Collection class objects. One obvious exampleof where it would be useful to allowCHAPTER 5— DiscussionandFuture Work91objects inside acollection to inheritpropertiesis theimplementation ofaName Server. TheNameServercanbe implementedusing a PersistentSet. Ifthe items in the Setcouldbe Part-Ofthe Set,string names can be placed in the Set andbecome Persistentfor the duration ofthe time theyareentries in the Name Server.This issue can be addressed in one of several ways. Thesystem 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 wouldbe treated. A second solution is to provide an extra parameter to the constructor methods ofthe Collection classes. Thisparameter would mirror the compilerkeywords used to specify Part-Of,Inherits, and Dependent,and would indicate how the items in the collection shouldbe viewed:• partof: The items in the collection shouldbe Part-Ofthe collection.• inherits: The items in the collection should inheritthe properties of theCollectionclass object.• dependent: Theitems in the collection shouldbeDependentupon theCollectionclass object.A third solutionis forthe systemto treattheobjects inside acollection in the same way theCal—1ection class instance is used. Ifthe collection object is Part-Ofanother object, the objectsinthe collection will be Part-Ofthe collection.Ifthe collection object is invoked upon aspart of aDependentchain, the objects inthe collection willbecomepartofthe samechain. Ifthe collectionobject inherits properties, then the objectsin the collection will inheritpropertiesas well.CHAPTER6 RelatedWork6.1 Object-oriented SystemsThe problem ofproviding system services in object-oriented systemsis not new, and manysolutions have been implemented. One scheme is to map traditional servicesinto objectrepresentations. These system objects are crafted to integrate intothe object model provided by theirruntime systems. Another scheme is to provide direct runtime supportfor various services toobjects in the system. There are many object-oriented languageswhich simply give the userobjects, without any real runtime system support. In such systems theuser relies on the underlying system (Unix, etc.) for services as they would ina non-object-oriented language. Sometimesobjects can be exploited to make access to someservices, such as persistence, more automatic.6.1.1 C++Several differentapproaches havebeenproposedfor adding persistenceto C++objects [12],including some which even allow theincrementalloading ofobject data [22]. This hasthe benefit92CHAPTER 6— Related Work93ofallowing C++ objects existing in any operatingsystem to be persistent, but the consequence isthat no general operating system support can be assumed. These approachesrely on overloadingthe “>>“ and “<<“ operators to write the object data into streamsto which files have beenattached. The basic mechanismis forapersistentclass to write out atyped streamwhich includesaclass identifierfollowedby the instance data. These schemes do notprovide general persistencefor all objects, but provide mechanisms whichprogrammerscan use to make specific classes persistent. Since C++ classes aren’t real objects, there is no mechanismby which the system canautomatically traverse the instance data. Instead, the programmer is responsible for writingtheload and store functions for each class by hand (although tools forgenerating these functionsautomatically could potentially be developed at an unknown cost). Theseschemes further requirethe user to manage aunique identifier (either a class name or numericalid) foreachclass which isto be persistent, and to develop a mechanism (such as a simple switch orjump table) to allow thecreation ofnew classes given the name oridentity.6.1.2 ArjunaThe Arjuna system ([18], [23]) was designed to provide a C++ classlibrary and system tosupport the building ofrobust distributed systems through theuse ofatomic transactions andpersistentobjects. Arjunasuppliesthe systemsupportforatomic transactions (serializedconcurrencycontrol and recoverability) and persistent objects throughspecific C++ classes organized into aclass ortype hierarchy. Arjunais currentlydesignedtorun on top ofUnix. Unlike Raven, multipleversions of what are essentially the same class are requiredif one version is to make use ofthesystem services for atomic transactions and persistence.Additionally the support for these services is not transparent to the programmerlike it is in Raven. The use oftransactions, forexample, requires the programmer to explicitlyinstantiate an atomic transaction object and then usemethods ofthe atomic transactionobjectto start, end or abortthe transaction within the objectthetransaction is to affect. Becauseservices are provided through methods inherited fromsystemCHAPTER 6— Related Work94classes, the programmer does have the opportunityto subclass these system supplied classes inorderto customizethe way they systemhandles persistence,recoverability, and concurrencycontrol.6.1.3 NEXTSTEPPerhaps the most widely used object-oriented system is NEXTSTEP[17], which runs onhardwaredeveloped by NeXT Inc. as well as Intel 486 andPentiumplatforms.NEXTSTEPis nota true object-oriented operating system, but provides a runtime systemfor Objective-C objectswhich sits on top ofMach and Unix. Programmers are required to managethe use ofsystemservices themselves. The programmercan make use ofthe traditional Unixsystemcalls, but therecommended method for managing object archiving is through theuse of special C functionsprovided in NEXTSTEP. These functions support the archiving and retrievalof objects to specially typed streams by writing to the stream the object class and it’s instancedata. These functions can ensure that objects are only encoded once insideof each stream. By using thesefunctions, the programmer can read and write objects andobject references without having towrite special functions for each class. Concurrentprogramming is possiblein NEXTSTEP usingMach threads or the cthreads package. No system supportfor concurrency control is provided,however. It is the programmers responsibility to createmutex locks and manage their use amongany cooperatingthreads.6.1.4ArgusThe Argus system [13] was designed specifically foruse for developing applications thatrequire stable data storage in a distributedenvironment (such as banking systems). Argusprovides special objects called guardianswhich effectively encapsulate data with a well definedinterface, andcanalsoshieldthe datafromthe effects ofnetworkandhostfailures. Special atomicobjects, which contain locks to control against concurrentaccesses, are used to synchronizeCHAPTER 6— Related Work95accesses to guardians. Persistence is achievedby explicitly declaringpart (or all) ofthe datakeptby a guardian to be stable when the guardian is designed.Once the programmer has specifiedatomic and stable objects, the Argus systemitselfprovidesserializability and persistence withouttheprogrammerhaving to explicitlymakecallsto acquirelocks orwrite the datato storage. Othertypes ofsystem services are not available, as the designersofArgus focusedprimarily on providing persistent, distributed atomic transactions, and developedspecial language and runtime systemfeatures to support such transactions.6.1.5 CronusCronus [5] is an object-oriented distributed computing environment developedby BBNLaboratories Inc., that is a capable ofconnecting groupsofheterogenous computers. Among itsgoals are providing typical operating system services to a distributed environment,simplifyingthe taskofwriting distributedprograms, building highly availablesystems, building scalable systems and integrating local and remote resources. To accomplishthese goals Cronus employs theactive object model with access to objects managed byan object manager. Each machine has oneobjectmanagerperobjecttype and the objectperforms pre and postmethodprocessing anddetermines the method to execute. Although thereare some routines that can be used to control theexecution ofan object manager, these techniques applyto the whole collection ofobjects and notto individual objects. Raven provides a similar typeof system control only it is on a perobjectbasis. Cronus does provide a mechanismto allow individual objects to be customized.Eachobject has methods to allow user specific datato be attached to an object. The interpretation anduse ofthis data, however, is the responsibilityofthe application using the object. It isessentiallyadvisory information attached to theobject that only has a meaning if theuser of the objectchooses to examine the dataand followany usage guidelines associated withthedata.CHAPTER 6— Related Work966.1.6 GuideLike Raven, Guide [4] consists of both aprogramming language and a runtimesystem.Guide is designed for a multi-threadedenvironment with persistent synchronizedobjects whichsupport atomic transactions in a distributed environment.In contrast with Raven, all objects inGuide are persistent. Guide also has supportfor an atomicproperty forobjects,but Guiderequiresall updates to atomic objects to be withinthe confines of a transaction. Furthermore,atomicitymustbe specified atobjectcreation time, andcannotbe changed afterwards. Invocations in Guideare accomplished by using the ObjectCallsystem primitive. This does allow the systemto catchinvocations on objects, and potentially insertadditional code before and after the methodexecution to provide services in amannersimilarto Raven.6.1.7 SpringSpring [15] is a new object-oriented distributed operatingsystem developed by Sun Microsystems, Inc. Ituses objects to provide strong interfacesto data and services. Althoughone oftheprimary motivations for Spring objects is thetransparencytheyprovideduringdistributedcomputations, Spring objects can also be used withina local address space. One ofthe key componentsofaSpring objectis its subcontract[9], which defines the communications mechanismsthe objectshould use at runtime. Different subcontractscan be created to provide different services. Forexample, the architects ofSpringhavedeveloped subcontracts to provide objectreplication, caching, and crashrecovery, among others.Subcontractsprovide apowerful mechanismforcustomizingthe wayinvocations aremadeon objects. However, they have somelimitationsas thebasisfora general service providing schemelike Raven properties. First, subcontractsare not generallyused for local (same address space)invocations, as Spring’s Interface DefinitionLanguage (IDL)compiler will transform method invocationsinto calls on the object’s regular methodtable,bypassing the subcontract, when itcan access the object directly. Second,subcontracts cannot beassigned to an object dynamically,to allow the object to change theservices it receives; aparticuCHAPTER 6— Related Work97lar subcontract is used when the object is created andis thereafter used by the object. Thisalsocan lead to a “subcontract explosion” similar to theclass explosion problem, as an object couldnot have both the replicated and crash recoverablesubcontracts, for example, but would needsome subcontractthatcombinedbothservices ifbothweredesired. An intriguingnotion wouldbeto devise some mechanismto expand the abilities of subcontractsso thatthey couldbe composedtogether and dynamically changed at runtime alaRaven properties.6.1.8 COOLCOOL [8] is a distributed object-oriented layer developed for theChorus system [21].Object descriptors in COOL include an attributes field, which is similarto the properties field ofthe Raven capability structure. COOL attributes can specify variousproperties ofthe object, suchas whether the object is persistent orhas an active thread. Ifan object ispersistent, 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 checkpointthem during execution) forautomatic restart when the system reboots. COOL objects must have a specialattribute to be globally known, otherwise they are accessible only from within their context.One main differencebetween COOL attributes and Raven properties isthat attributes are assigned only at objectcreationtime.6.2 SummaryRavendiffers significantly frommanyofthe languages and systems discussed in this sectionin that it avoids a class explosion whenclasses differ only in the underlying system supportthatthey require. For example, an object ofan existing class can be made persistent, recoverableandcontrolled simply by instantiatinga new instance ofthat class with thedesired properties insteadofprogramming a new class.CHAPTER 6— Related Work98Unlike several ofthe systems described in this section, Raven’s supportfor system servicesis largely transparent to the programmer and requires littleeffort on the programmer’s part to utilize. Because services are provided automaticallyby the system, the programmerdoes nothave tomanage their use. Raven avoids some of the performance problemsinherent in other systemswhichprovide services transparently, becauseRaven allows objectstobe assignedproperties on aper-instancebasis. Objects only incurperformance overhead for servicesthey actually use.CHAPTER7ConclusionThis thesis has presented a new techniquefor providing system servicesto objects in an object-oriented system. This techniqueassociates each systemservice with a property, whichwhenassigned to an objectwill allowthe object to receive theassociated service. It alsoallows theprogrammer to describeinter-object relationships,to provide object clustering andserialize invocations on objects.The design and implementationofthe property scheme forRavenhas shownthatit is possible foran object-orientedsystemto provide servicesto objects:• transparently, withoutthe need for the programmerto manage the use oftheservices, and• on a per-instancebasis, so invocationperformance is directlyrelated to thenumberofservicesthe objectreceives.99CHAPTER 7— Conclusion100The property scheme also providesatomicity ofmethodinvocationsthroughthe use ofDependentrelationships.Three aspects ofthe propertyscheme stand out abovetheothers: Inherits references,Dependent references, and user properties.These features not only contributeto the uniqueness of theRaven property scheme, theyare enabling features whichvastly extendthe flexibilityand usability ofthe system, providingbasic capabilitieswhich can bebuiltuponto achieve desired results.Bibliography[1] DonaldActon. Unified Language and Operating SystemsSupportforParallel Processing. Ph.D. Thesis PHDO94-ACTO, Department ofComputer Science, UniversityofBritishColumbia, Vancouver,BritishColumbia, 1994.[2] Donald Acton, Terry Coatta, and GeraldNeufeld. TheRaven System. TechnicalReportTR92-15,DepartmentofComputerScience, University ofBritishColumbia,Vancouver, BritishColumbia,1992.[3] DonaldActon andGeraldNeufeld. Controlling ConcurrentAccesstoObjects in theRavenSystem. In1992 International Workshop on Object-Orientation in OperatingSystems, IW000S ‘92. IEEEComputer Society Technical Committee on Operating Systems,September24-25 1992.[4] R. Balteret al.ArchitectureandImplementationofGuide,an Object-OrientedDistributedSystem. InComputing Systems, 4, 1991.[5] James C. Berets, NatashaCherniak, andRichardM. Sands.Introduction to Cronus. TechnicalReport6986, BBN Systems and Technologies, Cambridge, MA, January 1993.[6] Barry Brachman andGeraldNeufeld. TDBM: A DBMLibrarywithAtomicTransactions. Proceedings ofthe USENIX SummerTechnical Conference, June, 1992,pp.63-80.[7] Terry Coatta. ConfigurationManagement Using Objects and Constraints.PhD Thesis PHDO94-COAT, DepartmentofComputer Science, University ofBritishColumbia, Vancouver, BritishColumbia, 1994.[8] SabineHabert and Laurence Mosseri. COOL: Kernel Supportfor Object-Oriented Environments.Proceedings ofECOOP/OOPSLA 1990, October21-25 1990,pp.269-277.[9] GrahamHamilton, Michael L. Powell, and JamesG. Mitchell. Subcontract: A FlexibleBase forDistributed Programming. Proceedings ofthe 14th Symposiumon Operating Systems Principles,Asheville, NC, December 1993.[10] Norm Hutchinson. GeneralizedTable Routines(unpublished).[11] The Institute ofElectrical and ElectronicEngineers. Information Technology—PortableOperatingSystem Interface (POSIX) Part 1: SystemApplication ProgramInterface. IEEE Standard 1003.1-1990 (also available as International StandardISO/IEC 9945-1, 1990).[12] Philippe Laurent andNino Silverio. Persistencein C++. Journal ofObject-OrientedProgramming,Vol. 6, No. 6, October 1993,pp.41-46.[13] BarbaraLiskov. Distributed ProgrammingInArgus. Communications ofthe ACM, Vol. 32,No. 3,March 1988,pp.300-312.101102[14] Mary E.S. Loomis. The ODMG ObjectModel. JournalofObject-OrientedProgramming, Vol.6, No.3, June 1993,pp.64-69.[15] James G. Mitchell et al. An Overview ofthe SpringSystem. Proceedings ofCompcon Spring 1994,February 1994.[161 Gerald W. Neufeld, Murry W. Goldberg, andBarry J. Brachman. The UBCOS!DistributedApplication Programming Environment. TechnicalReport90-37, Department ofComputerScience, University ofBritishColumbia, Vancouver, British Columbia,January 1991.[17] NeXT, Inc. NeXTStep Reference. Addison-WesleyPublishing Company,1991.[18] Graham D. Parrington. ReliableDistributedProgrammingin C++: TheArjunaApproach. Technicalreport, COmputing Laboratory, University ofNewcastle uponTyne, UK.[19] StuartRitchie. TheRavenKernel: a MicrokemelforSharedMemory Multiprocessors.Masters’ Thesis, DepartmentofComputer Science, University ofBritishColumbia, Vancouver,BritishColumbia,April 1993.[20] Mendel Rosenblum andJohn Ousterhout. TheDesignandImplementation ofaLog-StructuredFileSystem. In Proc. ACM Symposiumon Operating Systems Principles,pages 1-15, October 1991.121] M. Rozier et al. ChorusDistributed Operating Systems. Computing Systems, l(4):305-367, 1988.[22] John J. Shilling. How to Roll Your Own PersistentObjectsin C++. Journal ofObject-OrientedProgramming, Vol. 7, No. 4, July-August 1994,pp.25-32.[23] Santosh K. Shrivastava, GraemeN. Dixon, and Graham D. Parrington.AnOverviewoftheArjunaDistributedProgramming System. Technicalreport, ComputingLaboratory,University ofNewcastleupon Tyne, UK.[24] Soley, R.M., Ed. ObjectManagementArchitecture Guide,Rev. 2.0, 2ndEd. 0MG TC Document92.11.1, ObjectManagement Group, 1992.[25] Sun Microsystems Inc.. XDR: ExternalDataRepresentationStandard(RFC 1014). NetworkInformationCenter, SRI International, June 1987.103Appendix: TableofContentsAppendix A. Data ‘I’ypes............................................................................... 105A.1 Capability Structure 105A.2 Property Values 107A.2.1 Property Masks 107A.2.2 SystemSupportedProperties 108A.3 Structures forSupporting the Recoverable Property 108A.3.1 Shadow Structure 108A.4 Structures forSupporting the ControlledProperty 109A.4.1 Lock Status Values 109A.4.2 LockTypes 110A.4.3 Lock Structure 110A.4.4 LockInformation Structure 111A.5 Structures for Supporting ObjectStorage 112A.5.1 Storage Information Structure 112A.5.2 ObjectListEntry Structure 113A.6 Unique Identification Structures 113A.6.1 GID Structure 114A.6.2 Location Information GID Structure 114A.6.3 Unique IdentifierStructure 115A.7 Compiler Types 115A.7.1 Property Set 115A.7.2 Variable Attributes 116A.8 Other DataTypes 116A.8.1 Instance Variable ModifierBits 116A.8.2 DefinedValues forObject Storage 117A.8.3 EnvironmentVariables 117AppendixB Class Definitions•..........................................fl.. ...........fl.....fl. 118B.1 ThreadClass 118B.1.1 Public Interface 118B.1.2 Private Interface 120B.2 StorageManagerClass 120B.2.1 Public Interface 120B.2.2 Private Interface 120B.3 SMEntryClass 121B.4 GlDManagerClass121B.4.1 Public Interface 121B.4.2 Private Interface122B.5 TDBMManager Class 122B.5.1 Public Interface 122B.5.2 Private Interface123104B.6 TDBMDatum Class.123B.6.1 Public Interface123B.6.2 Private Interface124B.7 New Basic Methods124Appendix A DataTypesThe implementations ofthe property scheme and ofobject storage required modifications toexisting data types used by the Raven runtime as wellas the development ofnew data structures. What follows is an exhaustive list of all modified and new datastructures used by theruntime, including those already presentedin the thesis.Many of these data types and structures rely upon definitionsof other data types andstructures. This additional definitions are generally notprovided here.Al Capability StructureThis structure is also described in Figure 6.struct capability{Euncptr invoke;invokeis apointer to the currentinvocationfunction to use.105Appendix A: DataTypes106cap id;idpoints to the currentcapability structure.It is useful when debugging asa sanity checkfor acapability pointer.cap is_a;is_apoints to the Class objectwhichthisobject is an instance of.cap parent;parentpoints totheobjectfromwhichthisobjectinheritsproperties.parent points to thenilobjectifwe do notinheritproperties.cap inh_root;inh_root points to the objectwhich lies at the top ofour current inheritence chain. This pointer points to ourselfifwedo not inherit properties.This allows us to detect inheritance cycles,such as attempting to inheritproperties fromourself.cap storage_manager;storage_manager points to our currentStorage Manager object, or tonil ifwe do not have the Persistent or Durableproperties.method_type method_type_to_use;method_type_to_use is used by the runtimesystem to determine if alocal version of a method exists.Some invocations on remote objects can(and should) be handled locally.struct gid*gid;gidpoints to a global identificationstructure (see SectionA.6). In generalthis will point to NULL unless the objectrequires such a structure.voidp rw_lock;rw_lockis apointerto the object’sconcurrency control lock, orto NULLif the object is not Controlled. The structureof this lock is shown inSection A.4.voidp cluster_lock;cluster_lockis apointerto theobject’s cluster lock, or to NULL iftheobject is notpartof aPart-Ofcluster.propertiesobject_properties;object_propertiescontains thecurrentproperty set ofthe object.u_char *data;Appendix A: Data Types107datais apointerto the instance data for the object.}A.2 ProperLyValuestypedef 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_controlledOxfff7ffff#define immutableOxffffffef#define inherited_immutableOxffefffff#define immobileOxffffffdf#define inherited_immobileOxffdfffff#define replicatedOxffffffbf#define inherited_replicatedOxffbfffff#define test_propOxffffff7f#define inherited_test_propOxff7fffff#define u_prop_iOxfffffeff#define inherited_u_prop_iOxfeffffffAppendix A: Data Types108#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 StructuresforSupportingthe RecoverablePropertyRecoverability is accomplishedby creating shadowcopies ofthe object instance dataprior toexecuting the method code. The format oftheshadow structure has been modified to supportDependency.A.3.1 ShadowStructuretypedef struct ShadowStruct{structShadowStruct*next;next points to the next Shadow structurein the chainedlistofshadows.Appendix A: Data Types109struct ShadowStruct*prevjous;previous points to the previous Shadow structurein the chained list ofshadows.struct capability*object;objectis a pointerto the object for which this is a Shadow structure.u_long methodHash;methodHash is used for debugging purposes whendumping out theshadow list.mt depth;depthis the current call depth in the shadow chain.char*image;image is apointerto the copy ofthe instance dataofthe object.mt invokeDepth;invokeDepthis incrementedonceforeachinvocationmadeon aRecoverable object in the currentDependentcalling chain.mt dependentlD;dependentID is the ID ofthe currentDependentcalling chain.}Shadow;A.4 StructuresforSupporting the Controlled PropertyEachcontrolledobjecthas an associatedconcurrencycontrollock. Objects whicharein aPart-Ofcluster have a seperate cluster lock. Each threadmaintains a list ofthe locks which it hasaquired.A.4.1 LockStatusValuesEach lockwhich a threadholds (or is attemptingto aquire) has an associated status.typedef enum{GRANTED = 1,Appendix A: Data Types110Indicates the lockhas been granted to the thread.WAITING,Indicates the thread is waiting to aquire the lock.SUSPENDED,Indicates the thread has been suspended and the locktemporarily relinquishedby thethread due to a delayed result.WAITING_REACQUIRE,Indicates the thread is waiting to reaquire a lockthathadbeen suspended.RETRY,Indicates that the thread should attempt to aquire the lockagain. This willgenerallyinvolvethethreadreexecutingthelockingportionsofthepropertypre-handlers.DELETED,Indicates that the specified lock was deleted, either becuase the objectnolonger is Controlled or is no longer in a Part-Ofcluster.LOCKING_ERROR,Notcurrently used in the implementation.LOCK_TIMED_OUTIndicates the lockcouldnot be grantedbeforethe timeouttimerexpired. Apossible indicationofdeadlock.}LOCK_STATUS;A.4.2 LockTypestypedef enuin{CLUSTER_LOCK = 1,INSTANCE_LOCK}LOCK_FAMILIES;A.4.3 LockStructureThe concurrency control and clusterlocks have the following structure.Appendix A: Data Types111typedef struct LOCK{LIST granted;The listofthreads whichhave been granted thelock.LIST waiting;The list ofthreads which are waiting forthe lock.LIST suspended;The list of threads which have temporarily released this lockdue to adelayedresult.LIST reacquire_list;The listofthreads whichhadtemporarilyreleasedthe lockandnow wishtoaquire it again. They are given preferrentialaccess to the lockover threadswhich are simply on thewaitinglist.OSSemaphore semaphore;The semaphore whichensures thatonly one thread is manipulatingthe lockdata structures at atime.}LOCK;A.4.4 Lock Information StructureEach entry on any of the lock lists is aLOCK_INFO structure. Threads maintain a chain ofthesestructures,onestructureforeachlocktheyhaveaquired, arewaitingfor,orare suspendedin.typedef struct LOCK_INFO{struct LOCK_INFO*next;Used to point to the next structurein 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 Types112ThenextstructureinthechainofLOCK_INFOstructuresheldbythethread.struct LOCK*lock_ptr;A pointer to the lock.void*waitingthread;Ifthe thread is currently suspended, it’s position is recordedhere.behaviorLockType lock_type;The type oflock(read, write) we are holding/wishto hold.mt lock_holder;The P1D ofthe process.cap objectlD;The object which was was invoked upon.mt session_id;The identifierofthe current session (unique foreach thread).mt lock_depth;The currentdepth in the locking chain.LOCK_STATUS lock_status;The status ofourattempt to aquire alockwillbe placed here.mt dependentlD;The id ofthe currentdependentchain.}LOCK_INFO;A.5 StructuresforSupportingObjectStorageEachthread maintains alist ofStorageManagers forthe objects that have beeninvoked uponin aDependent calling chain. Theentries ofthis list are oftype structSTORAGE_INFO.A.5.1 Storage Information Structuretypedef struct STORAGE_INFO{Appendix A: Data Types113struct STORAGE_INFO*next;The nextentry on the listofStorage Managers.struct STORAGE_INFO*prevjous;The previous entry on the listofStorage Managers.mt dependentlD;The identifier ofthe currentDependentcalling 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 entryis oftype STOREL1ST_ENTRY, which is shown below.}STORAGE_INFO;A.5.2 Object List Entry Structuretypedef struct STORELIST_ENTRYstruct STORELIST_ENTRY*next;The nextentry in this list.struct STORELIST_ENTRY *prevjous;The previous entry in this list.cap object;The object, managedby the Storage Manager, which was invokedupon.}STORELIST_ENTRY;A..6 Unique IdentificationStructuresAn object’s unique identifier is storedin three levels. This is partly ahistorical artifact,due tothoughts abouthow Raven would handlegids. Raven’sinitial use ofthe term“gid” is somewhat of a misnomer, since it was simplyused to describe object location information(which,Appendix A: Data Types114prior to object storage, was sufficient to uniquely identifyan object). The capability structureofan objectcontains apointerto astruct gid.A.6.1 OlD Structurestruct gid(struct u_gid u_gid;The structure which actually contains the location informationand uniqueidentification information.mt gid_len;Unused. Originally designedto holdthe lengthofthe encodedgid.char*encoded_gid;Unused. Originally designed to hold a pointer to an encoded versionofthegid.A.6.2 Location Information OlD Structurestruct u_gidu_long hid;ThePaddress ofthe host on whichthis objectcurrentlyresides.u_long lid;The port numberofthe RavenWorldon which the objectcurrently resides.struct unique_id uid;The unique identifier ofthe object.d_cap capability;Apointerto the capability forthe object,i.e., the object’s location in memory on the Raven World specifiedby thehidandlidfields.char*classnameThe class name which this object isan instance of.Appendix A: DataTypes115A.6.3 Unique IdentifierStructurestruct unique_id{u_long creator;The IP address ofthe machine on which the object was created.u_long world;The portnumbertowhichtheRavenWorldonwhichtheobjectwascreatedwas bound.u_long generation;AcounterwhichisincrementedonceforeachincarnationofaRavenWorld.u_long name;A counterwhich is incrementedonce foreachgidwhich is assignedby anincarnation ofa RavenWorld.A7 Compiler TypesA.7.1 PropertySettypedef enum{persistent = 0,durable,recoverable,controlled,immutable,immobile,replicated,test_prop,u_prop_i,Appendix A: Data Types116u_prop_2,u_prop_3,u_prop_4,phaseout,lastProperty}Properties;Thephaseoutproperty is used to warn the user that he has selecteda property whichis no longer supported by the system.A.7.2 Variable Attributestypedef enum{stat=O,meta,copy,partof,inherits,dependent,indirect,public,lastVarAttribute}VariableAttributes;A8 Other Data TypesA.8.1 Instance Variable Modifier Bits#define PT_DEPENDENT 0x8#define PT_INHERITS OxlOAppendix A: Data Types117#define PT_INDIRECT 0x20#define PARTOF_MASK_VAL 0x40#define PT_PARTOF (PT_DEPENDENTIPT_INHERITSIPARTOF_MASK_VAL)A.8.2 Defined Valuesfor Object Storage#define GENERATIONSTRING “.sysGENERATION”#define GENERATIONSTRINGLEN 15#define DBMPATH “/raven/export r/gener±c/storage”A.8.3 Environment VariablesRVSTORAGEPATH Directory into whichTDBMwill store objectsRAVENWORLD Portnumberto bind to when starting RavenAppendixB Class DefinitionsMany new classes were created during the implementation of the object property scheme.Additionally, many existing classes weremodified to support the newproperty scheme.Theseclasses are presented here.Some ofthe interfaces listedhere as private interfaces are private simply in that they arenot to be known by the general programmer. They are not necessarily private in that theyarefunctions which are only used fromwithin an instance ofthat class. Many “private”behaviorsareinvokedby theruntime system, orfromotherobjects whichareusedtoprovide supportforproperties.B.1 ThreadClassB.1.1 Public Interfaceclass Thread uncontrolled{118Appendix B: Class Definitions119pid, 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 traceDumpOnFill0;behav traceDumpOnExit0;behav traceDurnp0;}Appendix B: Class Definitions120B.1.2 Private Interfaceclass Thread{behavior rernoteDependentWorker(handler: mt1resumeStatus :Int);behavior remoteRestoreO;behavior remoteRestoreFunctions0;}B.2 storageManagerClassB.2.1 Public Interfaceclass StorageManager controlled{$objects : F±xedArray[cap];$size : Int;$entries : Int;constructor();behav updateCacheOfObject(obj : cap, doWrite:mt1now : Int) writelock;behav manageObject(obj cap);behav uninanageObject(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 Definitions121behav privateWrite(id :Int) private;behav getCap(uidPtr : Int) :cap private;behav privateDelete(entry SMEntry)private;behav setUpEntry(obj : cap, entrycap) private;behav entriesHaveSameValue(el: cap, e2 : cap) : mt private;}B.3 SMEntryClassThis class isusedonly internallybythe StorageManger.Its interface is notvisibleto 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 Definitions122constructor();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 TDB1anagerClassB.5.1 Public Interfaceclass TDBMItanager controlled{dbm : Int;namedbm : Int;recovery : Int;constructor;behav shutdown;behav getGeneration(): mt writelock;Appendix B: Class Definitions123behav getTID() : mt readlock;behav preComrnit(id :Int) writelock;behav commit(id : Int) writelock;behav store(datum cap) writelock;behav storeForTransaction(id : mt1datum : 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 TDBMDatuinClassB.6.1 Public Interfaceclass TDBMlDatuin{keydptr : Int;keydsize : Int;valuedptr : Int;valuedsize : Int;behav setKey(dptr : mt1 dsize: Int);Appendix B: Class Definitions124behav 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 whatis specified in the publicinterface.B.7 New Basic MethodsThe Objectclass was extended to include several new methods todo the following:• Assign the object a GID.• Swizzle and unswizzle the instance data.• Provide supportforthe user definedproperties.These methods were added to the list ofbasic methods supportedby the Object class. Assuch, they do not appear in the interface definition ofObject.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 Definitions125behavior postUser3 (dependentlnvoke : mt1 isDependentRoot: Int,hasProp : Int);behavior preUser4(dependentlnvoke : Int);behavior postUser4(dependentlnvoke : mt1 isDependentRoot: mt1hasProp : Int);


Citation Scheme:


Usage Statistics

Country Views Downloads
United States 12 20
France 8 0
Japan 7 0
China 5 1
Russia 1 0
India 1 0
City Views Downloads
Unknown 10 4
Ashburn 7 0
Tokyo 7 0
Beijing 4 1
Sunnyvale 1 0
University Park 1 0
Shenzhen 1 0
Redmond 1 0
West Hartford 1 0
Redwood City 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items