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.
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
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 é requested before). And to grant a write request, it has to be on the end of the chain (hence the oldest remaining request).
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
];
Exported procedures
MakeLockID: PUBLIC PROC [did: DID] RETURNS [lock: YggLock.LockID] ~ {
Construct the lock identifier for the did
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]~ {
Acquires lock, in lock mode mode, for transaction trans.
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] ~ {
Acquires lock, in lock mode mode, for transaction trans.
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;
};
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
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];
};
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];
};
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;
};
Initialization
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.