Inter-OfficeMemorandumToCedarInterestDateOctober28,1982FromPaulRovnerLocationPaloAltoSubjectTheCedarRuntimeSystemOrganizationPARC/CSLXEROXFiledon:[Indigo]Documentation>SafeStorage.tiogaFornoviceusageoftheCedarsystemitisnotnecessarytoreadthismemoorusethefeaturesdescribedinit.INTRODUCTIONThismemoisintendedtobeusedasreferencematerialbyCedarimplementorsandadvancedusers.ItdocumentstheruntimesupportforCedarlanguagefeaturesthatdealwithstoragemanagement,universalreferences(REFANY)andATOMs.UsefulinformationforCedarWizardsappearsbelowinthisfont.TheinterfacesdescribedhereinareallexportedbyRT.bcd,whichisincludedinCedarCore.bcd,whichisincludedintheCedarbootfile.Thisdocumenthasthefollowingsections:1.StorageManagement1.1TheSafeStorageInterface1.1.1Bases1.1.2ZONEs1.1.3ControllingtheCollector1.1.4ERRORs1.2TheUnsafeStorageInterface2.UniversalReferencesandRuntimeTypes:TheRTTypesBasicInterface2.1Types2.2Typeattachments2.3Finalizationofcollectibleobjects2.4ERRORs3.ATOMs:TheAtomsPrivateInterface4.ConfigurationParameters1.StorageManagementTheCedarruntimesystemprovidessupportbothforautomaticstoragemanagementandforexplicitstoragemanagementintheMesa6.0style.TheprogrammerindicateswhichofthesehewantswhenheusestheNEWexpressionby(perhapsimplicitly)specifyingastoragezonefromwhichtogetnewstoragespaceforaCedardatavalue.ThemaximumallowedstoragespaceforaCedardatavalueis64Kwords.TheCedarstoragemanagementfacilityisbuiltontopofthePilotSpacemachinery.Normally,aclientofCedarwillnotexplicitlyusePilotSpacesfordatastorage.1p a  q _brn_bq#_br+_b03:q \rn\q#\r+\.q ZHrnZHF^!q+ZH r3oZHs{Rr HL.t Fo1 j%&(A*1,36A9=G?,ADX DZMr A o?@;!$&,138 @Czo=s:$/)i+06;m>jADo;  $?(,E.qo9d "[&d)*-ro6/ AS"$&,6.3N7D8>&? o50}="%o2k#o0 x.eu.e.e r.ex.e,+)T w'x%u%% r %!F%o$C/ 6 &+/u.$C/$C r8$C9R$Cx"x = x2 I "xou r#$vo!  :/ oc &-+U.17zrBtD!GoLv85r!"(*04 6 =:w>_>CrF(Foz%kW"$&*/-1w1/23:J?%CGgoi6ro CW #'),G.H02n4w8 8 r; =( C o 5Y*K %2'*/j14v)TVm$InCedar,therearetwotypesofstoragezone:ZONEsandUNCOUNTEDZONEs.ThecharacteristicthatdistinguishesZONEsfromUNCOUNTEDZONEsisthedeallocationmethod:storagefromaZONEisdeallocatedautomatically;storagefromanUNCOUNTEDZONEisdeallocatedexplicitlybytheclientprogramviatheFREEstatement.IfauserdoesnotspecifyastoragezoneparametertoNEW,storagewillbeallocatedfromadistinguished,predefined(collectible)ZONE,calledSystemZone(morebelow).Itisoftenconvenientandnaturaltousedifferentstoragezonesorstoragemanagementstrategiesfordifferentpurposes.TheSafeStorageandUnsafeStorageinterfacesprovidefacilitiesforcreatingdistinctzonesandforchoosingamongseveralalternatestoragemanagementstrategies.EachzonecreatedbyeitherSafeStorage.NewZoneorUnsafeStorage.NewUZonegetsitsstorageinunitsofstoragequantafromasingleBase.Azone'sBaseisspecifiedasaparameterwhenthezoneiscreated(seethedescriptionsofNewZoneandNewUZone,below).ABaserepresentsacontiguousregionofvirtualmemory.Basesareusedtodefineregionsofvirtualmemoryfromwhichzonesgettheirdataquanta.Thisisusefulbothforcircumscribingandforlimitingthestoragethatcanbeacquiredbyzones.ABasemaynotbemovedorextendedafteritiscreated.Foranapplicationthatdoesnotrequirecircumscribedregionsofvirtualaddressspace,theprogrammerneednotuseBasesexplicitly.IftheprogrammerdoesuseoneoftheproceduresthattakesaBaseparameter,hemayoptforthepre-definedRootBase,definedbelow,bydefaultingtheparameter.Astoragequantumisacontiguousblockofstoragecellsinvirtualmemory.Thequantumsizeisacompile-timeparameteroftheruntimesystem;thelocationofaquantumisdeterminedwhenthequantumisacquiredfromitsBase(atruntime).Eachzonerepresentsasetof(notnecessarilycontiguous)storagequanta.AtanygiventimeazonemayhaveasfewaszeroquantaorasmanyquantaasitsBaseowns(seethedescriptionsofExtendZoneandExtendUZone,below).Theidentificationofazone'sBaseismadewhenthezoneiscreatedanddoesnotchangethereafter.Theruntimesystemmaintainsatable,calledthequantummap,thathasaonewordentryforeachquantuminvirtualmemory.Thistableisindexedbythemostsignificantbitsofavirtualmemoryaddress.Therewillbeonenon-nullentryinthequantummapforeachquantumthathasbeenacquiredbyaZONE.EachquantummapentrycontainsenoughinformationaboutaquantumtofindtheZONEtowhichitbelongs,amongotherthings.(Notationalpoint:wewilloccasionallyusethewordobjectbelowtomeancontiguouswordsofstoragespaceforaCedardatavalue.)1.1TheSafeStorageInterfaceThisisaSAFEinterfacetothefeaturesoftheCedarstoragemanagementfacilitythatallowtheprogrammertodealwithBases,(counted)ZONEs,andthereference-countingcollector.ZONEmanagementSizeRepresentation:TYPE={quantized,prefixed};ThisisanargumentusedwhenanewzoneiscreatedbyNewZoneorNewUZonetoindicatehowsizeinformationistoberepresentedforobjectsfromthezone.Thequestforgoodperformancemotivatesachoiceofsizerepresentation:quantizedzonesaregoodiftherewillbemanyobjectsofthesamesizeandtype,orofafewdifferentsizesandtypes.Prefixedzonesaremoregeneral(e.g.forTEXTobjects),but2rob); #q%p*h.m36A Fo` + "'*D4#9 :N< D o^2| &< /837r9sCH#o]3   $*4,q.3 oZ?J %)/v1pZ2mZr4Z5Z:S=?DHeoX %  &+l/d 70;=oVo r#%8'-15_7; C oTu T!T r*pT+Tu-NT.aT r8T9 T>D+ oS  #&,16kZoI w I I r`I I ) #)'{)C-37M9<>BGoGfA $&**-42#5B6:>@U oEZ!$'Z)~/X157; >D@CGoDWUoAFb !$) 27v9[=BG/o? _M# )+z- 59;>S@B o>:y2 "$$P'*@,/T 6=BGo< Q o:w::rY:: $(*v/.2C38W>"AFo8]8 !?#%*/2b79:@BF o6$a"s%'*-o4'8  !$ + 3#7<>A|E8Heo2W" &(f*-2v4&69?<?A o0D - %`*Y-M 578=@vAEo/1J!1#(N o,R"d#'d+fw-,.,3~r5,6,9<5=i@ CGRo*|)$F'_*,11g3b59 ?BTD E4o)T "%X*.0,28d;|=@Fo'8"&@,//28= DHeo&MI "&'-H15lo#w   'a),@w/#w0~#wr3#w4#w79w=L#w=#wDGo!"r%y!oAuAA rApA1v a"$Y&,;.049 BF1 t t"?%V(,38;n=1d 1 uH$(L*0 2 rt!$(),01s6A8@>@eG# 'Y(*s,c 36 :>@n !` )r/05769C8 : 6#&(,y1+25n9;>B CEF 5 m$S)-/3f83;0=gAGv) UTVm$]theirallocatorisslower,eachobjectrequiresextrastoragecellstocarrysizeandtypeinformation,andprefixedzonesaresusceptibletofragmentationproblems.Thesizeandtypeofanobjectfromazonethathasaprefixedsizerepresentationiscarriedin2prefixwordsoftheobject.Forpurposesofallocationefficiencyandflexibilityinprefixedzones,thesizeofanobjectmaybebiggerthanisrequiredforavalueoftheobject'stype.Eachquantuminazonethathasaquantizedsizerepresentationsuppliesobjectsofonlyonesizeandtype.Thesizeandtypeofanobjectfromsuchaquantumisdeterminedfromtheinformationinthequantummap.Effectively,thequantummapentrypointstoadescriptorforallquantainthezonethathavethesamesizeandtype.Thisdescriptoridentifiesthesizeandtype.(Notethataquantizedzonecansupplystorageforobjectsofdifferentsizesandtypes.Eachquantuminaquantizedzoneisuniformwithrespecttosizeandtype,butdifferentquantainthezonemayhavedifferentobjectsizeandtypeattributes).NewZone:PROC[sr:SizeRepresentation_prefixed,base:Base_nullBase,--defaultwillusetheRootBaseinitialSize:LONGCARDINAL_0--words]RETURNS[ZONE];ZONEsarecollectibleobjects.AZONEwillbereclaimedautomaticallyifnoreferencestoitremainaccessibleandifnoreferencesremainaccessibletostorageinanyofitsquanta.TrimZone:PROC[zone:ZONE];Thismergesadjacentblocksonzone'sfreelistsandthenreleasesallquantathatdonotcontainallocatedstorage.Releasedquantaarereturnedtothezone'sBase.TrimAllZones:PROC;ThisinvokesTrimZoneforeachZONE.MergeAllPrefixedZones:PROC[zone:ZONE]RETURNS[BOOL];ForeachprefixedZONE,mergeadjacentfreeblocksonitsfreelist.IsZoneEmpty:PROC[zone:ZONE]RETURNS[BOOL];ThisreturnsTRUEiftherearenoquantaassignedtothespecifiedzone.GetSystemZone:PROCRETURNS[ZONE];Thisreturnsapredefined,prefixedZONEintheRootBase.ThiszoneisusedforNEWexpressionsinwhichthezoneargumentiselided.ControllingthegarbagecollectorSetCollectionInterval:PROC[newInterval:LONGCARDINAL--words--]RETURNS[oldInterval:LONGCARDINAL];Thecollectorisautomaticallyinvokedwheneverncollectiblewordshavebeenallocatedsincethelastcollection.SetCollectionIntervalallowstheclienttospecifyn.Garbagecollectionwillalsobeinvokedautomaticallybythereference-countingmachinerywhenitstablesbecomefullorwhenmorequantathanareavailablearerequiredfromaBase.Ifthetablesoverflowduringacollectionthenreferencecountingandtheincrementalcollectorwillbedisabled.Thetrace-and-sweepcollectorwillbeinvokedatthistimetoperformamoreleisurelyandthoroughcollection(recoveringcircular3rb)>M#'-+K048;=ACF` $(+ 23 <]T q"7$4(Z+-0W3356" )+G-36 >2@FtQt#: %'). /2 5>7;/=}@CF'O)  $'?*,0`4m7X8?BvEN5 "i(+X.25;}=8>nDH#L{"$']*F-06h;,= ?CFHJ!\$'# uH]F7,C-E '$;%v-E-E.36v9C;uCQ #(O02v4CQ4CQ5~uA7 r?z &/+V-146=P EG=r +!% +./1 8f= C8D;bu9B %r6w$)"u+$6+6r.6.6/25k8;A@FB2F5 &+1~68S=?AEu2 r/u/ /r'$/'/)a,u-v& /5 r*_"',1}4I8:IAdE  "'P)+ 16Q8:?>Ab &Sc!"5$>&',*-/468: ? E}v) TTVm$structuresandinaccessibleobjectswithpinnedreferencecounts)andreconstructthereferencecounttable.SetMaxDataQuanta:PROC[nQuanta:CARDINAL]RETURNS[CARDINAL];ThisestablishesthemaximumnumberofstoragequantathattheCedarruntimesystemwillrequestfromthePILOTSpacemachinery.Whenanallocationrequestoccursthatwouldcausethislimittobeexceeded,acollectionfollowedbyTrimAllZones[];TrimRootBase[];willoccurandtheallocationrequestwillthenberetried.SetMaxDataQuantareturnsthepreviousvalueofthisthreshold.Athresholdvalueof0meansthatnolimitisenforcedbytheCedarruntimesystem(thisisthedefaultsetting).ReclaimCollectibleObjects:PROC[suspendMe:BOOLEAN_TRUE,traceAndSweep:BOOLEAN_FALSE];Thiscausesacollectiontobeinitiated(returntothecallerwillbedelayeduntilcompletiononlyifsuspendMe=TRUE).Whenthecollectionfinishes,apassismadeoverthefreelistofeachprefixedzonetomergeadjacentfreeblocks.IftraceAndSweep=TRUEthenaTraceAndSweepcollectionwilloccurratherthananincrementalone.ATraceAndSweepcollectioncausestheworldtowedgeforroughly30seconds.TheCedar"garbagecollection"strategyisbasedonthemaintenanceofreferencecountsbyanincrementalcollectorthatrunsconcurrentlywithclientprograms.Thesystemwilldoatrace-and-sweepcollectioniftheincrementalcollectorrunsintotrouble,forexampleifitstablesoverflowduringacollection.Acompactifyingcollectorisplanned,butisnotyetdesigned.MonitoringthegarbagecollectorTheproceduresbelowareintendedforusebya"collectorwatcher"process(seetheexample).ReclamationReason:TYPE={clientRequest,clientTAndSRequest,clientNoTraceRequest,rcTableOverflow,allocationInterval,quantaNeeded};IsCollectorActive:PROCRETURNS[active:BOOLEAN,previousIncarnation:CARDINAL];WaitForCollectorStart:PROCRETURNS[incarnation:CARDINAL,--identifiesthecollectioneventreason:ReclamationReason,wordsAllocated:LONGCARDINAL,--sincepreviouscollectionwasinitiatedobjectsAllocated:LONGCARDINAL--ditto--];Thisreturnscontrolsometime(soon)afterthecollectorbecomesactive.Returnsimmediatelyifthecollectorisalreadyactive.WaitForCollectorDone:PROCRETURNS[incarnation:CARDINAL,reason:ReclamationReason,wordsReclaimed:LONGCARDINAL,objectsReclaimed:LONGCARDINAL];Thisreturnscontrolsometime(soon)afterthecollectorceasesactivity.Returnsimmediatelyifthecollectorisinactive.4qbX  "%(;+046 WC"F4u_# /^ r[v  'E,W-279;?EYX"&* 157 =BFX'!w"$l&],- 49yVr$ rTV  e &+q.1:3'v7T8TrDTE`TSx- "% ,5-4#79;,?BDH#Qn#(M,/1O38WuN))7(>@J) M" 5= >rJM1 $&(.i3R5@7;>@FHH v NH Hr(Hv)H*Hr-H.H.25* ;G@AD{EG= S#X(+-6186{9=v>G=?PG= rEvEEr ExE'H ) /2Q6 :=,? FC &+/-1z3)7m9>@qAX5w $(),.w0Y 68<@ZACu ?a $p&)/1C4689xA FxG> 8!#')-.0:3G7;4< A3BZ 7 ,"c'3*+@9 (%&*r$%? +.< 4qu#%!, 0r! "N #K'B, 35uj-1r9Pj9ju=j>jrdo"z)-1*39?DW, + &',Yu%* H+&6 Hv-@1 H.<2 r*u")H-14U:M>DW + &'v)TVm$9Exampleofa"collectorwatcher"process:...CollectorWatcher:PROC={DOni,incarnation:CARDINAL;reason:ReclamationReason;wordsAllocated:LONGCARDINAL;--sinceprevcollectionstartobjectsAllocated:LONGCARDINAL;wordsReclaimed:LONGCARDINAL;objectsReclaimed:LONGCARDINAL;[incarnation,reason,wordsAllocated,objectsAllocated]_WaitForCollectorStart[];IFstopPleaseTHEN{cwStopped_TRUE;RETURN};WriteString[SELECTreasonFROMclientRequest=>"[clientRequest",clientTAndSRequest=>"[clientTAndSRequest",clientNoTraceRequest=>"[clientNoTraceRequest",rcTableOverflow=>"[rcTableOverflow",allocationInterval=>"[allocationInterval",quantaNeeded=>"[quantaNeeded",ENDCASE=>ERROR];WriteString["Collectioninitiatedafterallocating"];WriteLongOctal[wordsAllocated];WriteString["words,"];WriteLongOctal[objectsAllocated];WriteLine["objects]"];[ni,,wordsReclaimed,objectsReclaimed]_WaitForCollectorDone[];IFstopPleaseTHEN{cwStopped_TRUE;RETURN};IFni#incarnationTHENWriteLine[""];WriteString["["];WriteString["Collectionfinished,"];WriteLongOctal[wordsReclaimed];WriteString["wordsreclaimed,"];WriteLongOctal[objectsReclaimed];WriteLine["objectsreclaimed]"]ENDLOOP};...Process.Detach[FORKCollectorWatcher[]];StatisticsNWordsAllocated:PROCRETURNS[LONGCARDINAL];Thisreturnsthenumberofwordsofcollectiblestoragethathavebeenrequestedsincethebeginningoftime.NWordsReclaimed:PROCRETURNS[LONGCARDINAL];5rb)f #)_y^$ (X\Zz*Z '*Y *Wa&*9U$)0 2w*T(X,*Rg&**P(X,*Mm $+96aK*J $)0 2w4'96*Ht aF#I)0E" *-gCz/1A03O@),/>/1< *,9;/$'*9 $ .?6; E*7*65 $**4!*2 #I *1<a,a/*- $)0 2w4'96*,B9 *($ .?2w96*'J*% $ .?6*#*"P $* 3O* !* #I* RV]%r1b u"n'' 3? rg!'(,. 5!9<?CN &#%u B#' 3 v)pTVm$Thisreturnsthenumberofwordsofcollectiblestoragethathavebeenreclaimedsincethebeginningoftime.BasesRTBasic.Base:TYPE...ABaserepresentsacontiguousregionofvirtualmemory.Basesareusedtodefinetheoriginforrelativereferencetypes(whicharenotimplementedyet)andtodefineregionsofvirtualmemoryfromwhichzonesgettheirdataquanta.Thislatterpropertyisusefulbothforcircumscribingandforlimitingthestoragethatcanbeacquiredbyzones.ABasemaynotbemovedorextendedafteritiscreated.GetRootBase:PROCRETURNS[Base];ThispredefinedBaserepresentstheentireaddressspace,notincludingtheMDS.ItisthedefaultBaseforcreatingnewBasesandzones.NewBase:PROC[size:LONGCARDINAL,baseParent:Base_nullBase]RETURNS[Base];sizeisinwords,roundedtothenearestnumberofstoragequanta.Aquantumisasectionoftheaddressspacethatincludesaddresses[j*Q..(j+1)*Q)whereQisafixedvaluecalledthequantumsize(currently4pages)andjiscalledaquantumindex.AquantumisthesmallestamountofaddressspacethataBasecanoccupy.ThenewBaseobtainsitsstoragequantafromitsparentBase.UseofthenullBasedefaultforthebaseParentargumentcausesRootBasetobeusedastheparent.Basesarecollectibleobjects.ABasewillbereclaimedautomaticallyifnoreferencestoitremainaccessible(thiscanbetrueonlyiftherearenozonesinit).ItsquantawillbereturnedtoitsparentBase.TrimRootBase:PROCRETURNS[nSpacesDeleted:CARDINAL];TrimRootBaseattemptstofindanddeletePilotspacesthatareassignedtotheRootBasebutfromwhichnostoragequantaarecurrentlyassignedtoanyZONE.Afteracollectionfinishes,thecollectorinvokesTrimAllZones[]followedbyTrimRootBase[]ifthecollectionwasinitiatedbecausevirtualspaceisexhausted.UnusualoperationsonZONEsforsophisticatedclientsZoneFullProc:TYPE=PROC[zone:ZONE,size:LONGCARDINAL];ExtendZone:ZoneFullProc;ThisaddsstoragequantatoaZONE.Thequantacomefromzone'sBase.sizeisanumberofwordstobeadded,andisroundeduptothenextmultipleofthequantumsize.IftheBasecannotsupplytheneededquanta,agarbagecollectionfollowedbyTrimAllZones(seebelow)willoccur.SetZoneFullProc:PROC[zone:ZONE,proc:ZoneFullProc]RETURNS[oldProc:ZoneFullProc];WhentheallocatorfindsthatinadequatespaceisleftinthespecifiedZONEtosatisfyanewrequest,itcallstheZoneFullProcfortheZONE,andthenre-attemptstheallocation.Theinitial(default)ZoneFullProcforeveryZONEisExtendZone.SetZoneFullProcestablishesprocaszone'sZoneFullProc.6rb)!'(,. 59<?CD`&#%1^x[u[["rYuvY~YrYDY$x% ,1w3f7=ADnGW\6",$^)1/#27(9p; D!FU_"Y$(e-135=9;I>AFuTS "n&), 5e8':o?BFRfv"{$)*.<1w4$6K; =C#FH#PuN@ K$ rK !$ +j-16:= CEwJ+!$',N/<25uG %N)AE (,.25 CqrCq{Cq2"(),)067BnE3FT;?9|j7 P$&+A/248@uB9|C9|r7Tu 7!7r)7*W7/4:&;=@BD5VN} #(*-)/1{7 ?A,C 3R. %^(i*,/237j9;?]@CD2_P!#%t)u/ $9 r- &(|+.g26:\=M?E^G/+a M#').W25,;@pBD)9 #),A2/7 AG( !"%\ +.=38=@B> 1% c i%w' /u# #% .37<@  a r"'g)*L/326:Yu=>rA+ABuF*FrnCm!#%-&(-?/1]68:<@EyG/ ".$',\03<8 =>1CZ XT (3*/21u!7M 7)> r$O#'*` 1z5A69F;=wCEG }$%(+ 357<?UB[   #q'W, 57;@Ak  ."C u) .) .r, .-t .u.} ./B .r1 .29 .3B v)TVm$%SIGNALsandERRORsInvalidSize:ERROR[size:LONGCARDINAL];RaisedbytheallocatorandbyNewBase,NewZone,andExtendZoneiftheirsizeargumentistoobig.MemoryExhausted:ERROR[base:Base];RaisedbytheallocatorandbyExtendZoneandExtendUZone.NarrowRefFault:ERROR[ref:REFANY,targetType:Type];RaisedbyNARROW.NarrowFault:ERROR;RaisedbyNARROW.UnsafeProcAssignment:SIGNAL[proc:PROCANYRETURNSANY];1.2TheUnsafeStorageInterfaceThisisanUNSAFEinterfacetofeaturesthatallowtheprogrammertodealwithUNCOUNTEDZONEs.NewUObject:PROC[size:CARDINAL,--wordszone:UNCOUNTEDZONE,type:RTTypesBasic.Type_RTTypesBasic.nullType]RETURNS[LONGPOINTER];ThisisausefulalternativetotheMesaNEWexpressionforallocatingobjectsfromanUNCOUNTEDZONEthatcarrytheirtypes.GetHeapReferentType:PROC[ptr:LONGPOINTER]RETURNS[type:Type];ThisreturnstheTypethatisassociatedwiththespecifiedobject.THISISUNSAFE.ItisintendedonlyforobjectsthathavebeenallocatedfromanUNCOUNTEDZONEthatwascreatedbyNewUZonewithtypeRepresentation=TRUE.Ifptr=NIL,GetHeapReferentTypereturnsnullType.NewUZone:PROC[initialSize:LONGCARDINAL_0--wordssr:SizeRepresentation_prefixed,typeRepresentation:BOOL_FALSE]RETURNS[UNCOUNTEDZONE];NewUZonecreatesanewUNCOUNTEDZONEthatwillgetitsquantafromtheRootBase.FreeUZone:PROC[uz:UNCOUNTEDZONE];FreeUZoneexplicitlydeallocatesuz,whichisassumedtobeanobjectthatwascreatedbyNewUZone.ExtendUZone:UZoneFullProc;ExtendUZoneaddsquantatoanUNCOUNTEDZONEthatwascreatedbyNewUZone.ThequantacomefromtheRootBase.sizeisanumberofwordsthatisroundeduptothenextmultipleofthequantumsize.AgarbagecollectionfollowedbyTrimAllZonesisinvokedifRootBasecannotsupplytheneededquanta.UZoneFullProc:TYPE=PROC[zone:UNCOUNTEDZONE,size:LONG7r1b)xu_  'O+ r].6- &(*17:| BECF[I!uY #& -OrV:6 &/(* 25f uT!P *-O1o :GrQ:6uO rL:6uJ& 1359@roGuGG rG =G1E &(.158 @CFt1Cv7u1@ GX?PuS%'%=E';x;; u%;&;)x+9;, ; u3;4;X:Vu%r7h %L&)Jv,7-7r071=77H9} ?D?G61#&P)-u13#+/P2 !r/,"%& -l028=$AB-TQ V"}'),0659:;E,?!){,8;?uA,?B,?vDp,?F,?rH,?v*r#*$E*v(t*)F*r-*u1(X&qu %-S.v0&q1Q&q2Ou`$)k*`# ',6-X!xu)vrS!g"%/47:u<>CG/Su1 ",HvXrX0X"V u)+X*Xr*X+X/06L79;?B6Duru13  v rf"~'),66;?BHGvr ` 2$(a+.u45fr78V9X:|?ATE[H#go $)+Z-368p= C  !8&z'.269P>u1 B #&@ 00:@YDv)fTVm$CARDINAL];SetUZoneFullProc:PROC[zone:UNCOUNTEDZONE,proc:UZoneFullProc]RETURNS[oldProc:UZoneFullProc];Whenzone'sallocatorfindsthatthereisinadequatestoragespacetosatisfyanewrequest,itcallszone'sUZoneFullProcandthenre-attemptstheallocation.Theinitial(default)UZoneFullProcforeveryUNCOUNTEDZONEisExtendUZone.SetUZoneFullProcestablishesthespecifiedprocedureasthespecifiedUNCOUNTEDZONE'sUZoneFullProc.MergeUZone:PROC[zone:UNCOUNTEDZONE];MergeUZonemergeszone'sfreelists.ForprefixedUNCOUNTEDZONEs.TrimUZone:PROC[zone:UNCOUNTEDZONE];TrimUZonemergeszone'sfreelistsandthenreleasesallquantathatdonotcontainallocatedobjects.Releasedquantaarereturnedtotheoperatingsystem.IsUZoneEmpty:PROC[zone:UNCOUNTEDZONE]RETURNS[BOOL];IsUZoneEmptyreturnsTRUEiftherearenoquantaassignedtothespecifiedzone.GetSystemUZone:PROCRETURNS[UNCOUNTEDZONE];Thisreturnsapredefined,prefixedUNCOUNTEDZONEthatwillgetitsquantafromtheRootBase.Ithasnotyperepresentation.InvalidPointer:ERROR[ptr:LONGPOINTER];RaisedbyFREE.2.UniversalReferencesandRuntimeTypes:TheRTTypesBasicInterfaceOneofthe"delayedbinding"featuresofsafeCedaristheabilitytomanipulategeneralreferenceswithouteithercompile-timeknowledgeofthereferenttypeortheuseofaLOOPHOLEtospecifythereferenttypewhenitcomestimetode-reference.Suchreferencesaretermed"universalreferences"andhavetypeREFANY.TheCedarlanguagefacilities(REFANY,NARROW,WITH...SELECT)fordealingwithuniversalreferencesaresupportedatruntimebyasystemthatcanallocateanobjectofagiventype,determinethereferenttypeofaspecifieduniversalreference,anddeterminewhethertwogiventypesareequivalent.Inadditiontosuchbasicsupportforcompiledprograms,theCedarruntimesystemprovidesanimplementationfortheRTTypesBasicinterfacedescribedbelow.Anotherclientoftheruntimetypesystemisthegarbagecollector,whichmustbeabletodetermineforeachobjectinmemorywherewithinthestorageforthatobjecttherearereferencestootherobjects.Forthispurpose,theruntimetypesystemmaintainsadatastructurethatrepresentsthisinformation(calleda"referencecontainingmap")foreachtypeforwhichacollectibleobjecthasbeencreated.2.1TypesType:TYPE=RTBasic.TypeATypeisadatumthatrepresentsaCedarTYPEatruntime.Conceptually,everycollectibleobjectincludesaTyperepresentingtheTYPEofthedatavalue.Thisisstoredwiththeobject.TheCedarNEWexpressionautomaticallyattachestheappropriateTypetothenewlycreatedobject.TheNEWexpressionistheonlywayinthelanguagetocreateacollectibleobject.8u1b 1_ ;X]u&\P$ XZu&}rX)u)X)X)rX)X) #'V*C-/u 6;k??A EYFVeulV2Vr!V")V#) ,/2 9@L S3 'T)/^57~9?QX u1O H %x/3vL rLLu"L#HLr%L&?L'H*-./5G?Nu1J  $D-vGrGGu!fG"+Gr$G%"G&1)+.168=T@(B5DE%*,e236<-u1Cm  &0z5 v@ r@^@#()h,/E1K5;W=?dE u1>p$e5r;?% %+5:=@sBD:JY!9"%&',*<u179 %*r5Nyvt5NF5Nr5N 2:n t+#(mu+F2,M2 r6 262o0Qfv#(*.2t4)6;S=K Do. ` 6 (0I2q5?:>Y@CZF=Heo-C %),.#2\57G ?C o+[L  #&),/36:@k Eo)A!p'*B//2d8Z >AdGo( K!&(,.l/3L6=8?DGo&eU1 "%>+137n;=V o#Up$&,3|5: ?nDo"@_ >{ (.4qo% 5 $;%]'B+[ 03Q6 79;M@BJDHo- o"I$'*, 23l6b:i<>CREHos"$ *,> 2N56 <9 AEFo  V"M$roMu1xu!"rPuPPrP2P_" % +-1B57O= E %Cu&'or*+0 259b;6=@DH#0 v  r * &6 .36/ u= >o rA A C4E v! " r% &l ,.r14s79<#B-DHe 5 uv) ITVm$-ACedarexpressionoftheformCODE[<>]returnsaTypeforthespecifiedTYPE.(NOTE:thisisaninterimsyntax.TherewillbebettersyntaxinCedarforacquiringTypesfromTYPEexpressions).nullType:Type=...Byconvention,thisisadistinguished,predefinedTypethatistheTypeofthereferentofNIL.Otherdistinguished,predefinedTypesarelistedbelow:unspecType--thedistinguishedtypeofUNSPECIFIEDfhType--thedistinguishedtypeoflocalFramesgfhType--thedistinguishedtypeofglobalFramesGetReferentType:PROC[ref:REFANY]RETURNS[type:Type];ThisreturnstheTypethatiscarriedbythespecifiedobject.Ifref=NIL,GetReferentTypereturnsnullType.GetCanonicalType:PROC[type:Type]RETURNS[Type];ThiscomputesthecanonicalTypeforthespecifiedType.EachTypehasacanonicalType.CanonicalTypesareusedfortestingTypeequivalenceefficiently(ift1andt2arecanonicalTypes,thent1=t2IFFt1andt2representequivalentTYPEs).Undernormalcircumstances,theCedarclientwillnotusethisfunction.NotethatGetCanonicalType[nullType]=nullType.GetCanonicalReferentType:PROC[ref:REFANY]RETURNS[type:Type];Thisisincludedforconvenience.ItreturnsGetCanonicalType[GetReferentType[ref]].EquivalentTypes:PROC[t1,t2:Type]RETURNS[BOOL];Thisisincludedforconvenience.ItreturnsGetCanonicalType[t1]=GetCanonicalType[t2]ThiswillbeTRUEifthecorrespondingCedarTYPEsareequivalent..IsReferentType:PROC[ref:REFANY,type:Type]RETURNS[BOOL];Thisisincludedforconvenience.Itreturns(EquivalentTypes[GetReferentType[ref],type])NarrowRef:PROC[ref:REFANY,type:Type]RETURNS[REFANY];Thisisusefulforchecking,andisincludedforconvenience.Ifref=NIL,NarrowRefreturnsNIL.Otherwise,NarrowRefreturnsrefifGetCanonicalType[type]=GetCanonicalReferentType[ref]orraisesSafeStorage.NarrowRefFaultifnot.2.2TypeattachmentsPutTypeAttachment:PROC[type:Type,attachment:REFANY];GetTypeAttachment:PROC[type:Type]RETURNS[REFANY];TheseprovideawaytoassociateanarbitraryobjectwithaspecifiedType,forexampleauser-definedprintprocedure.Thisfacilityisviewedasaninterimoneuntilthereareappropriatelanguagefeaturesforusefulapplications.9rb | !F"%Xv(b )b 1 r;b ;b ?u@b Ab rDb Enb G/`y$n&(P*+.3o7\9;?CEw^/D!P$( u1\L\eIrY ^ "Q#n , 26v97:<@dBDcX & -147U !Q# ,/0 S "$u ,/1 R? "B$ ,01 u1N u'Q*. :rK $').1b4?:x?evAdKAKDFrHKvIr fI Iv%I%Ir*Iu1GY \ )U- rDQw D!XD&r*BD*D,.48<-?BEC{C,e#%)-+x/3 ; ACtE&GA^" %G),t.0128 ?E4?B #&+/3696')r/">6u1;&.|1P: !r7~ x!\ )*v55%r1s5u13K&P(P1 r/ x!\ )*v-l-l%'vr5-l+ !#"$ -168 u1)9B&)h-1P' r% x!\ )*v#Z}#Z%1u1 "&*..Y2 =rN x%(*/1 vtrvrvr%%v)*r+ vr#(#v'(`r**{vHHr& Hv'H)Hr9THv9Hr;pHzu. v!" r+, -o4 u1! */ 8;;1 !&S+/ :r !#O(*0Q4W7_8u>AD  !L (+'/157<9=@CG; 5 R"'D)- y4 5v)TVm$2.3FinalizationofcollectibleobjectsItisoftenconvenienttospecifyactionstotakewhenanobjectofaparticularTypeisnolongeraccessibletoanyclientofthepackagethatcreatedit.Suchpackagefinalizationactionsmightinclude(forexample)removalofareferencetotheobjectfromapackage-maintainedcache.Abuilt-infacilityforobjectfinalizationismorethanaconvenience.Inapplicationswhereapackagemustmaintaincopiesoftheobjecthandlesthatitgivestoclients,thealternativestopackagefinalizationareexpensive,andduplicateinonewayoranotherthestoragemanagementfunctionsthatthecollectorprovides.TheCedarfinalizationmechanismisspecificallytailoredtosuchapplicationsandtotherequirementsofefficiencyandsafety.Thoughonecanimaginemoregeneralfacilitiesforfinalization,webelievethatthefeaturesdescribedbelowareapowerfulandusefulset.TheyareinexpensiveandSAFE.BEWARE:Untilappropriatelanguagechangesaremade,itisnecessarytoestablishfinalizationforaTypeBEFOREallocatinganyobjectsoftheType.AllocateobjectsoftheTypeONLYintheprogrammodulethatmakesthecallstoestablishfinalization.UsetheexactsameTYPEexpressioninthefinalization-establishingcallsandinNEWexpressionsforobjectsoftheType.ProceduresEstablishFinalization:PROC[type:Type,npr:[1..maxNPackageRefs],fq:FinalizationQueue];typeisaTypeforwhichfinalizationactionsaretobeenabled.fqisaqueueonwhichthecollectorwillputREFstofinalizableobjectsofthatType.NotethatfinalizationisapropertyoftheobjectType,notoftheREFType.ThecollectorputsaREFtoanobjectonthequeueforitsTypewhenitfindsthatexactlynprreferencesremaintotheobjectinotherobjects.Inotherwords,npristhenumberofreferencesthatareconsidered"packagereferences"forthispurpose.NotethattheremustbeatleastonepackagereferenceforafinalizableType.Smallpoints:(1)Ifthefinalizationqueueisfull,thecollectorwilltryagainnexttimeacollectionoccurs.(2)Referencesonthestack(i.e.inlocalvariablesofaprocedure)arenotincludedinthecountingtodeterminewhetheranobjectshouldbefinalized.Referencesinglobalframes(i.e.inprogramvariables)AREincludedinthiscounting.Ifanyreferencestotheobjectappearonthestack,theobjectwillnotbefinalized.Typically,aclientwillFORKaprocessthatinvokesFQNexttodequeueREFsfromfqandthenperformsthedesiredfinalizationactions.FQNextwillwaituntilfqisnon-empty,sothisprocesswillbeinactivemostofthetime.TheuserprocedurethatinvokesFQNextshouldbeexternaltothemonitorthatprotectsthedatastructurebeingfinalized.ThisprocedureshouldthencallanENTRYproceduretodothefinalizationactions.Seetheexamplebelow.ReEstablishFinalization:PROC[type:Type,npr:[1..maxNPackageRefs],fq:FinalizationQueue];Thisisusefulwhen(forexample)anewversionofaprogramthatestablishes10rob) @ !|1_$ !z&*,{/|3:529S;F?FrBRFBF 1Dn #w1Bp u?$>1<:96rb66!v#' .3x57s9au>6?p6r@6A;6B@CgG4Q#&)U-M/ 5:/ r?/ @5/ AE)u-cr-c-c_#%6 +.w0 7= DF+V #'<*,.E1r4&9p?vAB *q' !# )- .E02789t;F>M@CvD} %a #!$&),-0T5 67 =V?UAnFG$7l#N')n,02W 7C = >BEH" !#(O)+013 8:?<?]BDFk  " rZ &l#Iv&Z&Zr*Z+Z03v8Z9Zr>6Z>Z@Eu r"(|*/ 6v;~A\G[u[[r/[3 [:?EuYr(Y)oY,L0;248<=? GX= #%&?( )v,- 36r:G< AH#V` y#e%('c), 5U9=?BSGT G"$'d)j+.uRg#U+-lO"'.MY %d-/#2$rJ gu,&J,Jr1J1J6q8?D1vEJFJrHJI*cuF7"x0 ;XrD<v"D#Dr%D&:D'q)Y.u2HD2Dr3D4D7:[;|AFBu U$ &i+015'v7-Bu7Bur8lBu9jBuv:Bu;9BurE1z*/a )0**.H,.?03O8^*#I'-g2w96R)@'%&58^$7%" roV<x1 u@ $ -x1G uGG. 7r1vr% 9v:9,9rG99u99 r 9!h9oN $C).06: B(G/o ("%}(1 .04q9<?RACoc "$*+vo r   v  r!` ! $&]*.&25wv7 8y r<8 < >@FHevo 5rl 5 5Ov! 5" 5$~r( 5( 5.06Z86v9 5: 5<r@ 5A; 5Fv)eZTVm$ATOMcanappearastheTYPEexpressioninanarmofaWITH<>SELECTconstruct,andthatNILcanbeassignedtoanATOMvariableorpassedasanATOMparameter.TheCedarruntimesystemmaintainsanATOMdictionary.ThisisanamespacethatisglobaltothecurrentCedarexecution.ItisusedasauniquemapbetweenprintnamesandATOMs.ThecompilerrecognizesasanATOMconstantanyidentifierthathas$asitsfirstcharacter.ATOMsareacquiredfromtheATOMdictionaryforsuchconstantsbytheCedarruntimeloader.TheAtomsPrivateinterfaceprovidesthefollowingoperations:GetAtom:PROC[pName:Rope.ROPE]RETURNS[ATOM];GetAtomisusedtoacquiretheuniqueATOMwiththespecifiedprintname.AnewATOMwillbecreatedifnecessary.UnsafeMakeAtom:PROC[pName:LONGPOINTERTOREADONLYTEXT]RETURNS[ATOM];LikeGetAtom,butunsafe.Includedforconvenience.EnumerateAtoms:PROC[callee:PROC[ATOM]RETURNS[stop:BOOL]]RETURNS[ATOM];EnumerateAtomsmaybeusedtoenumeratetheATOMsthatareknowntotheruntimesystem.Itwillinvokethespecifiedprocedure("callee")exactlyonceforeachATOM.EnumerateAtomswillreturneitherwhenaninvocationofcalleereturnsTRUEorwhentherearenomoreATOMstoenumerate.Intheformercase,thevaluereturnedbyEnumerateAtomswillbetheATOMthatwaspassedtocallee.Inthelattercase,thevaluereturnedbyEnumerateAtomswillbeNIL.Neverfear:nomonitorlockisheldbyEnumerateAtomswhencalleeisinvoked.WhilethecallonEnumerateAtomsisactive,ATOMsthatarecreatedeitherbyexplicitcallsonMakeAtomorbyloadingaprogrammodulethatdefinesnewATOMconstantsmayormaynotbeincludedintheenumeration.AnATOMvaluecanbeLOOPHOLEdtoaREFAtomsPrivate.AtomRec,whichisdefinedasfollows:AtomRec:TYPE=RECORD[pName:Rope.Text,--theargtoGetAtompropList:REFANY_NIL,link:ATOM_NIL--usedbyGetAtom];4.ConfigurationParametersThecurrentstoragemanageruses1024-wordquanta(4pages),a22-bitaddressspace,andrequiresroughly65Kwordsofstorageforitsinternaldatastructures,whichincludethereferencecounttable,thequantummap,andvariousauxilliarytablestosupportruntimetypes.Onlyonepageofthisdataispinned.Thecodeisdesignedtoworkwithanyquantumsizethatisapowerof2between2^8and2^15,andwithanaddressspaceofanysizebetween16and28bits.ChanginganyoftheseparametersrequiresmodificationoftheruntimesystemandtheCedarmicrocode,butdoesnotrequireclientrecompilation.12vob)rb)b)v b)b)r#Cb)#b))+-0r2+v/`<$ro^ Jv ^^r^L^ ."'z)v*^+^r/~^0.^46[:2^?%^rB^C|^o\_Nn /&uv(m\_)`\_r-\_-\_ 368p9=gA$CEloZ}G_ "$c%) *+039 @;vBZCZrGZoX=c:  v"X=#X=r'{X=(X=-/ 58;K<>e@[CO voVrV:VWv!V"Vr&[V'"V,.179;?DoRsvGRs:Rs rGRsRs &|(. u1Or x$.O%Ou'zO(OPNQ vKr.KK!&)#v-K.Kr2K3K58$= EFvJ/rJ/J// "$J u1G */,68A.PF rC"!%+- u1A} ) 3 ?vP?o v< r <!<$ &B)+2v5g<6Z<r9t<:<=@pE;G/;M' k#')/6 *@jC6Wv6W6W r"6W#6W%N'Lv)6W*6Wr.Y6W.6W1638c: >[@8BFH4X v"4#4 r.;4/940v2434r54q54649O;=AD5E]G3 { 3!&3q#3$3$r03v0 u0 r*0+_0,Lv0v01h0r405p08#:[? BD.v..r!.!."$)y*0473!$&(x* qo*K/'# $d%R( x.k*q.*47?8b