<> <> <> <<>> <> <<>> 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; }; <> <> <> <> < Camelot.LockModeRead,>> < Camelot.LockModeWrite,>> < ERROR;>> <> <> <<}>> << ELSE {>> <> <<};>> <<};>> <<>> <> 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]; }; <> <> <> <> <> <> <> <> <> <> <> <> <> <> << ELSE prevDocLock.nextDocLock _ 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.