<> <> <> <> <> <> <> <> <> <<(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; <> 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; <> <<(-1)**(i-1) * (F(i) - seed*F(i-1)), 0> <<(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 <> <> <> <<>> <<>> <<>> <> <> <<>>