BackupBTreeImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Carl Hauser, April 22, 1986 2:49:28 pm PST
DIRECTORY
AlpFile,
AlpineEmergency USING [UncaughtThruMonitor, UnwindingMonitor],
AlpineEnvironment,
AlpineFile,
AlpineLog USING [nullRecordID, RecordID],
AlpTransaction,
AlpineTransaction,
BackupBTree USING [Error, Reason],
BackupLog USING [nullRecordID, RecordID],
BasicTime USING [GMT, nullGMT],
BTree,
BTreeAlpineVM USING [Handle, EndLongUpdate, Open, ReferencePage, ReleasePage, ReOpen, StartLongUpdate],
PrincOps USING [wordsPerPage],
PrincOpsUtils USING [LongCopy],
Rope USING [Flatten, Length, ROPE, Text, TextRep],
RuntimeError USING [UNCAUGHT],
ViewRec,
VM;
BackupBTreeImpl:
CEDAR
MONITOR
IMPORTS
AlpineEmergency, AlpFile, AlpTransaction, BackupBTree, BTree, BTreeAlpineVM, PrincOpsUtils, Rope, RuntimeError, ViewRec, VM
~ BEGIN
OPEN AE: AlpineEnvironment, BB: BackupBTree, RuntimeError;
Error: PUBLIC ERROR[why: BB.Reason] = CODE;
There is just one btree maintained by this package -- it is here in the global frame.
btree:
RECORD [
tree: BTree.Tree,
storage: BTreeAlpineVM.Handle,
pathStk: BTree.PathStk
] ← [NIL, NIL, BTree.NewPathStk[]];
globals:
RECORD [
openFile: AlpFile.Handle,
universalFile: AE.UniversalFile,
trans: AlpTransaction.Handle
];
nullRecordID: BackupLog.RecordID = BackupLog.nullRecordID;
UniversalFile: TYPE = AlpineEnvironment.UniversalFile;
RecordID: TYPE = BackupLog.RecordID;
OpenForNormalOperation:
PUBLIC
ENTRY
PROC [trans: AlpTransaction.Handle, btreeFile:
AE.UniversalFile, initialize:
BOOL ←
FALSE] ~
TRUSTED {
fileID: AE.FileID ← AE.nullFileID;
globals.universalFile ← btreeFile;
globals.trans ← trans;
[globals.openFile, fileID] ← AlpFile.Open[trans, btreeFile, readWrite];
IF btree.tree =
NIL
THEN {
btree.tree ← BTree.New[
repPrim: [compare: Compare, entrySize: EntrySize],
storPrim: [BTreeAlpineVM.ReferencePage, BTreeAlpineVM.ReleasePage]]};
IF btree.storage =
NIL
THEN btree.storage ← BTreeAlpineVM.Open[file: globals.openFile, filePagesPerPage: pageSize, cacheSize: 8, base: 1]
ELSE BTreeAlpineVM.ReOpen[handle: btree.storage, file: globals.openFile, base: 1]; -- reuse backing VM
BTree.Open[
tree: btree.tree, storage: btree.storage,
pageSize: pageSize*PrincOps.wordsPerPage,
maintainRecomputableState: FALSE,
initialize: initialize ! BTree.Error => GOTO damagedBTree]; -- badSeal or wrongPageSize
AlpFile.ReadPages[ handle: globals.openFile, pageRun: positionPageInfo.pageRun, pageBuffer: positionPageInfo.buffer, lock: [read, fail] ! AlpFile.LockFailed => {GOTO Failure} ];
IF initialize THEN {
positionPageInfo.ptr.logRecord ← AlpineLog.nullRecordID;
positionPageInfo.ptr.backupRecord ← BackupLog.nullRecordID;
positionPageInfo.ptr.lastFullyConsistentTime ← BasicTime.nullGMT;
positionPageInfo.ptr.lastFullyConsistentBackupRecord ← BackupLog.nullRecordID;
};
BTreeAlpineVM.StartLongUpdate[btree.storage];
EXITS
Failure => RETURN WITH ERROR BB.Error[lockFailure];
damagedBTree => RETURN WITH ERROR BB.Error[damagedBTree];
};
OpenForRecovery: PUBLIC ENTRY PROC [] ~ {
Body
};
BTree Management
BTreeEntry: TYPE ~ REF BTreeEntryObject;
BTreeEntryPtr: TYPE ~ LONG BASE POINTER TO BTreeEntryObject;
BTreeEntryObject:
TYPE ~
MACHINE
DEPENDENT
RECORD [
size(0): CARDINAL, -- size in words of entire entry, including TextRep's at end
universalFile(1): AlpineEnvironment.UniversalFile,
base(10), lastIncrement(13), prevBase(16): BackupLog.RecordID ← nullRecordID,
name(19): TextRP -- FName w/o version,
here follows the necessary TextRep
];
Key: TYPE ~ REF KeyObject;
KeyObject:
TYPE ~
RECORD [
universalFile: UniversalFile
];
pageSize: NAT = 4;
SetFileInfo:
PUBLIC
ENTRY
PROC [universalFile: UniversalFile, baseRecord, lastIncrementRecord: RecordID ← nullRecordID, name: Rope.
ROPE] ~
TRUSTED {
key: Key ← NewKey[universalFile];
flatName: Rope.Text;
size: CARDINAL ← SIZE[BTreeEntryObject] + SIZE[TextRep[name.Length[]]];
Write:
UNSAFE
PROC[e: BTree.Entry] =
UNCHECKED
BEGIN
entry: BTreeEntryPtr = LOOPHOLE[e];
SELECT
TRUE
FROM
baseRecord = nullRecordID
AND lastIncrementRecord # nullRecordID => {
entry.lastIncrement ← lastIncrementRecord;
};
baseRecord # nullRecordID
AND lastIncrementRecord = nullRecordID => {
entry.prevBase ← entry.base;
entry.base ← baseRecord;
};
baseRecord # nullRecordID
AND lastIncrementRecord # nullRecordID => {
entry.prevBase ← entry.base;
entry.base ← baseRecord;
entry.lastIncrement ← lastIncrementRecord
};
baseRecord = nullRecordID
AND lastIncrementRecord = nullRecordID => {
entry.prevBase ← entry.base ← entry.lastIncrement ← nullRecordID
};
ENDCASE;
entry.universalFile ← universalFile;
entry.size ← SIZE[BTreeEntryObject];
IF name = NIL THEN name ← "";
flatName ← Rope.Flatten[name];
entry.name ← AppendText[LOOPHOLE[entry, BTreeEntryPtr], flatName];
END;
TRUSTED {
BTree.UpdateEntry[btree.tree, key, btree.pathStk,
TRUE, size, Write
! BTree.Error => BB.Error[damagedBTree]]};
FreeKey[key];
};
GetFileInfo:
PUBLIC
ENTRY
PROC [universalFile: UniversalFile, relation: BTree.Relation ← equal]
RETURNS [found:
BOOLEAN ←
FALSE, baseRecord, lastIncrementRecord, prevBaseRecord: RecordID ← nullRecordID, name: Rope.
ROPE] ~
TRUSTED {
key: Key ← NewKey[universalFile];
Read:
UNSAFE
PROC [e: BTree.Entry] =
UNCHECKED
BEGIN
entry: BTreeEntryPtr = LOOPHOLE[e, BTreeEntryPtr];
IF entry #
NIL
THEN {
found ← TRUE;
baseRecord ← entry.base;
lastIncrementRecord ← entry.lastIncrement;
prevBaseRecord ← entry.prevBase;
name ← GetText[entry, entry.name];
};
END;
TRUSTED {BTree.ReadEntry[btree.tree, key, relation, btree.pathStk,
TRUE, Read
! BTree.Error => BB.Error[damagedBTree]]};
FreeKey[key];
};
The following procedures store additional non-btree information in BTree page 0 of the file containing the BTree.
PositionInfo:
TYPE =
RECORD [
logRecord: AlpineLog.RecordID,
backupRecord: BackupLog.RecordID,
lastFullyConsistentTime: BasicTime.GMT,
lastFullyConsistentBackupRecord: BackupLog.RecordID
];
PositionPageInfo:
TYPE =
RECORD [
interval: VM.Interval,
ptr: LONG POINTER TO PositionInfo,
buffer: AlpineFile.PageBuffer,
pageRun: AlpineFile.PageRun
];
positionPageInfo: PositionPageInfo;
SetPositionInfo:
PUBLIC
ENTRY
PROC [logRecord: AlpineLog.RecordID, backupRecord: BackupLog.RecordID] ~
TRUSTED {
positionPageInfo.ptr.logRecord ← logRecord;
positionPageInfo.ptr.backupRecord ← backupRecord;
};
GetPositionInfo:
PUBLIC
ENTRY
PROC []
RETURNS [logRecord: AlpineLog.RecordID, backupRecord: BackupLog.RecordID] ~
TRUSTED {
logRecord ← positionPageInfo.ptr.logRecord;
backupRecord ← positionPageInfo.ptr.backupRecord;
};
SetFullyConsistent:
PUBLIC
ENTRY
PROC [backupRecord: RecordID, time: BasicTime.
GMT] ~
TRUSTED {
positionPageInfo.ptr.lastFullyConsistentTime ← time;
positionPageInfo.ptr.lastFullyConsistentBackupRecord ← backupRecord;
};
Commit:
PUBLIC
PROC [] ~
TRUSTED {
outcome: AlpineTransaction.Outcome;
AlpFile.WritePages[ handle: globals.openFile, pageRun: positionPageInfo.pageRun, pageBuffer: positionPageInfo.buffer, lock: [write, fail] ! AlpFile.LockFailed => {GOTO LockFailure} ];
BTreeAlpineVM.EndLongUpdate[btree.storage];
outcome ← AlpTransaction.Finish[handle: globals.trans, requestedOutcome: commit, continue: TRUE];
IF outcome # commit THEN GOTO TransactionFailure;
BTreeAlpineVM.StartLongUpdate[btree.storage];
EXITS
LockFailure => RETURN WITH ERROR BB.Error[lockFailure];
TransactionFailure => RETURN WITH ERROR BB.Error[transactionFailure];
};
DeleteFileInfo:
PUBLIC
ENTRY
PROC [universalFile: UniversalFile]
RETURNS [found:
BOOLEAN] ~
TRUSTED {
key: Key ← NewKey[universalFile];
found ← BTree.DeleteKey[btree.tree, key, btree.pathStk,
TRUE
! BTree.Error => BB.Error[damagedBTree]];
FreeKey[key];
};
EntrySize: BTree.EntrySize
-- [entry: BTree.Entry] RETURNS [words: BTree.EntSize] -- =
TRUSTED {
e: BTreeEntryPtr ← LOOPHOLE[entry, BTreeEntryPtr];
RETURN[e.size];
};
Compare: BTree.Compare
-- [key: BTree.Key, entry: BTree.Entry] RETURNS [PrincOps.Comparison] -- =
TRUSTED {
This loopholing trick only works because the components of a UniversalFileID are complete (not partial) word values. Be careful.
k: Key = NARROW[key];
e: BTreeEntryPtr = LOOPHOLE[entry, BTreeEntryPtr];
KeyIndex: TYPE = [0..9);
KeyArray: TYPE = ARRAY KeyIndex OF CARDINAL;
FOR i:
CARDINAL
DECREASING
IN KeyIndex
DO
Do the loop in decreasing order because, presumably, fileIDs are much less alike than VolumeIDs.
SELECT
TRUE
FROM
LOOPHOLE[k.universalFile, KeyArray][i] < LOOPHOLE[e.universalFile, KeyArray][i] => RETURN[less];
LOOPHOLE[k.universalFile, KeyArray][i] > LOOPHOLE[e.universalFile, KeyArray][i] => RETURN[greater];
ENDCASE => NULL;
ENDLOOP;
RETURN[equal];
};
TextRP: TYPE = BTreeEntryPtr RELATIVE POINTER TO TextRep;
TextRep: TYPE = Rope.TextRep;
GetText:
PROC [eP: BTreeEntryPtr, textRP: TextRP]
RETURNS[text: Rope.Text] =
TRUSTED {
textRep: LONG POINTER TO TextRep ← @eP[textRP];
size: CARDINAL ← SIZE[TextRep[textRep.length]];
text ← NEW[TextRep[textRep.length]];
PrincOpsUtils.LongCopy [
from: textRep,
nwords: size,
to: LOOPHOLE[text]
];
};
AppendText:
PROC [eP: BTreeEntryPtr, text: Rope.Text]
RETURNS [textRP: TextRP] =
TRUSTED {
textRep: LONG POINTER TO TextRep;
size: CARDINAL ← SIZE[TextRep[text.length]];
textRP ← LOOPHOLE[eP.size];
textRep ← @eP[textRP];
PrincOpsUtils.LongCopy [
from: LOOPHOLE[text],
nwords: size,
to: textRep
];
eP.size ← eP.size+size;
};
stockKey: Key ← NIL;
NewKey:
INTERNAL
PROC [universalFile: UniversalFile]
RETURNS[key: Key] = {
ENABLE {
UNWIND => AlpineEmergency.UnwindingMonitor[];
UNCAUGHT => {AlpineEmergency.UncaughtThruMonitor[]; REJECT};
};
IF stockKey = NIL THEN stockKey ← NEW[KeyObject];
key ← stockKey;
stockKey ← NIL;
key^ ← [universalFile];
};
FreeKey:
PROC [key: Key] =
INLINE {
IF key # NIL THEN stockKey ← key;
};
ShowTree: PROC [] = {
[] ← ViewRec.ViewRef[agg: btree.tree];
};
Body of BackupBTreeImpl
positionPageInfo.interval ← VM.Allocate[count: 1];
positionPageInfo.ptr ← LOOPHOLE[VM.AddressForPageNumber[positionPageInfo.interval.page]];
TRUSTED { positionPageInfo.buffer ← DESCRIPTOR[VM.AddressForPageNumber[positionPageInfo.interval.page], 1*PrincOps.wordsPerPage] };
positionPageInfo.pageRun ← [0, 1]
END.