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.Heavyuseforobjectsofwidelydifferent1pîÆïaïî§î ?qî ìï^rîòï^ qî+¯ï^rî6ï^î;Rî=�qî ìïZrîòïZîqî+¯ïZrî6ïZsî:–ïZî;“ïZqî ìïV3rîòïV3îîbî î% î-Lî.úqî ìïRIrî ®ïRIð5î/Stî{ïJœqî ìï@œî ôrî¬ï@œð5î4Rqî ìï>îrî¬ï>îð8î6Mqî ìï=@î Vî¯rî¬ï=@îÒsî7ï=@îï=@îaî!žî$äî'óqî ìï:·rî¬ï:· î¦î éî#+î&uî(î, î.»î3¨î8Áî=¯î?ÎîCÉî ìï9îî î£î± î&,î)uî-î5î9lî:äîA1îCÖî ìï7hî åîüîFîOîöî î-îkî"¦î)Hî,cî1nî3 î;üî>î@V î ìï5Áî ÂîÛ îžîî@î%sî)Hî.•î1aî7_ î@ÛîC{îE�î ìï4î šð.î)Ûî- sî0Öï4pî ìï-\îîîëîóî!Íî%’î*m î1ëî3ï rî ®ï)ûîíîê î#»î&gî- î0[î3~ î:Çî? îD,îGRî ®ï(T î î îìîfîÕî Óî"þî%`î(¿î/…î2Äî8lî>xî@w î ®ï&­îî~îÃî|î˜îî ®ï$$î$î¶ î$î&\î,©î1î3¿î=_îB-î ®ï"}î ®ïôî#îÊ î$Fî&œî+ˆî0•î3Éî6Aî9Ìî?îBDîFØî ®ïMîÌî\îî ´ î'áî*$î+Tî.ãî0®î2ýî5cî8òî:±î=îA6îG“î ®ï¥î ×pî ìï¼îºîàîîîî î#Ûî'Qrî ®ï[ îtî«îÿî1î!®î$î&žî(eî)œî.4î0ùî3fî7Ãî9Šî;r îAÀîFäî ®ï³îºî{ î î¤î 9î#î%iî,î/Bî2† î:�î>éîA³îDqîGàî ®ï îyît î¾îßî ¸î#î&]î+î-î0$î2ûî6!î8iî:Cî?Bî@üîEðî ®ïe îí î8îeî  î&Šî+Àî.î0î2zî ®ï Üî€îLî¿î"î î#,î%åî(Gî*öî-°î/ûî1_î4î6‘î:ƒî>”îA½îGî ®ï 5î Éî¥îcîêî“î|îÙ î%Æî'f î0„î4Æî7,î9Zî=éî?“îCéuî)Èïö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î*Ñî-ƒî1èî5wî8™îÇîBÐîD„î ®ï]øî ûî]îîØî.îî 6î"î& î'dî*î.Òî0aî3}î6 î:’î?îAGîGî ®ï\Qî©îäpî ìïVfî¤îjîßî\î ‚ î('î*Êî1œî7 rî ®ïSîÓîØïQVîÀîÆî ¬î"9îeïO§îùî4îÁî",î#£î(Lî*÷î-lî/ËîeïMù î4îî'Iî(Öî*Žî,îØïLJîÀ î ®ïIÁîâîßî�îZî‡î!øî'6 î/£î2bî6¹î8î; î? î@ìîBúîGáî ®ïHîÜî´îÎîîîxî"¤î%[ î, î-Ùî2kî59î7Ãî9´î?ZîAUîB~îEÄîG/î ®ïFrî—î/îÉî×î •î&î'ôî(ýî,!î0§î5ÿî7Œî8Áî;æî>%îAIîB”î ®ïDËîiîî Jî$î&:î+Ä î4%î7Éî:î>îC¨î ®ïC#î‘î~îÿî¥îNî~ î&™î,î/Aî3Aî5î9ãî>hî@ îEaî ®ïA|î«î�î6î§î* î$ î'µî+6î,™î-¹î/Âî1rî46î8àî:…î<Üî@qîBñîD�îFØî ®ï?Õîgî�îï î ®ï=KîÉî3îÆ î×î�î$Kî&´î+î,Çî.×î:Çî?! îG/î ®ï;¤îaîpîüîÜîî î ®ï9î:î‘îÖîBî´îî!žî#ñî'¼î,Yî.î0qî3îî6šî9Qî<¹î>}î@5îA_îDî ®ï7tî Ûîëî²î£î~î'î"Zî%î)î/¶î2pî7î;çî>>îD>îEûî ®ï5ÌîžîKî´î|îî$'î&œî+½î1 î2çî7›î;hî=ßîBfîC½îH#î ®ï4%î:îûî?îÏîä î&åî,Fî.Tî/‘î5ûî9«î<ÙîA0îDîF™îHeî ®ï2~îîJî‡ î¼î!]î"‡î%(î)5î*îî, î2Mî5Êî9Ìî;8î@›îBTî ®ï/ôîqî[îÏîaî¿î#}î(:î-|î1%î2±î4× î;zî@MîF·î ®ï.Mî/îÚî“î„îœî!î"-î(„î+Êî-6î/áî6î8ïî?DîAïîC[îD�î ®ï+Äî;îî‚î)î!î$(î&zî*Òî0Uî2ëî6Fî;õî=uîB0îEvî ®ï*îúîkîî+îØî"Uî$ÿî'µî*Ä î2¦î5\î:Éî>’î@å îGàî ®ï(u îõîçî‚î"Gî$î&$î*Wî-Øî/î4¤î8î9‰îFÉîGáî ®ï&ÎîîÔîî¿îîIî#¢î&oî+î0þî3hî8Ìî<Ùî>:î?dîC½î ®ï%&îòîøîWî$îæîŸî�î#ýî'Èî*î/î0¨î3î5¿î7xî;, î ®ï"�îîî×î+îqî#oî%�î&â î-Æî0î4¶î8�î:‡î=ÍîAV î ®ï@î×îG îæîöî!Ÿî&Eî) î+î1€ î:î;Œî=®îA«îCuîDèî ®ï™ îîî¥îî îìî!“ î'Ôî)‚î.î/Íî2nî4'î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îî,îî%%î*î1‚î6î7òî;0î?åîA  î ®ï`‚îœîèî™îÞîî–î)»î.cî19 î7—î9!î<Ó îCîFî ®ï^ÚîCîzî³ î1î"Éî$0î'hî*Õ î2’ î9î:kî@½îBfîDhîGÖî ®ï]3î îŠ îöîî"î(î,/ î2oî9î:‰î=Åî ®ïZ¥î«î^î†î�î#Eî&"î2-î4�î9Äî=´î?ˆî ®ïXþîÅîÈîHîî% î+Ãî-áî2î5…îFØî ®ïWWî¤î!\î+bî0pî2Ãî58 î;»pî ìïQjîkî=îÛî…î$Ú rî ®ïNîî1îFîœîÂî"õ î+èî-�î/tî3�î6Nî8©î>Ïî@zîBÕîFÁî ®ïL[î�î²î×îMîG î#‰î'¡î)î*Kî.Lî2!î5î67î9ªî<‚î=ø îE*îG/î ®ïJ´î&î9 î%î$î%Åî)Bî+1î0~î8Lî<þî@îC¨î ®ïI îôî¼îî!îàî%¶ î-Pî1Bî6[î9Dî=ÏîC¦î ®ïGe î- î!î$0î&î'Wî/Çî2¼î4Pî6Öî:õî>çîALîCÓî ®ïE¾î ®ïC0îKîï î$gî&¹î+¡î0¬î3Ûî6Oî9×î?#îBHîFØî ®ïA‰î»îBîîî5î ’î$î%Ïî(-î,Cî2˜î4‘î5¹î9kî;îA—îFãî ®ï?âîºî îîÙî‡î"$ î)Jî+ˆî,±î ®ï=TîÑî%îŽîÄîpî ½î#‰î$çî'‘î+›î-ìî0^î4tî7�î9†î;øîAóîDPîGËî ®ï;¬ îœîäîðqî/ßï;¬î0˜ï;¬î3=î6Dî8mî9Žî={ îCîFñî ®ï:îŠîgîCîDîŠîpî!wî%8î' rî,ï:î ®ï7wî$î�îÐî î6îõî£î"?î&Ûî(‰î+�î/5î1%î5=î6õî8 î>SîAÛîCFîEKî ®ï5Ð î×îoîùî£îFî�î#ºî&rî+%î,¼vî0ï5Ðî0Êï5Ðî5F rî�îD î ®ï$õî»îNî î~î>î�î#î%¯î(»î-£ î3Öî6—î8Ü î@yîEî ®ï#NîTî›î÷î—ît î!œî%8î*aî, î/É î7î8çî=`î@YîCõî ®ï ÀîÒîãî§î îUî!î')î)—î,tî.< î5áî;íî@°îC@îEvî ®ïîî8 î0îæî ¹î#Bî$‹î'6î-î1Iî3oî7õî;‡î>tîBîC î ®ïqîëî‘îèînî$²î)Qî-Åî1|î6îî9ê î@#îBéîF(î ®ïÊî^ îÑîŠî!2î'0î+‹î/@î ®ï<î¾îæîéî î%§î+.î-õî0˜î5oî:\î?uîB% î ®ï•îzîwîìîÓîªî%Öî*¸î-hî.íî3äî6sî:�î<ùî?öîANîF0îHeî ®ïîî¬îMîGîîÜî§ î'Üî-_î/ýî1áî7 î?|îC$îEwî ®ïFîHîºîîÅî� î&ªî)Äî/3î2Bî ®ï¹ð%î$¤î*¡î,8î/~î1šî6‚î9O îCÿî ®ï î ®ï ƒî î;îÝî 4î"ƒî$èî&‘î'ªî,òî/çî5”î7Á î?FîE4î ®ï ÜîqîºîKîfîîÕ î%xî)Dî.#î2¿î70î:åî@TîCN î ®ï 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)îºîîaîÂîyîgî!©î' î(»î+0î3—î5Eî7æî:¾î?½îAkpî ìï[Œî€îà î#Ñ î,"î.úî5 rî ®ïUÂî~î î!î"É î)Ðî,‡ î35î6î:¶î=îB6 î ®ïSGî¬îôîªîžî#( î+Âî2î>Ù îE‚î ®ïQ îî�îŠî#î©î"O î(ªî+| î1]î4[î:î=Qî?&îA« î ®ïOø î§îÕî© î ûî#Æî/|î4° î< îCîDÝî ®ïNQ î2î¬î¦îîMî .î$kî(Þî* î0Xî4î6ˆî<&î=ŸîBäîFÁî ®ïLªîmîÍîîýî î,�î0‡î3åî6/î;ªî>Aî@¬îFiî ®ïKî îáîŒî}î7î"~î$Þî*mî ®ïH‡îîVîzî î•î×î)Oî-­ î4iî7eî<Ìî?îA¾îCZ î ®ïFàîJî© î‚î 4î$ î'Êî ®ïDeîA îoîîÙîÃî$þ î-jî/^î1·î=TîDîG´î ®ïB¾î‹î’î îÂîhî ìî%oî(†î*Êî0vî2ºî8;î;“î>³î@sîBÃîFHî ®ïAîœî¨îQî@îÙî �î#Zî'Ôî*~î,mî2î3³î6÷î:1î<� îBÂîHî ®ï?oîOîÆîªî‡îî#eî%¡î)îî/¾î2Ëî5Ïî:íî>Tî?³ îFuî ®ï=ÈîNîÊî´îŠî®î!»î%¡î(uî-8î1Ñî6Šî9 î?™îB�îEÏî ®ï< î ®ï9¥îîRî1îéî3î#Hî'šî(¦ î.¼î1Äî7£î=5î?ÎîB î ®ï7þîNî î îåîÎî)öî/—î2Tî4Vî9©î;Sî>îA<îBüîHeî ®ï6WîQîÚî¢î¥ î$ë î,-î13 î7„î:L îAÇîFtî ®ï4¯îVîSî(îß î%òî(Qî.Oî2&î ®ï24ð%î$6î%¢î(î+Áî1gî3¤î8x î?&î@ßîC? uî)Èïö‡TVm$a TIMESROMANþŸ HELVETICAþŸLOGOü´LAURELþŸ TIMESROMANþŸ TIMESROMANþæ TIMESROMANþY¶ ' ÒZ!j/$"™éŒüÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿSafeStoragePrimer.tioga29-Oct-82 12:20:28