DIRECTORY Basics USING [BITXOR], Camelot USING [segmentIdT], Mach USING [vmOffsetT], PBasics USING [BITXOR], Process USING [ InitializeCondition, MsecToTicks], YggDID USING [DID], YggDIDPrivate USING [DIDRep], YggEnvironment USING [LockFailure, TransID], YggLock USING [ErrorType, LockID, LockMode, nullLockID], YggTransaction USING [EqualTrans]; YggLockImpl: CEDAR MONITOR IMPORTS Basics, PBasics, Process, YggTransaction EXPORTS YggDID, YggLock ~ BEGIN DID: PUBLIC TYPE ~ REF DIDRep; DIDRep: PUBLIC TYPE ~ YggDIDPrivate.DIDRep; Error: PUBLIC ERROR [type: YggLock.ErrorType] = CODE; Failed: PUBLIC ERROR [why: YggEnvironment.LockFailure] = CODE; DocLock: TYPE = REF DocLockRep; DocLockRep: TYPE = RECORD [ lockID: YggLock.LockID _ YggLock.nullLockID, trans: YggEnvironment.TransID, mode: YggLock.LockMode, grantedCount: INT _ 0, nextTransLock: DocLock _ NIL, -- link field all transaction locks nextDocLock: DocLock _ NIL, -- link field for lock hash table (different lock hashing to same slot) nextTransWaiting: DocLock _ NIL -- link field for lock hash table (same lock but different trans) ]; lookupDocLock: DocLock _ NIL; -- for the "package's" use only. lockCondition: CONDITION; TransItem: TYPE = REF TransItemRep; TransItemRep: TYPE = RECORD [ trans: YggEnvironment.TransID, nextTrans: TransItem _ NIL, firstTransLock: DocLock _ NIL ]; MakeLockID: PUBLIC PROC [did: DID] RETURNS [lock: YggLock.LockID] ~ { segmentId: Camelot.segmentIdT; offset: Mach.vmOffsetT; segmentId _ [did.didHigh]; offset _ did.didLow; RETURN[[did: did, subEntity: [segmentId, offset]]]; }; Set: PUBLIC ENTRY PROC [trans: YggEnvironment.TransID, lock: YggLock.LockID, mode: YggLock.LockMode, wait: BOOL _ FALSE] RETURNS [granted: BOOL _ FALSE]~ { lookupAndInsertLock: DocLockRep; lookupAndInsertRef: DocLock _ NIL; lookupAndInsertLock.lockID _ lock; lookupAndInsertLock.trans _ trans; lookupAndInsertLock.mode _ mode; lookupAndInsertRef _ LookupAndInsert[lookupAndInsertLock]; granted _ tryToGrant[lookupAndInsertRef, wait]; }; Release: PUBLIC ENTRY PROC [trans: YggEnvironment.TransID, lock: YggLock.LockID, mode: YggLock.LockMode] RETURNS [released: BOOL _ FALSE] ~ { docLock: DocLock _ NIL; docLock _ Lookup[lock, trans, mode]; IF docLock = NIL THEN RETURN [FALSE]; IF (docLock.grantedCount _ docLock.grantedCount - 1) = 0 THEN Delete[docLock]; RETURN [TRUE]; }; ReleaseTransactionLocks: PUBLIC ENTRY PROC [trans: YggEnvironment.TransID, directoryOnly: BOOL] RETURNS [numberReleased: INT _ 0] ~ { foundTI: TransItem _ NIL; foundTI _ LookkupAndDeleteForTrans[trans]; IF foundTI # NIL THEN { FOR dl: DocLock _ foundTI.firstTransLock, dl.nextTransLock UNTIL dl = NIL DO Delete[dl]; ENDLOOP; }; }; tryToGrant: INTERNAL PROC [lookupAndInsertRef: DocLock, wait: BOOL _ FALSE] RETURNS [granted: BOOL _ FALSE] ~ { IF lookupAndInsertRef.grantedCount > 0 THEN { -- already granted lookupAndInsertRef.grantedCount _ lookupAndInsertRef.grantedCount + 1; RETURN [TRUE]; }; SELECT lookupAndInsertRef.mode FROM read => { DO FOR dl: DocLock _ lookupAndInsertRef.nextTransWaiting, dl.nextTransWaiting UNTIL dl = NIL DO IF dl.mode = write THEN EXIT; REPEAT FINISHED => { -- no conflicting writes lookupAndInsertRef.grantedCount _ lookupAndInsertRef.grantedCount + 1; RETURN [TRUE]; }; ENDLOOP; IF ~wait THEN { Delete[lookupAndInsertRef]; RETURN [FALSE]; }; WAIT lockCondition; ENDLOOP; }; write => { DO FOR dl: DocLock _ lookupAndInsertRef.nextTransWaiting, dl.nextTransWaiting UNTIL dl = NIL DO IF dl.mode = write OR dl.mode = read THEN EXIT; REPEAT FINISHED => { -- no conflicting write's or read's, so grant lookupAndInsertRef.grantedCount _ lookupAndInsertRef.grantedCount + 1; RETURN [TRUE]; }; ENDLOOP; IF ~wait THEN { Delete[lookupAndInsertRef]; RETURN [FALSE]; }; WAIT lockCondition; ENDLOOP; }; directoryRead => { DO FOR dl: DocLock _ lookupAndInsertRef.nextTransWaiting, dl.nextTransWaiting UNTIL dl = NIL DO IF dl.mode = directoryWrite THEN EXIT; REPEAT FINISHED => { -- no conflicting directoryWrite's lookupAndInsertRef.grantedCount _ lookupAndInsertRef.grantedCount + 1; RETURN [TRUE]; }; ENDLOOP; IF ~wait THEN { Delete[lookupAndInsertRef]; RETURN [FALSE]; }; WAIT lockCondition; ENDLOOP; }; directoryWrite => { DO FOR dl: DocLock _ lookupAndInsertRef.nextTransWaiting, dl.nextTransWaiting UNTIL dl = NIL DO IF dl.mode = directoryWrite OR dl.mode = directoryRead THEN EXIT; REPEAT FINISHED => { -- no conflicting directoryWrite's or directoryRead's, so grant lookupAndInsertRef.grantedCount _ lookupAndInsertRef.grantedCount + 1; RETURN [TRUE]; }; ENDLOOP; IF ~wait THEN { Delete[lookupAndInsertRef]; RETURN [FALSE]; }; WAIT lockCondition; ENDLOOP; }; ENDCASE => ERROR; }; PrimeTable: ARRAY PrimeTableIndex OF NAT _ [37, 67, 131, 257, 513, 1031, 2003]; PrimeTableIndex: TYPE = [0 .. 6]; hashSlots: REF HashSlots _ NIL; HashSlots: TYPE = RECORD[SEQUENCE nSlots: NAT OF DocLock]; numHashSlots: NAT _ 0; hashTrans: REF HashTrans _ NIL; HashTrans: TYPE = RECORD[SEQUENCE nSlots: NAT OF TransItem]; HashPkgDuplicateKey: ERROR = CODE; -- from Insert. HashPkgCallerProgrammingError: ERROR = CODE; -- from Delete. ClientHashInit: PROC [numHashSlotsDesired: NAT] RETURNS [numHashSlotsAllowed: NAT] = { FOR i: PrimeTableIndex IN PrimeTableIndex DO IF PrimeTable[i] >= numHashSlotsDesired THEN RETURN [PrimeTable[i]]; ENDLOOP; RETURN [PrimeTable[PrimeTableIndex.LAST]]; }; ClientHash: INTERNAL PROC [lockRep: DocLockRep] RETURNS [NAT--[0..numHashSlots)--] = INLINE { RETURN [ PBasics.BITXOR[ LOOPHOLE[lockRep.lockID.did.didHigh, CARD32], LOOPHOLE[lockRep.lockID.did.didLow, CARD32]] MOD numHashSlots]; }; TransHash: INTERNAL PROC [trans: YggEnvironment.TransID] RETURNS [NAT--[0..numHashSlots)--] = INLINE { rb: WORD _ trans.top.randomBits; high: WORD _ trans.top.highTicker; low: WORD _ trans.top.lowTicker; RETURN [Basics.BITXOR[Basics.BITXOR[rb, high], low] MOD numHashSlots]; }; ClientEqualKeys: INTERNAL PROC [docLock1: DocLock, docLock2: DocLockRep] RETURNS [equal: BOOL] = INLINE { RETURN [ docLock1.lockID.did.didHigh = docLock2.lockID.did.didHigh AND docLock1.lockID.did.didLow = docLock2.lockID.did.didLow]; }; LookupAndInsert: INTERNAL PROC [lookupAndInsertLock: DocLockRep] RETURNS [ndl: DocLock _ NIL] = INLINE { index: NAT _ ClientHash[lookupAndInsertLock]; prevDocLock: DocLock _ NIL; FOR newDocLock: DocLock _ hashSlots[index], newDocLock.nextDocLock UNTIL newDocLock = NIL DO IF ClientEqualKeys[newDocLock, lookupAndInsertLock] THEN { dl: DocLock; FOR dl _ newDocLock, dl.nextTransWaiting UNTIL dl = NIL DO IF YggTransaction.EqualTrans[lookupAndInsertLock.trans, dl.trans] THEN { SELECT lookupAndInsertLock.mode FROM read => IF dl.mode = write OR dl.mode = read THEN RETURN [dl]; write => IF dl.mode = write THEN RETURN [dl]; directoryRead => IF dl.mode = directoryWrite OR dl.mode = directoryRead THEN RETURN [dl]; directoryWrite => IF dl.mode = directoryWrite THEN RETURN [dl]; ENDCASE => ERROR; }; ENDLOOP; lookupAndInsertLock.nextDocLock _ newDocLock.nextDocLock; newDocLock.nextDocLock _ NIL; ndl _ NEW[DocLockRep]; ndl^ _ lookupAndInsertLock; IF prevDocLock = NIL THEN hashSlots[index] _ ndl ELSE prevDocLock.nextDocLock _ ndl; InsertForTrans[ndl]; RETURN [ndl]; }; prevDocLock _ newDocLock; ENDLOOP; lookupAndInsertLock.nextDocLock _ hashSlots[index]; ndl _ NEW[DocLockRep]; ndl^ _ lookupAndInsertLock; hashSlots[index] _ ndl; InsertForTrans[ndl]; RETURN [ndl]; }; Lookup: INTERNAL PROCEDURE [lockID: YggLock.LockID, trans: YggEnvironment.TransID, mode: YggLock.LockMode] RETURNS [docLock: DocLock] = -- INLINE -- { -- returns docLock = NIL if not found. lookupDocLock.lockID _ lockID; FOR docLock _ hashSlots[ClientHash[lookupDocLock^]], docLock.nextDocLock UNTIL docLock = NIL DO IF ClientEqualKeys[docLock, lookupDocLock^] THEN { dl: DocLock; FOR dl _ docLock, dl.nextTransWaiting UNTIL dl = NIL DO IF YggTransaction.EqualTrans[trans, dl.trans] AND mode = dl.mode THEN RETURN [dl]; ENDLOOP; IF mode = directoryRead THEN { FOR dl _ docLock, dl.nextTransWaiting UNTIL dl = NIL DO IF YggTransaction.EqualTrans[trans, dl.trans] AND dl.mode = directoryWrite THEN RETURN [dl]; ENDLOOP; }; IF mode = read THEN { FOR dl _ docLock, dl.nextTransWaiting UNTIL dl = NIL DO IF YggTransaction.EqualTrans[trans, dl.trans] AND dl.mode = write THEN RETURN [dl]; ENDLOOP; }; }; ENDLOOP; RETURN[NIL]; }; Delete: INTERNAL PROCEDURE[docLock: DocLock] = INLINE { index: NAT _ 0; prevDocLock: DocLock _ NIL; topDocLock: DocLock _ NIL; FOR topDocLock _ hashSlots[index _ ClientHash[docLock^]], topDocLock.nextDocLock UNTIL topDocLock = NIL DO IF ClientEqualKeys[topDocLock, docLock^] THEN EXIT; prevDocLock _ topDocLock; REPEAT FINISHED => ERROR HashPkgCallerProgrammingError; ENDLOOP; IF YggTransaction.EqualTrans[topDocLock.trans, docLock.trans] AND topDocLock.mode = docLock.mode THEN { -- found at front of list for DID IF topDocLock.nextTransWaiting = NIL THEN { -- list now will be empty IF prevDocLock = NIL THEN hashSlots[index] _ docLock.nextDocLock ELSE prevDocLock.nextDocLock _ docLock.nextDocLock; } ELSE { -- list still has stuff in it docLock.nextTransWaiting.nextDocLock _ docLock.nextDocLock; IF prevDocLock = NIL THEN hashSlots[index] _ docLock.nextTransWaiting ELSE prevDocLock.nextDocLock _ docLock.nextDocLock; }; }; docLock.nextDocLock _ NIL; docLock.nextTransWaiting _ NIL; docLock.nextTransLock _ NIL; BROADCAST lockCondition; }; InsertForTrans: INTERNAL PROC [ndl: DocLock] = INLINE { index: NAT _ TransHash[ndl.trans]; FOR ti: TransItem _ hashTrans[index], ti.nextTrans UNTIL ti = NIL DO IF YggTransaction.EqualTrans[ndl.trans, ti.trans] THEN { ndl.nextTransLock _ ti.firstTransLock; ti.firstTransLock _ ndl; EXIT; }; REPEAT FINISHED => { newTI: TransItem; newTI _ NEW[TransItemRep]; newTI.trans _ ndl.trans; newTI.firstTransLock _ ndl; newTI.nextTrans _ hashTrans[index]; hashTrans[index] _ newTI; }; ENDLOOP; }; LookkupAndDeleteForTrans: INTERNAL PROC [trans: YggEnvironment.TransID] RETURNS [foundTI: TransItem _ NIL]= INLINE { index: NAT _ TransHash[trans]; prevTransItem: TransItem _ NIL; FOR ti: TransItem _ hashTrans[index], ti.nextTrans UNTIL ti = NIL DO IF YggTransaction.EqualTrans[trans, ti.trans] THEN { foundTI _ ti; IF prevTransItem = NIL THEN hashTrans[index] _ ti.nextTrans ELSE prevTransItem.nextTrans _ ti.nextTrans; EXIT; }; prevTransItem _ ti; ENDLOOP; }; InitializeHashTable: PROCEDURE[numHashSlotsDesired: NAT] = { numHashSlots _ ClientHashInit[numHashSlotsDesired]; hashSlots _ NEW[HashSlots[numHashSlots]]; hashTrans _ NEW[HashTrans[numHashSlots]]; FOR index: NAT IN [0..numHashSlots) DO hashSlots[index] _ NIL; hashTrans[index] _ NIL; ENDLOOP; lookupDocLock _ NEW[DocLockRep]; }; InitializeHashTable[257]; TRUSTED {Process.InitializeCondition[@lockCondition, Process.MsecToTicks[157]]; }; END. ϊYggLockImpl.mesa Copyright Σ 1988 by Xerox Corporation. All rights reserved. Bob Hagmann January 6, 1989 1:23:08 pm PST Handle all operations on Locks. Locks are kept in a table (hashSlots). To find a lock, the DID is hashed and the bucket is interogated. Chaining along the nextDocLock field, succesive items are examined for the right DID. Once found, nextTransWaiting is the chain for the lock. The chain is then examined to find a matching tid. Read requests match either read or write locks, while write requests only match wirte locks. If none is found, a new DocLock is added to the front of the nextTransWaiting chain. If the DID is not found, it is added to the chain (it so happens that it is added at the beginning, but this is not important.) To grant a lock, all the locks after it on the nextTransWaiting chain must be compatible. That is, to grant a read lock all the outstanding locks must be read and no write lock request is after the grant node in the chain (after on the chain f requested before). And to grant a write request, it has to be on the end of the chain (hence the oldest remaining request). Exported procedures Construct the lock identifier for the did Acquires lock, in lock mode mode, for transaction trans. Acquires lock, in lock mode mode, for transaction trans. Set: PUBLIC PROC [trans: YggEnvironment.TransID, lock: YggLock.LockID, mode: YggLock.LockMode, wait: BOOL _ FALSE] ~ { Acquires lock, in lock mode mode, for transaction trans. lockMode: Camelot.lockModeT; lockMode _ SELECT mode FROM read => Camelot.LockModeRead, write => Camelot.LockModeWrite, ENDCASE => ERROR; IF wait THEN { Camelot.Lock[tid: trans, lockName: lock.subEntity, lockMode: lockMode]; } ELSE { Camelot.TryLock[tid: trans, lockName: lock.subEntity, lockMode: lockMode]; }; }; Access to the hash table this proc is commented since it may not work and is not needed Insert: INTERNAL PROCEDURE[lookup: DocLockRep] RETURNS [ndl: DocLock _ NIL] = INLINE { -- errors: HashPkgDuplicateKey. index: NAT _ ClientHash[lookup]; FOR newDocLock: DocLock _ hashSlots[index], newDocLock.nextDocLock UNTIL newDocLock = NIL DO IF ClientEqualKeys[newDocLock, lookup] THEN { dl: DocLock; FOR dl _ newDocLock, dl.nextTransWaiting UNTIL dl = NIL DO IF YggTransaction.EqualTrans[lookupAndInsertLock.trans, dl.trans] AND lookupAndInsertLock.mode = dl.mode THEN RETURN [dl]; ENDLOOP; lookupAndInsertLock.nextDocLock _ newDocLock.nextDocLock; newDocLock.nextDocLock _ NIL; ndl _ NEW[DocLockRep]; ndl^ _ lookupAndInsertLock; IF prevDocLock = NIL THEN hashSlots[index] _ ndl ELSE prevDocLock.nextDocLock _ ndl; RETURN [ndl]; ERROR HashPkgDuplicateKey; ENDLOOP; lookup.nextDocLock _ hashSlots[index]; ndl _ NEW[DocLockRep]; ndl^ _ lookup; hashSlots[index] _ ndl; RETURN [ndl]; }; Initialization ΚQ˜code•Mark outsideHeaderšœ™Kšœ<™J˜Jšœ œœ ˜šœ œœ˜Jšœ,˜,Jšœ˜Jšœ˜Jšœœœ˜KšœœΟc#˜AKšœœ’G˜cKšœœ’A˜aK˜—Kšœœ’ ˜>Kšœ œ˜K˜Kšœ œœ˜#šœœœ˜Jšœ˜Kšœ˜Kšœ˜K˜——headšœ™š Οn œœœœœ˜EJ™)Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ-˜3J˜—J˜š£œœœœUœœœ œœ˜›Jšœ8™8Kšœ ˜ Kšœœ˜"Jšœ"˜"Jšœ"˜"Jšœ ˜ Jšœ:˜:Jšœ/˜/Jšœ˜J˜—š £œœ œOœ œœ˜Jšœœ˜Jšœ$˜$Jš œ œœœœ˜%Jšœ7œ˜NJšœœ˜J˜J˜—š £œœ œ0œœœ ˜…Jšœœ˜Jšœ*˜*šœ ˜šœ8œœ˜LJšœ ˜ Jšœ˜—J˜—J˜J˜—šΟb œœœ%œœœ œœ˜oJšœ8™8šœ%œ’˜AJšœF˜FJšœœ˜J˜—šœ˜#šœ ˜ š˜šœHœœ˜\Kšœœœ˜šœœ’˜.KšœF˜FKšœœ˜Kšœ˜—Kšœ˜—šœœ˜Jšœ˜Jšœœ˜J˜—Jšœ˜Jšœ˜—J˜—šœ ˜ š˜šœHœœ˜\Kšœœœœ˜/š œœ’œ’œ’ ˜CKšœF˜FKšœœ˜Kšœ˜—Kšœ˜—šœœ˜Jšœ˜Jšœœ˜J˜—Jšœ˜Jšœ˜—J˜—šœ˜š˜šœHœœ˜\Kšœœœ˜&šœœ’"˜8KšœF˜FKšœœ˜Kšœ˜—Kšœ˜—šœœ˜Jšœ˜Jšœœ˜J˜—Jšœ˜Jšœ˜—J˜—šœ˜š˜šœHœœ˜\Kšœœœœ˜Ašœœ’?˜UKšœF˜FKšœœ˜Kšœ˜—Kšœ˜—šœœ˜Jšœ˜Jšœœ˜J˜—Jšœ˜Jšœ˜—J˜—Jšœœ˜—Jšœ˜J˜—š £œœœUœœ™vJšœ8™8Jšœ™šœ œ™Jšœ™Jšœ™Jšœœ™—šœœ™JšœG™GJ™—šœœ™JšœJ™JJ™—Jšœ™J™——™K˜Kšœ œœœ'˜OKšœœ ˜!K˜Kšœ œ œ˜Kš œ œœœ œœ ˜:K˜Kšœœ˜K˜Kšœ œ œ˜Kš œ œœœ œœ ˜Kšœ œœœ˜-Kšœœ5 œ˜YKšœœ œ˜?Kšœœ˜—K˜—Kšœ˜—Kšœ:˜:Kšœœ˜Kšœœ ˜Kšœ˜Kšœœœ˜0Kšœœ˜$K˜Kšœ˜ K˜—Kšœ˜Kšœ˜ —Kšœ4˜4Kšœœ ˜Kšœ˜Kšœ˜K˜Kšœ˜ K˜K˜K™>—š £œœ œœœœ’™wKšœœ™ šœ?œ™\šœ$œ™-Kšœ ™ šœ&œœ™:Kšœ@œ$œœ™zKšœ™—Kšœ:™:Kšœœ™Kšœœ ™Kšœ™Kšœœœ™0Kšœœ™$Kšœ™ Kšœ™—Kšœ™ —Kšœ'™'Kšœœ ™Kšœ™Kšœ™Kšœ™ Kšœ™K™K™—š £œœ œPœ œ’ œ’˜ΎKšœ˜šœEœ ˜_šœ*œ˜2Kšœ ˜ šœ#œœ˜7Kšœ,œœœ˜RKšœ˜—šœœ˜šœ#œœ˜7Kšœ,œœœ˜\Kšœ˜—K˜—šœ œ˜šœ#œœ˜7Kšœ,œœœ˜SKšœ˜—K˜—K˜—Kšœ˜ —Kšœœ˜ Kšœ˜K˜K˜—š£œœ œ˜7Kšœœ˜Kšœœ˜Kšœœ˜šœMœ˜jKšœ'œœ˜3Kšœ˜Kšœœœ˜7Kšœ˜—šœ<œ œ’!˜‰šœœœ’˜EKšœœœ'˜@Kšœœ/˜4K˜—šœœ’˜&Kšœ;˜;Kšœœœ,˜EKšœœ/˜4K˜—K˜—Kšœœ˜Kšœœ˜Kšœœ˜Kš œ˜Kšœ˜K˜—š£œœœœ˜7Kšœœ˜"šœ0œœ˜Dšœ0œ˜8Kšœ&˜&Kšœ˜Kšœ˜K˜—šœœ˜Kšœ˜Kšœœ˜Kšœ˜Kšœ˜Kšœ#˜#Kšœ˜K˜—Kšœ˜—K˜K˜—š£œœœEœ˜tKšœœ˜Kšœœ˜šœ0œœ˜Dšœ,œ˜4Kšœ ˜ Kšœœœ ˜;Kšœœ(˜-Kšœ˜K˜—Kšœ˜Kšœ˜—K˜K˜—K˜—™š£œ œœ˜