YggCoordinatorTransIDImpl.mesa
Transaction ID generator.
Copyright Ó 1984, 1988 by Xerox Corporation. All rights reserved.
Last edited by
MBrown on November 3, 1982 3:29 pm
Kupfer, August 5, 1984 4:59:49 pm PDT
Bob Hagmann April 22, 1988 9:30:29 am PDT
Carl Hauser, October 4, 1985 1:26:32 pm PDT
NOTES:
(1) random bits in TransID should be more unpredictable; someone who sees enough consecutive TransIDs should not be able to guess the next one, even knowing the TransID generation algorithm.
(2) need to implement controlled shutdown (and restart) of TransID generator? Note that the value of maxSeqNumsIssuedWithoutForce may only be decreased after a controlled shutdown (not after a crash); increasing it is always OK.
DIRECTORY
YggEnvironment,
YggInternal,
YggConcreteTransID,
Convert USING [RopeFromInt],
YggCoordinator,
YggCoordinatorInternal USING [],
YggCoordinatorMap USING [GetHandle],
YggLog,
Rope USING [Cat, ROPE],
YggMonitoringHooks;
YggCoordinatorTransIDImpl:
CEDAR MONITOR
IMPORTS
Convert,
YggCoordinatorMap,
YggLog,
Rope
EXPORTS
YggEnvironment,
YggInternal,
YggCoordinatorInternal,
YggMonitoringHooks =
BEGIN
VolumeID: TYPE = YggEnvironment.VolumeID;
TransID:
PUBLIC
TYPE = YggConcreteTransID.TransID;
YggEnvironment.TransID.
CoordinatorObject:
PUBLIC
TYPE = YggCoordinator.Object;
YggInternal.CoordinatorObject.
YES: BOOL ← TRUE;
myFileStoreID: VolumeID;
randomSeed: INT ← 0;
lastSeqNum:
INT ←
INT.
FIRST;
The largest transaction sequence number ever issued.
nSeqNumsIssuedSinceForce: INT [0 .. maxSeqNumsIssuedWithoutForce];
maxSeqNumsIssuedWithoutForce: INT = 8;
nextForceLogRecordID: YggLog.RecordID;
NoticeCoordinatorBegin:
PUBLIC
PROC [trans: TransID] = {
lastSeqNum ← MAX [trans.idOnFileStore, lastSeqNum];
randomSeed ← trans.randomBits;
};
InitTransIDGenerator:
PUBLIC
ENTRY
PROC [fileStore: VolumeID] = {
myFileStoreID ← fileStore;
lastSeqNum ← lastSeqNum + (2*maxSeqNumsIssuedWithoutForce - 1);
nSeqNumsIssuedSinceForce ← 0;
nextForceLogRecordID will be initialized on first call to NextTransID, since nSeqNumsIssuedSinceForce = 0.
InitRandom[randomSeed];
};
NextTransID:
PUBLIC
ENTRY
PROC [c: YggCoordinator.Handle] = {
IF nSeqNumsIssuedSinceForce = maxSeqNumsIssuedWithoutForce
THEN {
YggLog.Force[followingRecord: nextForceLogRecordID];
nSeqNumsIssuedSinceForce ← 0 };
c.transID ← TransID[
fileStore: myFileStoreID,
idOnFileStore: (lastSeqNum ← lastSeqNum + 1),
randomBits: Random[]];
[thisRecord: c.beginRecord, followingRecord: c.forceRecord] ← YggLog.CoordinatorWrite[c, coordinatorBegin, YggLog.nullBlock];
IF nSeqNumsIssuedSinceForce = 0 THEN nextForceLogRecordID ← c.forceRecord;
nSeqNumsIssuedSinceForce ← nSeqNumsIssuedSinceForce + 1;
};
TransIDToRope:
PUBLIC
SAFE
PROC [transID: YggEnvironment.TransID, includeRName:
BOOL ←
YES]
RETURNS [Rope.
ROPE] ~
CHECKED {
YggMonitoringHooks.TransIDToRope. Returns a string which identifies the transaction. If "includeRName," the string includes the RName owning the transaction.
trueTransID: YggConcreteTransID.TransID ← LOOPHOLE[transID];
temp: Rope.ROPE ← Convert.RopeFromInt[trueTransID.idOnFileStore];
IF includeRName
THEN {
c: YggCoordinator.Handle;
TRUSTED {c ← YggCoordinatorMap.GetHandle[transID]};
SELECT c
FROM
NIL =>
IF transID = YggEnvironment.nullTransID
THEN
temp ← temp.Cat[" (null)"]
ELSE
temp ← temp.Cat[" (deleted)"];
ENDCASE =>
temp ← temp.Cat[" (", c.extras.userRName, ")"];
};
RETURN [temp];
};
Additive random number generator using the recurrence y(n) = y(n-55) - y(n-24).
See Knuth Algorithm 3.2.2 A (Volume 2, second edition, p.27.)
y: ARRAY [0..55] OF INT; -- y[0] included to improve the compiled code.
j, k: INTEGER [0..55];
Random:
INTERNAL
PROC []
RETURNS [result:
INT] =
INLINE {
result ← y[k] - y[j];
y[k] ← result;
IF (j ← j-1) = 0 THEN j ← 55;
IF (k ← k-1) = 0 THEN k ← 55;
RETURN [result]
};
InitRandom:
INTERNAL
PROC [seed:
INT] = {
numCalls: INTEGER = 289;
minSeed: INT = INT.LAST / 10;
maxSeed: INT = minSeed * 9;
defaultSeed: INT = 1354117939;
g, gPrev, gSave: INT;
IF seed = 0 OR seed = INT.FIRST THEN seed ← defaultSeed;
seed ← seed.ABS;
WHILE seed<minSeed DO seed ← seed*3 ENDLOOP;
WHILE seed>maxSeed DO seed ← seed/3 ENDLOOP;
The array y is initialized by placing seed in y[55], and scattering the values
(-1)**(i-1) * (F(i) - seed*F(i-1)), 0<i<55,
(where F(i) denotes the i-th Fibonacci number) throughout the rest of y. Then the generating procedure Random is called, numCalls times, to make things sufficiently random.
y[55] ← gPrev ← seed;
g ← 1;
FOR i:
CARDINAL
IN [1..54]
DO
y[(21*i) MOD 55] ← gSave ← g; g ← gPrev-g; gPrev ← gSave;
ENDLOOP;
j ← 24; k ← 55;
THROUGH [1..numCalls] DO [] ← Random[] ENDLOOP;
};
END.
CHANGE LOG
Edited on August 5, 1984 4:59:41 pm PDT, by Kupfer
Add TransIDToRope function.
changes to: DIRECTORY, CoordinatorTransIDImpl, TransIDToRope
Carl Hauser, October 4, 1985 1:26:07 pm PDT
Change "Log" to "YggLog"