ToCSLDateAugust10,1984FromMikeKupferLocationPARCSubjectInternalstructureofAlpineLocksOrganizationCSLXEROXReleaseas[Indigo]Release52>Doc>LockInternals.pressCamefrom[Indigo]Release52>Doc>LockInternals.tiogaLasteditedbyKupfer,August11,19842:37:26pmPDTAbstractTheAlpineLockManagercontrolsacomplicatedwebofvariantrecords.ThismemodescribesthevariantrecordstructureandgivesanexampletakenfromarunningAlpineserver.Itmaybenecessarytoreadthememoonce,lookattheexample,andthenreadthememoagain.IntroductionTheAlpinefileservice,asdesigned,supportsatomictransactionsthatspanmultipleservers.Thisdocumentbrieflyexplainsthehigh-levelinterfacetoAlpinelocks,anditexplainsthecomplicateddatastructurethateachAlpineserver'sLockManagermaintains.LockinterfaceAlpinenamesalockwithaLockID(definedinAlpineInternal.mesa).Unlike,say,atransactionID,aLockIDalwaysreferstoexactlyoneobject,suchasafileorapage,evenacrosseventssuchasservercrashes.AclientoftheLockinterfaceissomeothermoduleinAlpine,actingonbehalfofatransaction.ThisclientmayrequestthatthelockmanagerSetalockinagivenmode.Ifthereisalreadyaconflictinglockset,theclientmayspecifywhetheritwishestowaituntilthelockisavailable,orwhetheritwishestobeinformedimmediatelythatsomeoneelsehasthelock.Alockmaybeheldbymorethanonetransaction,andatransactionmayholdmorethanonelock.Giventhelock,thetransactionmayReleaseitwhenitnolongerneedsit.Thetransactionmanageralsohasthepowertoabortatransactionandtakeallofitslocksaway,usuallysothatthelockscanbegiventoothertransactions.WhattheLockManagerneedsSupposeatransactionrequeststhelockMyLock.TheLockManagermustquicklyfindthislockinapotentiallylargejungleofotherlocks,determineifanyonep_/q_/8p_/-q_/27~9p[Sq[S8Zp[S-q[S89pWwq;WwWwr/$npWw- qWw89rOqsINetIN1sGBtG1sEwEtAEE4w"$(-0<sBtB,!'-/ 7\:< !u5u q2%*!H#6)/Y4 ;>0~f#'-X/ 6.;=.{5 &M)X/15&9>-/ v)jq&-t!w"&&#q&(#-/Q=5$ -S"o&*,K037;%<=@Z#CY"$F(Y./3[57;@!Nk7"2&\(,./ 8;=?Qnw",#q$& )'*,G056:m;@M X!$(-/;3558(;h=@ V"<$&,( 47<??!#'$*H, 4D68 ?Wx(t $w'(q,-1359@=?F4 !Y#(7* -/& 6J9)b@C_5y!%V')-/52 v= mq ] %w( w+7 ,q07 15 8> G  %Q(,.Z15< =VxTVm$CSLNotebookTopic2elsehasMyLock,anddeterminewhetherthetwotransactionscanbothhaveMyLockatthesametime.Ifthereisaconflictandtherequestingtransactionwishestowait,theLockManagermustplacetherequestinaqueue,waitingforthelock'seventualavailability.Supposethatatransactioncompletes(eithercommitsoraborts).TheLockManagermustfindallofthelocksownedbythetransactionandfreethem.Ifanothertransactioniswaitingforoneoftheselocks,theLockManagershouldgivethelocktothissecondtransaction.Finally,considerthemaintenanceworkthattheLockManagermustdo.Itshouldbeabletodetectacircularchainofrequests(deadlock),anditshouldbeabletoscanwaitingrequeststofindcasesoflivelock(akastarvation).Itshouldbeabletoperformthesetasksquicklyandwithlittleoverhead,sothatproblemsarecorrectedquicklyandwithlittleperformanceloss.TheSolutionTheAlpineLockManagerusesasingledatastructuretomeetthesevariedneeds.Thisdatastructureconsistsofmanyvariantrecords,allofwhicharetiedtogetherbyassortedREFlinksintocircularandsimplesingly-linkedlists.LockInternal.ObjectThevariantrecordthattheAlpineLockManagerusesisdefinedinLockInternal.mesa.ALockObjectalwayscontainsarequestListREFandabodyrecord.ThetwomainvariantsofaLockObject--requestandheader--aredistinguishedbyvaryingthebody.Weshallrefertothesetwovariantsas"requestobjects"and"headerobjects,"respectively.TherequestListREFlinksobjectsassociatedwithonelockintoacircularlist,aswewillexplainbelow.HeaderObjectRecallthatanAlpineLockIDuniquelyidentifiesoneobjectthatistobelocked(eg.,apageorafile).Whenatransactionrequestsalock,theLockManagerentersarequestobjectforthetransactiononacircularlistassociatedwiththedesiredLockID.ThiscircularlististiedtogetherwiththerequestListREF,asstatedabove.Aheaderobjectalsositsinthecircularlist,anditidentifieswhichlockisbeingrequested.TheLockManagerreferstoheaderobjectsviaahashtable,usingthelockIDasthehashkey.Thenextfieldisusedbythehashpackagetoconnectheaderobjectsthathashtothesamelocation.RequestObjectArequestobjectalwayscontainsatransactionhandle,atransListREF,andmodeinformation.Thetransactionhandletellswhattransactiontherequestobjectisassociatedwith.WewilldescribethetransListREFbelow.Themodetellswhatlockingmodehasbeenrequested.Therestofarequestobjectisyetanothervariantrecord,consistingofeitheragranted,awaiting,oratransHeadervariant.uf"&o.tfEq_,zw_,_,%q_,&"'), 36U9rw<_,_,=q]l- _!{&W)+R 1 8=,>[5^!@#(Z)+/4N6~8<Z6 WZY ")}.35;>Vbyt!%*<,a. 68;@Tl O!!#]&'+E/1w4:?0RA: PIw ',*-0O39=s@N{l$(*0 7K: ;@-Li "o%\(*/2 :<;@-KS* A%8(+;.469?Iw" *vF]qC a#&,'+.46:7=Af / %$&*/468<?[?FAp??bq?Y!$)w,/0 8u9!q5O:"%*.598:@p4*;w 4*4*!q%U4*4*%)/hw04*4*1; p4*7q4*:=w>4*4*?q2r#%'J+/w1222 q26kw9j22:&q> 22>?0 >9! $'a*-/3!5:</4## ,/N p6/4/47q/49=- Ni "')+I-p04v*>q&ew&&q&#) /2"6(8:>;=%G7 ! (.'/F248U>#=B %')H.n0 7y:=U! v#3(+. p5 !!5q7S!!8*9= Q<wg #=(U+-/b 5w9<>S .!#(,/0>37T; w=v..=qBlwm,q $%)+%-168W=M8!v#qA 2%w&AA' -|q1VAA2w34AA3pA8q;AA;w>AA?q  "&)-~ 47O<_@ lD $' p,-q/47;> Ki $&)j+,*046P8=  w !_q% %w' 'q+Q ,--w/ / q 6TVm$CSLNotebookTopic3waitingvariantWhenatransactionmustwaitforalock,theLockManagercreatesa"waiting"variantforthetransaction.Allofthe"waiting"requestobjectsaretiedinasingly-linked,non-circularlistthroughthetransListREF.Thislistisused,forexample,bytheLockWatchdogtofindlockrequeststhathavetimedout.grantedvariantWhentheLockManagergrantsarequest,itmakesa"granted"variantforthetransaction.Thisobjectsitsinacicularlistcontainingallgrantedrequestsforthetransaction.ThelistitselfisboundtogetherviathetransListREF.transHeadervariantInadditiontothetransaction'sgrantedrequests,thetransList-threadedcircularlistcontainsatransHeader.Thisobjectidentifiesthetransactionandcontainsacountofthe(granted)requestobjectsinthelist.AnExampleTheaccompanyingdiagram(filedin[Indigo]Release52>Doc>LockExample.griffin)wasderivedbytracingpointersonarunningAlpineserver(Monitor.alpine).Itshowsthelockobjectsfortwotransactions,numbers402and1002.Therearefourlocksinvolved,asshownbythefourheaderobjects:A,B,C,andD.ThetransactionsAtransaction'slocksareassociatedwithitsworker(s),so"self,"intheupperleftcorner,isaWorker.Handlefortransaction402.Itpointstothecircularlistofallthelocksthat402hasbeengranted.BecausetherequestListREFispresentinallLockobjectsbutdoesn'thaveausefulfunctioninatransHeader,itisNILinthetransHeader.ThetransHeaderfor1002isatthebottomofthediagram,inthemiddle.Transaction402hasbeengrantedallfourlocks(A,B,C,andD).Transaction1002hasbeengrantedonelock(D),andiswaitingforanother(C).Transaction1002iswaitingbecauseitisrequestingamodethatisincompatiblewiththemodethat402haslockedCwith.ThelocksLockAhasbeengrantedtoonetransaction(402).Itistheonlylockinitshashbucket,soits"next"fieldisNIL.LockBhasbeengrantedto402.B'sandC'slockID'shashtothesamevalue,soBislinkedtoCvia"next".LockChasbeengrantedto402,and1002iswaitingforit.The"waiting"requestobjectfor1002isthelastoneintheLockManager'slistofwaitingobjects.uf"&o.tfEw_:q[ !*$&R't*-06H:;ZCT !p$&(/A4b9K;>@X  "('*Mp09XX1 q2XX4m7:S<?V#$'*026: wSqPV!^%v&+-"1Z28=?N  "D#z'*A 138=u?M , $*V,.p4MM5lq6MMwI qFir $)/t1=)DK0 !&$l( .1Z 8;e@Cr!&6'*Cu<|q9- *v6J@p7204:=507b!!%.0b158I;C?47 _ !$R(,/;2<5;=2=A!#%a(v/@ q+M A!K '+ - 35u9;>*Jbw*J*J" q*J"l$ +/E0469>@e(Rc"U(Q-0 p75((8 q(:;@p&CU #M$p(-/0 8:'p;&&?%T  "%=(*I,.35y8=?#!1 %!&(u+z.1W347: DOk 3#I&S)'*/17 : /{ s ')(Y,6/ 0~ 8;>H;F vqA"!#& -2}458!;\>u@C"2p#$q%z!^!^# &~(+~-3U68?:>}e$ WI"<$''*-t/46h8; L!#&='*G-4d68W=)`TVm$CSLNotebookTopic4LockDhasbeengrantedtoboth402and1002.uf"&o.tfEq_/!9!#E&)+5TVm$. TIMESROMAN TIMESROMAN TIMESROMANY HELVETICA HELVETICALOGO TIMESROMAN TIMESROMAN j/EDl.[]<>users>kupfer.pa>Alpine>LockInternals.tioga%Saturday, August 11, 1984 3:00 pm PDT