File: DBStorageTupleImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Last edited by
MBrown on December 6, 1982 9:27 am
Cattell on November 4, 1983 2:26 am
Willie-Sue on February 15, 1985 12:38:55 pm PST
Donahue, March 10, 1986 11:48:57 am PST
Widom, September 12, 1985 9:13:44 am PDT
DIRECTORY
DBCommon USING [GetDebugStream, Segment, CacheHandle, TupleObject],
DBSegment USING [IsValidTID, SegmentFromTID],
DBStorage,
DBStorageTID USING [TID, NullTID],
DBStorageTuple USING [],
Process USING [Detach],
RefTab,
SafeStorage USING [
EnableFinalization, FinalizationQueue, EstablishFinalization, ReEstablishFinalization,
CantEstablishFinalization, NewFQ, FQNext],
IO;
DBStorageTupleImpl: CEDAR MONITOR
IMPORTS
DBCommon,
DBSegment,
Process,
RefTab,
SafeStorage,
IO
EXPORTS
DBStorage,
DBStorageTuple
= BEGIN
TID: TYPE = DBStorageTID.TID;
NullTID: TID = DBStorageTID.NullTID;
Segment: TYPE = DBCommon.Segment;
TupleObject: PUBLIC TYPE = DBCommon.TupleObject;
TupleHandle: TYPE = REF TupleObject;
Module state not requiring monitor protection.
nullTupleHandle: TupleHandle;
After initialization, points to a TupleObject with tid = NullTID (on storedTupleList.)
This is returned by NullTupleHandle[] so that others may share. Nobody should modify!
storedFinalizationQLen: INT = 100;
establishFinalizationFailed: BOOLFALSE;
tupleFQ: SafeStorage.FinalizationQueue ← SafeStorage.NewFQ[length: storedFinalizationQLen];
systemTuples: TupleHandle ← NIL;
freeTuples: TupleHandle ← NIL;
freeCount: NAT ← 0;
For each segment in use there is an associated storedTupleList (head of doubly-linked list (through pred, succ) of all in-use stored tuple objects).
SegmentRecordHandle: TYPE = REF SegmentRecord;
SegmentRecord: TYPE = RECORD [ storedTupleList: TupleHandle ← NIL ];
A RefTab is used to map segments to their tuple and free lists. The segment table and the free list are monitored
sizeOfSegmentTable: CARDINAL = 17;
segmentTable: RefTab.Ref = RefTab.Create[mod: sizeOfSegmentTable];
maxFree: CARDINAL = 100;
InitSegmentTuples: PUBLIC PROC [segment: Segment] = {
establishFinalizationFailed: BOOLFALSE;
sHandle: SegmentRecordHandle ← NEW[SegmentRecord];
sHandle.storedTupleList ← NEW[TupleObject ← [tid: NullTID, pred: NIL, succ: NIL, cacheHint: NIL]];
sHandle.storedTupleList.pred ← sHandle.storedTupleList.succ ← sHandle.storedTupleList;
[] ← RefTab.Store[segmentTable, segment, sHandle] };
ConsTupleObject: PUBLIC ENTRY PROC [tid: TID, cacheHint: DBCommon.CacheHandle] RETURNS [result: TupleHandle] = {
ENABLE UNWIND => InitSegmentTuples[DBSegment.SegmentFromTID[tid]];
segment: Segment = DBSegment.SegmentFromTID[tid];
sHandle: SegmentRecordHandle;
found: BOOLEAN; item: RefTab.Val;
[found, item] ← RefTab.Fetch[segmentTable, segment];
IF NOT found THEN ERROR;
sHandle ← NARROW[item];
IF freeCount > 0 THEN {
result ← GetFreeTuple[sHandle.storedTupleList];
result.tid ← tid; result.cacheHint ← cacheHint
}
ELSE {
result ← NEW[TupleObject ← [tid: tid, cacheHint: cacheHint]];
result.pred ← sHandle.storedTupleList.pred;
result.succ ← sHandle.storedTupleList;
sHandle.storedTupleList.pred.succ ← result;
sHandle.storedTupleList.pred ← result;
SafeStorage.EnableFinalization[result] };
RETURN[result];
};
GetFreeTuple: INTERNAL PROC[head: TupleHandle] RETURNS[result: TupleHandle] = {
result ← freeTuples.succ;
Remove the handle from the free list
result.succ.pred ← result.pred;
result.pred.succ ← result.succ;
And add it to the list of stored handles that begins at head
result.succ ← head.succ;
result.pred ← head;
head.succ.pred ← result;
head.succ ← result;
freeCount ← freeCount - 1;
SafeStorage.EnableFinalization[result] };
ConsSystemTupleObject: PUBLIC ENTRY PROC [] RETURNS [result: TupleHandle] = {
IF freeCount > 0 THEN { result ← GetFreeTuple[systemTuples] }
ELSE {
result ← NEW[TupleObject ← []];
result.pred ← systemTuples.pred;
result.succ ← systemTuples;
systemTuples.pred.succ ← result;
systemTuples.pred ← result;
SafeStorage.EnableFinalization[result] };
RETURN[result] };
TupleObjectFinalizerProcess: PROC [] = {
FinalizeStoredTupleObject: ENTRY PROC [t: TupleHandle] = {
ENABLE UNWIND => NULL;
IF freeCount < maxFree THEN {
Cut it out of the list to which it belongs
t.succ.pred ← t.pred;
t.pred.succ ← t.succ;
Stitch it back into the free list
t.succ ← freeTuples.succ;
t.pred ← freeTuples;
freeTuples.succ.pred ← t;
freeTuples.succ ← t;
freeCount ← freeCount + 1 }
ELSE {
Next line is a noop for single-element list (t.succ = t), but that is ok ...
t.succ.pred ← t.pred; t.pred.succ ← t.succ;
t.succ ← t.pred ← NIL;
}
};
DO
th: TupleHandle ← NARROW[SafeStorage.FQNext[tupleFQ]];
FinalizeStoredTupleObject[th];
ENDLOOP;
};
TIDOfTuple: PUBLIC PROC [x: TupleHandle] RETURNS [TID] = { RETURN[x.tid] };
EqualTuple: PUBLIC PROC [x, y: TupleHandle] RETURNS [BOOLEAN] = {
IF x=NIL THEN x ← nullTupleHandle;
IF y=NIL THEN y ← nullTupleHandle;
RETURN[x.tid = y.tid];
};
NullTupleHandle: PUBLIC PROC [] RETURNS [TupleHandle] = { RETURN[nullTupleHandle] };
InvalidateMatchingTuples: PUBLIC PROC [x: TupleHandle] = {
xTID: TID = x.tid;
s: Segment = DBSegment.SegmentFromTID[x.tid];
sHandle: SegmentRecordHandle;
found: BOOLEAN; item: RefTab.Val;
[found, item] ← RefTab.Fetch[segmentTable, s];
IF NOT found THEN ERROR;
sHandle ← NARROW[item];
FOR p: TupleHandle ← sHandle.storedTupleList.succ, p.succ UNTIL p=sHandle.storedTupleList DO
IF p.tid=xTID THEN p.tid ← NullTID;
ENDLOOP;
};
IsValidTuple: PUBLIC PROC [x: TupleHandle] RETURNS [valid: BOOL] = {
IF NOT ISTYPE[x, TupleHandle] THEN RETURN [valid: TRUE];
IF DBSegment.IsValidTID[x.tid] THEN RETURN [valid: TRUE]
ELSE {
x.tid ← NullTID;
RETURN [valid: FALSE];
};
};
InvalidateTuple: PUBLIC PROC [x: TupleHandle] = {
IF x#NIL THEN x.tid ← NullTID;
};
CallAfterFinishTransaction: PUBLIC PROC [s: Segment] = {
sHandle: SegmentRecordHandle;
found: BOOLEAN; item: RefTab.Val;
[found, item] ← RefTab.Fetch[segmentTable, s];
IF NOT found THEN ERROR;
sHandle ← NARROW[item];
FOR p: TupleHandle ← sHandle.storedTupleList.succ, p.succ UNTIL p=sHandle.storedTupleList DO
IF p.tid # NullTID THEN p.tid ← NullTID;
ENDLOOP;
};
PrintTupleObjectToStream: PROC [t: TupleHandle, debugStream: IO.STREAM] = {
IOref: PROC[p: REF ANY] RETURNS[IO.Value] = INLINE {
RETURN[IO.card[LOOPHOLE[p, LONG CARDINAL]]]};
debugStream.PutF["tupleHdl: %11bB, tupleID: %12bB, cacheHdl: %11bB",
IOref[t], IO.card[t.tid], IOref[t.cacheHint]] };
PrintTupleObject: PUBLIC PROC [t: TupleHandle] = {
PrintTupleObjectToStream[t, DBCommon.GetDebugStream[]]
};
PrintTupleList: PROC [t: TupleHandle] =
BEGIN start: TupleHandle← t;
out: IO.STREAM = DBCommon.GetDebugStream[];
out.PutF["tid %g\n", IO.int[t.tid]];
FOR t← start.succ, t.succ UNTIL t=NIL DO
out.PutF["tid %g\n", IO.int[t.tid]] ENDLOOP;
END;
SafeStorage.EstablishFinalization[ type: CODE[TupleObject], npr: 2, fq: tupleFQ !
SafeStorage.CantEstablishFinalization => {establishFinalizationFailed← TRUE; CONTINUE} ];
IF establishFinalizationFailed THEN
SafeStorage.ReEstablishFinalization[ type: CODE[TupleObject], npr: 2, fq: tupleFQ ];
systemTuples ← NEW[TupleObject ← [tid: NullTID, pred: NIL, succ: NIL, cacheHint: NIL]];
systemTuples.pred ← systemTuples.succ ← systemTuples;
freeTuples ← NEW[TupleObject ← [tid: NullTID, pred: NIL, succ: NIL, cacheHint: NIL]];
freeTuples.pred ← freeTuples.succ ← freeTuples;
TRUSTED{ Process.Detach[ FORK TupleObjectFinalizerProcess[] ] }

END
.--DBStorageTupleImpl