CSLNotebookEntryToCedarUsersDateOctober29,1982FromPaulRovnerLocationPARC/CSLSubjectConciseGuidetoStorageManagementinCedarFile[Indigo]Documentation>SafeStoragePrimer.tioga,.pressXEROXReleaseas[Indigo]Documentation>SafeStoragePrimer.tioga,.pressDraft[Indigo]Documentation>SafeStoragePrimer.tioga,.pressLasteditedbyPaulRovner,October26,19827:51pmAbstractSafeStorage.dfcomprisesthepartsofCedarthatprovideruntimesupportforCedarlanguagefeatures:storageallocation,garbagecollection,REFANY(NARROW,WITH...SELECT)andATOMs.ThismemoisaconciseguidetothemostcommonlyusedfeaturesofSafeStorage.dfforthebeyond-noviceclientwhounderstandstheCedarlanguage.Moredetailedandcompletedocumentationcanbefoundin[Indigo]Documentation>SafeStorage.tioga(and.press).OverviewofthemostcommonlyusedpublicinterfacesofSafeStorage.dfSafeStorage.mesaprovidesfacilitiesformanagingsafe(i.e.collectible,REF)storageandforcontrollingthecollector.ItisbyfarthemostcommonlyusedinterfacepurveyedbySafeStorage.df(hencethechoiceof.dffilename).UnsafeStorage.mesaprovidesfacilitiesformanagingunsafe(i.e.non-collectible,LONGPOINTER)storage.RTTypesBasic.mesaprovidesfacilitiesfordealingdirectlywiththebasicruntimetypesystem(viaRTBasic.Type's),e.g.tospecifyfinalizationforaTypeorgettheTypeoftheobjectaddressedbyaREF.WhenandwhennottocreateyourownZONEGenerally,apoormatchbetweentheuseofaZONEandthedesignofitsallocationstrategywillleadtoinefficientoperation.Ifyouareconcernedwithsuchperformanceissues,youwillwanttoselectanallocationstrategythatfitsyourusage.(Itmayalsohelpforuswizardstoexploreotherallocationstrategies,perhapsasadditionaloptions.It'sonthelist.)IncurrentCedar,thesystemZONE(i.e.theoneyougetifyouuseNEWratherthanz.NEW)hasasinglefreelist,andhenceissusceptibletofragmentation.Heavyuseforobjectsofwidelydifferent1pa ?q ^r^ q+^r6^;R=q ZrZq+Zr6Zs:Z;Zq V3rV3b % -L.q RIr RI5/St{Jq @ r@54Rq >r>86Mq =@ Vr=@s7=@=@a!$'q :r:  #+&u(, .38=?C 9  &,)u-59l:A1C 7h FO-k")H,c1n3 ;>@V 5  @%s)H.1a7_ @C{E 4 .)- s04p -\!%*m 13 r ) #&g- 0[3~ :? D,GR (T  f "%`(/28l>x@w &~| $$$ $&\,13=_B- "} # $F&+036A9?BDF M\ '*$+T.025c8:=A6G  p  #'Qr [ t1!$&(e).403f79;r AF {   9#%i,/B2 :>ADqG  yt  #&]+-0$26!8i:C?B@E e  8e  &+.02z L"#,%(G*-/1_46:>AG 5 c| %'f 047,9Z=?Cu)TVm$sizesaffectsoverallsystemperformanceadversely.Ifyourpackageorapplicationexplicitlyallocates(viaNEW)morethanabout2Kwordsofstorage,itislikelythattheworldwouldbebetterifyoucreatedatleastonespecialZONEforexclusiveusebyyourpackage.CreatingyourownZONEandguidelinesforselectingZONEparametersSafeStorage.NewZone:PROC[sr:SizeRepresentation_prefixed,base:Base_nullBase,--defaultwillusetheRootBaseinitialSize:LONGCARDINAL_0--words]RETURNS[ZONE];Zonesacquirequantaastheyareneeded.Occasionally,thiscausesanewSpacetobecreatedinVM.Theonlylimitonthenumberandrun-lengthofquantathatcanbeacquiredbyazoneistheamountofavailableVM.Quantaacquiredbyazoneremainassignedtoituntilthezoneis"trimmed"(seeSafeStorage.TrimZone).AllzonesgettrimmedautomaticallywhentheCedarallocatordiscoversthatVMisgettingtight.This(discovery)happensveryrarelyincurrentCedar.ApackagewoulddowelltoinvokeTrimZoneexplicitlywhenthereisalotoffreestorageinthezone,e.g.attheendofabigcomputation.OfthethreeparameterstoNewZone,thechoiceofsr:SizeRepresentationaffectsperformancethemost.Youcansafelyignoretheothers.Aquantizedzoneisgoodiftherearemanyobjectsofthesamesizeandtype,orofafew(roughlyadozenorless,say)differentsizesandtypes.Sequencesandvariantrecordsareexamplesoftypesthatcanhavedifferentsizedobjects.Anintegralnumberofquanta(each1Kwords,4pages)isassignedtoeach(size,Type)combinationservicedbyaquantizedzone.Thismeansthatuseofaquantizedzoneforallocatingjustafewwordsofaparticular(size,Type)iswastefulofVM.Quantizedzonesaregoodforsmallobjectsbecausethereisnoper-objectstorageoverhead.Themaximumsizeofanobjectfromaquantizedzoneisonequantum.Theminimumsizeis2words.Prefixedzonesaremoregeneral(e.g.forTEXTobjects),buttheirallocatorisslower,eachobjectrequiresextrastoragecellstocarrysizeandtypeinformation,andprefixedzonesaresusceptibletofragmentation.Themaximumsizeofanobjectfromaprefixedzoneis(LAST[CARDINAL]-1)words.Theminimumsizeis4words.Thestorageoverheadperprefixedobjectis2words.Adjacentblocksonthefreelistsofallprefixedzonesaremergedattheendofeverycollection.Allobjectlengthsareeven(roundedupifnecessary).Allobjectsbeginonevenwordboundaries.ZONEsarecollectibleobjects.AZONEwillbereclaimedautomaticallyifnoREFstoitremainaccessibleandifnoREFsremainaccessibletoobjectsinanyofitsquanta.FacilitiesinCedarforcreatingUNCOUNTEDZONEsUnsafeStorage.NewUZone:PROC[sr:SizeRepresentation_prefixed,initialSize:LONGCARDINAL_0--wordstypeRepresentation:BOOL_FALSE]RETURNS[UNCOUNTEDZONE];2r b)-. %2 _+b` n %Q*-15w8BD ] ]. 6"& 'd*.0a3}6 :?AGG \Qp Vfj\ ('*17 r SQV "9eO4",#(L*-l/eM 4'I(*,LJ IZ!'6 /2b68; ? @BG Hx"%[ , -2k5979?ZAUB~EG/ Fr/ &'(,!0578;>%AIB Di J$&:+ 4%7:>C C#~N~ &,/A3A59>h@ Ea A|6* $ '+6,-/1r468:<@qBDF ?g =K3 $K&+,.:?! G/ ;ap  9:B!#',Y.0q369Q<>}@5A_D 7t ~'"Z%)/2p7;>>D>E 5K|$'&+1 27;h=BfCH# 4%:? &,F.T/59<A0DFHe 2~J !]"%()5*, 2M59;8@BT /q[a#}(:-|1%24 ;z@MF .M/!"-(+-6/68?DAC[D +;)!$(&z*0U26F;=uB0Ev *k+"U$'* 25\:>@ G (u "G$&$*W-/489FG &I#&o+03h8<>:?dC %&W$#'*/0357x;, "+q#o%& -048:=AV @G !&E) +1 :;=ACuD   ! ')./2n4'6p   u ,r @ "9 {&(Q* + b#%i 5$u) uTVm$ThisguycreatesanewUNCOUNTEDZONE.NewUZoneshouldbeusedinsteadofHeap.Create(itallowsmorethan64KperUNCOUNTEDZONEandallocationismoreefficient).Thesameallocatorusedforcollectibleobjectsisusedhere.Appropriateclevernessisemployedtodononeoftheworkassociatedwithreferencecounting.Cedarallocationmicrocodeisused(!).ThecommentsaboveaboutquantaandSizeRepresentationforZONEsapplytoUNCOUNTEDZONEs,exceptthatnoautomatictrimmingisdone(seeUnsafeStorage.TrimUZoneandUnsafeStorage.MergeUZone)andUNCOUNTEDZONEsarenotcollectibleobjects.BasicDealingswithRuntimeTypes;FinalizationEachCedarobjectcarriesaruntimerepresentationofitsTYPE(i.e.theargumenttotheNEWthatcreatedit).ThisisanRTBasic.Type,whichisa14-bitindexintoatablethatismaintainedbytheruntimesystem.InformationthereinisusedtosupportNARROW,WITHSELECTFROM,andruntimeaccesstosymbolicinformationaboutTYPEs.ThespeciallanguageconstructCODE[]evaluatestoaCARDINALthatisthe14-bitindexforthespecifiedTYPE.RTTypesBasic.Mesaprovidesfacilitiesfordealingdirectlywiththebasicruntimetypesystem(viaRTBasic.Type's),e.g.togettheTypeoftheobjectaddressedbyaREF,todeterminewhethertwoTypesareequivalent,ortospecifyfinalizationforaType.BEWARE:itiswrongtoexpectthatiftwoTypesarenotequal,theydonotrepresentthesameorequivalentTYPEs.UseRTTypesBasic.EquivalentTypes.EveryTypehasaunique"canonicalType".TwocanonicaltypesareequalIFFtheoriginalTYPEsareequivalent.ItispossibleforaclienttospecifyactionstotakewhenanobjectofaparticularTypeisnolongeraccessibletoanyclientofthepackagethatcreatedit.Suchpackagefinalizationactionsmightinclude(forexample)removalofareferencetotheobjectfromapackage-maintainedcache.SeeSafeStorage.pressforthedetails.CaveatsabouttheuseofREFs:limitationsandunsafeoperationsGarbagecollectioninCedarisbasedonthemaintenanceofreferencecounts.Theinherentproblemwiththisschemeisthatthecollectorwillmisscircularstructuresthatarereclaimable.ClientsshouldavoidtheuseofcircularstructureswhenpossibleorbreakcircularitiesbystoringNILwhenpossible.Variousclevertricksareusedtominimizethecostofmaintainingreferencecounts,but(asusual)thesehavelimitations.Themajoroneisthatreferencecountsgetpinnedwhentheyreachamaximum(77Binthesoon-to-be-currentsystem).Clientsshouldavoidbuildingdatastructuresthathavelargenumbers(~thousands)ofpinnedreferencecountswhenpossible.Cedardoesprovidea"TraceAndSweep"collectorthatwillreclaimcirculargarbageandinaccessibleobjectsthatoncehadpinnedreferencecounts,butitwedgestheworldforhalfaminuteonaDoradotodoitswork.TheTraceAndSweepcollectorwillbeinvokedautomaticallywhentheCedarallocatorfindsitselfindirecircumstances.Thishappensveryrarely.SafeStorage.ReclaimCollectibleObjectsprovidesawaytoinvoketheTraceAndSweepcollectorexplicitly.Anotherlimitationderivesfromtheuseofaseparatedatastructureformaintainingreferencecountsthataregreaterthanone(the"referencecounttable").Clientsshouldavoidbuildingdatastructuresthathavelargenumbers(~thousands)ofsuchobjects.3r b)x,%%*167;0?A `).c19 79!< CF ^Cz 1"$0'h* 2 9:k@BfDhG ]3  "(,/ 2o9:= Z^#E&"2-49=? XH% +-25F WW!\+b0p258 ;p Qjk=$ r N1F" +-/t36N8>@zBF L[MG #')*K.L2!5679<= E*G/ J&9 %$%)B+10~8L<@C I !% -P1B6[9D=C Ge - !$0&'W/24P6:>ALC E C0K $g&+036O9?#BHF AB5 $%(-,C2459k;AF ? "$ )J+, =T%p #$'+-0^4t79;ADPG ; q/;0;3=6D8m9={ CF :gCDp!w%8' r,: 7w$ 6"?&(+/51%5=68 >SACFEK 5 oF#&r+%,v05055F rD  $N ~>#%(- 368 @yE #NTt !%8*a, / 78=`@YC  U!')),t.< 5;@C@Ev 8 0 #B$'6-1I3o7;>tBC  qn$)Q-1|69 @#BF( ^ !2'0+/@ < %+.-05o:\?uB% zw%*-h.36s:<?ANF0He MG '-_/17 ?|C$Ew FH &)/32B %$*,8/~169O C   ; 4"$&',/57 ?FE4 qKf %x)D.#270:@TCN 5|) $M&)8u) _TVm$}ComeseemeifyoufindyourselftemptedtouseLOOPHOLEinanywayrelatingtoREFs.Client-alterablesystemparameters:controllingthegarbagecollectorSafeStorage.mesaprovidesaccesstoparametersandoperationsthatcontrolthegarbagecollector.Thegarbagecollectorgetsinitiatedautomaticallywhenever"CollectionInterval"collectiblewordshavebeenallocatedsincethelastcollectionwasinitiated.Thecollectorrunsinthebackground,concurrentwithclientallocationandreference-countingactivity.Per-processaccountingofstorageutilizationisdone;ifaprocesswouldtriggeracollectionwhilethecollectorisrunningANDthatprocesshasallocatedmorethan"CollectionInterval"wordssincethecollectorwaslasttriggeredthentheprocesswillbesuspendeduntilthecollectorfinishes.Itispossibletochangethe"CollectionInterval"systemparameter.Thisbalancesthecostofcollectionagainsttheunreclaimedstorage"highwatermark".Garbagecollectionwillalsobeinvokedautomaticallybythereference-countingmachinerywhenitstablesbecomefullorwhenmorequantathanareavailablearerequiredfromVM.Inthelattercase,allZONEswillbetrimmedandfreeSpaceswillbereturnedtoPilotafterthecollectionfinishes.ItispossibletochangethethresholdonCedarallocatorVMthattriggerssuchacollection.ThisbalancesthecostoftrimmingallzonesandfreeingSpacesagainsttheallocator'sVMhighwatermark.Ifthereferencecounttableoverflowsduringacollectionthenreferencecountingandtheincrementalcollectorwillbedisabled.Thetrace-and-sweepcollectorwillbeinvokedatthistimetoperformamoreleisurelyandthoroughcollection(recoveringcircularstructuresandinaccessibleobjectswithpinnedreferencecounts)andreconstructthereferencecounttable.SafeStorage.ReclaimCollectibleObjectsistheclientinterfaceforexplicitinvocationofthecollector.4r b)ayg!' (+035E7:?Akp [ # ,".5 r U~ !" ), 356:=B6 SG#( +2> E Q#"O (+| 1]4[:=Q?&A O  #/|4 < CD NQ 2M .$k(* 0X46<&=BF Lm ,036/;>A@Fi K }7"~$*m HVz )O- 4i7e<?ACZ FJ  4$ ' DeA o$ -j/^1=TDG B h %o(*0v28;;>@sBFH AQ@ #Z'*~,m236:1< BH ?oO#e%)/25:>T? Fu =N!%(u-8169 ?BE <  9R13#H'( .17=5?B 7N  )/2T4V9;S>A<BHe 6WQ $ ,-13 7:L AFt 4VS( %(Q.O2& 24%$6%(+1g38x ?&@C? u)TVm$a TIMESROMAN HELVETICALOGOLAUREL TIMESROMAN TIMESROMAN TIMESROMANY ' Z!j/$"SafeStoragePrimer.tioga29-Oct-82 12:20:28