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; CoordinatorObject: PUBLIC TYPE = YggCoordinator.Object; YES: BOOL _ TRUE; myFileStoreID: VolumeID; randomSeed: INT _ 0; lastSeqNum: INT _ INT.FIRST; 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; 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 { 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]; }; 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 seedmaxSeed DO seed _ seed/3 ENDLOOP; 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 à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. YggEnvironment.TransID. YggInternal.CoordinatorObject. The largest transaction sequence number ever issued. nextForceLogRecordID will be initialized on first call to NextTransID, since nSeqNumsIssuedSinceForce = 0. YggMonitoringHooks.TransIDToRope. Returns a string which identifies the transaction. If "includeRName," the string includes the RName owning the transaction. 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.) 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