CoordinatorTransIDImpl.mesa
Transaction ID generator.
Copyright © 1984 by Xerox Corporation. All rights reserved.
Last edited by
MBrown on November 3, 1982 3:29 pm
Last Edited by: Kupfer, August 5, 1984 4:59:49 pm PDT
Carl Hauser, November 20, 1985 11:51:44 am PST
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
AlpineEnvironment,
AlpineInternal,
ConcreteTransID,
Convert USING [RopeFromInt],
Coordinator,
CoordinatorInternal USING [],
CoordinatorMap USING [GetHandle],
AlpineLog,
Rope USING [Cat, ROPE],
SkiPatrolHooks;
CoordinatorTransIDImpl: MONITOR
IMPORTS
Convert,
CoordinatorMap,
AlpineLog,
Rope
EXPORTS
AlpineEnvironment,
AlpineInternal,
CoordinatorInternal,
SkiPatrolHooks =
BEGIN
VolumeID: TYPE = AlpineEnvironment.VolumeID;
TransID: PUBLIC TYPE = ConcreteTransID.TransID;
AlpineEnvironment.TransID.
CoordinatorObject: PUBLIC TYPE = Coordinator.Object;
AlpineInternal.CoordinatorObject.
YES: BOOLTRUE;
myFileStoreID: VolumeID;
randomSeed: INT ← 0;
lastSeqNum: INTINT.FIRST;
The largest transaction sequence number ever issued.
nSeqNumsIssuedSinceForce: INT [0 .. maxSeqNumsIssuedWithoutForce];
maxSeqNumsIssuedWithoutForce: INT = 8;
nextForceLogRecordID: AlpineLog.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: Coordinator.Handle] = {
IF nSeqNumsIssuedSinceForce = maxSeqNumsIssuedWithoutForce THEN {
AlpineLog.Force[followingRecord: nextForceLogRecordID];
nSeqNumsIssuedSinceForce ← 0 };
c.transID ← TransID[
fileStore: myFileStoreID,
idOnFileStore: (lastSeqNum ← lastSeqNum + 1),
randomBits: Random[]];
[thisRecord: c.beginRecord, followingRecord: c.forceRecord] ← AlpineLog.CoordinatorWrite[c, coordinatorBegin, AlpineLog.nullBlock];
IF nSeqNumsIssuedSinceForce = 0 THEN nextForceLogRecordID ← c.forceRecord;
nSeqNumsIssuedSinceForce ← nSeqNumsIssuedSinceForce + 1;
};
TransIDToRope: PUBLIC SAFE PROC [transID: AlpineEnvironment.TransID, includeRName: BOOLYES] RETURNS [Rope.ROPE] ~ CHECKED {
SkiPatrolHooks.TransIDToRope. Returns a string which identifies the transaction. If "includeRName," the string includes the RName owning the transaction.
trueTransID: ConcreteTransID.TransID ← LOOPHOLE[transID];
temp: Rope.ROPE ← Convert.RopeFromInt[trueTransID.idOnFileStore];
IF includeRName THEN {
c: Coordinator.Handle;
TRUSTED {c ← CoordinatorMap.GetHandle[transID]};
SELECT c FROM
NIL =>
IF transID = AlpineEnvironment.nullTransID THEN
temp ← temp.Cat[" (null)"]
ELSE
temp ← temp.Cat[" (deleted)"];
ENDCASE =>
temp ← temp.Cat[" (", c.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 "AlpineLog"