<> <> <> <> <> <> <> <> <> DIRECTORY YggEnvironment USING[PageCount, PageNumber, PageRun], YggInternal USING[Document, LogRecordID, TransHandle], Basics USING[CompareInt], YggDIDMap USING[ClearLogMapHandle, Document, VerifyLogMapHandle], YggLogMap USING[CheckOutOption, CallingErrorType, FileDescription, Location, MappedPageRun], YggLogMapPrivate USING[IntentionObject, Intention], RedBlackTree USING[Compare, Create, Delete, GetKey, Insert, Lookup, LookupLargest, LookupNextLarger, LookupNextSmaller, LookupSmallest, Node, Table], YggTransactionMap USING[IsCommitted]; YggLogMapImpl: CEDAR MONITOR LOCKS logMapHandle USING logMapHandle: LogMap IMPORTS Basics, YggDIDMap, RedBlackTree, YggTransactionMap EXPORTS YggInternal, YggLogMap = BEGIN LogMap: TYPE = REF LogMapRep; LogMapRep: PUBLIC TYPE = MONITORED RECORD[ createTrans: YggInternal.TransHandle, deleteTrans: YggInternal.TransHandle, sizeUncommitted: YggEnvironment.PageCount, sizeUncommittedTrans: YggInternal.TransHandle, sizeCommitted: YggEnvironment.PageCount, highWaterMarkCommitted: YggEnvironment.PageCount, intentionsTable: RedBlackTree.Table, <> rbKeyRef: REF YggEnvironment.PageNumber ]; Error: PUBLIC --CALLING-- ERROR [error: YggLogMap.CallingErrorType] = CODE; <> ProbableLockingFailure: --CALLING-- ERROR = CODE; Horrible: --CALLING-- ERROR = CODE; DescribeFile: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] RETURNS [fileDesc: YggLogMap.FileDescription] = BEGIN -- non-fatal errors: none. MonitoredDescribeFile: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. fileDesc.registered _ TRUE; fileDesc.created _ trans = logMapHandle.createTrans; fileDesc.deleted _ trans = logMapHandle.deleteTrans; TRUSTED BEGIN fileDesc.exists _ ( ((fileDesc.created) OR (logMapHandle.createTrans = NIL) OR (YggTransactionMap.IsCommitted[logMapHandle.createTrans])) AND NOT ((fileDesc.deleted) OR ((logMapHandle.deleteTrans # NIL) AND (YggTransactionMap.IsCommitted[logMapHandle.deleteTrans])))); END; fileDesc.sizeChanged _ trans = logMapHandle.sizeUncommittedTrans; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; IF logMapHandle # NIL THEN MonitoredDescribeFile[logMapHandle] ELSE fileDesc.registered _ FALSE; END; <> RegisterCreate: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] = BEGIN -- non-fatal errors: none. MonitoredRegisterCreate: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. IF logMapHandle.createTrans # NIL THEN RETURN WITH ERROR ProbableLockingFailure; logMapHandle.createTrans _ trans; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, TRUE]; MonitoredRegisterCreate[logMapHandle]; END; <> RegisterDelete: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] = BEGIN -- non-fatal errors: none. MonitoredRegisterDelete: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. IF logMapHandle.deleteTrans # NIL THEN RETURN WITH ERROR ProbableLockingFailure; logMapHandle.deleteTrans _ trans; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, TRUE]; MonitoredRegisterDelete[logMapHandle]; END; <> SetUncommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle, size: YggEnvironment.PageCount] = BEGIN -- non-fatal errors: none. MonitoredSetUncommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. IF ((logMapHandle.sizeUncommittedTrans = NIL) OR (trans = NIL) OR (trans = logMapHandle.sizeUncommittedTrans)) THEN BEGIN logMapHandle.sizeUncommittedTrans _ trans; logMapHandle.sizeUncommitted _ size; END ELSE RETURN WITH ERROR ProbableLockingFailure; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, TRUE]; MonitoredSetUncommittedSize[logMapHandle]; END; <> GetUncommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] RETURNS[size: YggEnvironment.PageCount] = BEGIN -- non-fatal errors: none. MonitoredGetUncommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. IF ((trans # logMapHandle.sizeUncommittedTrans) AND (logMapHandle.sizeUncommittedTrans # NIL)) THEN TRUSTED BEGIN IF YggTransactionMap.IsCommitted[logMapHandle.sizeUncommittedTrans] THEN RETURN WITH ERROR ProbableLockingFailure ELSE size _ LAST[YggEnvironment.PageCount]; END ELSE size _ logMapHandle.sizeUncommitted; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; IF logMapHandle = NIL THEN RETURN[LAST[YggEnvironment.PageCount]]; MonitoredGetUncommittedSize[logMapHandle]; END; <> SetCommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document, size: YggEnvironment.PageCount] = BEGIN -- non-fatal errors: none. MonitoredSetCommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. logMapHandle.sizeCommitted _ size; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, TRUE]; MonitoredSetCommittedSize[logMapHandle]; END; <> GetCommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document] RETURNS[size: YggEnvironment.PageCount] = BEGIN -- non-fatal errors: none. MonitoredGetCommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. size _ logMapHandle.sizeCommitted; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; IF logMapHandle = NIL THEN RETURN[LAST[YggEnvironment.PageCount]]; MonitoredGetCommittedSize[logMapHandle]; END; <> SetCommittedHighWaterMark: PUBLIC PROCEDURE[file: YggInternal.Document, highWaterMark: YggEnvironment.PageCount] = BEGIN -- non-fatal errors: none. MonitoredSetCommittedHighWaterMark: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. logMapHandle.highWaterMarkCommitted _ highWaterMark; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, TRUE]; MonitoredSetCommittedHighWaterMark[logMapHandle]; END; <> GetCommittedHighWaterMark: PUBLIC PROCEDURE[file: YggInternal.Document] RETURNS [highWaterMark: YggEnvironment.PageCount] = BEGIN -- non-fatal errors: none. MonitoredGetCommittedHighWaterMark: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE BEGIN -- non-fatal errors: none. highWaterMark _ logMapHandle.highWaterMarkCommitted; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; IF logMapHandle = NIL THEN RETURN[LAST[YggEnvironment.PageCount]]; MonitoredGetCommittedHighWaterMark[logMapHandle]; END; <> < for transaction trans, identified in the log by logRecordID. The log record contains exactly this pageRun. If writes are already registered for any of those pages by the same transaction, the old writes are forgotten. If writes are already registered for a different transaction, a fatal error is raised.>> RegisterPages: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle, pageRun: YggEnvironment.PageRun, logRecordID: YggInternal.LogRecordID] = BEGIN -- non-fatal errors: none. MonitoredRegisterPages: ENTRY PROCEDURE[logMapHandle: LogMap] = BEGIN -- non-fatal errors: none. currentFirstPage: YggEnvironment.PageNumber _ pageRun.firstPage; currentCount: INT _ pageRun.count; int: YggLogMapPrivate.Intention _ RBTLookupNextSmaller[logMapHandle, currentFirstPage]; IF ((int # NIL) AND (int.pageRun.firstPage + int.pageRun.count > currentFirstPage)) THEN -- fission off the higher part. BEGIN higherPartInt: YggLogMapPrivate.Intention _ NEW[YggLogMapPrivate.IntentionObject _ [int.trans, [currentFirstPage, int.pageRun.count - (currentFirstPage - int.pageRun.firstPage)], int.logRecordID, FALSE, , , ]]; RBTInsert[logMapHandle, higherPartInt, higherPartInt.pageRun.firstPage]; int.pageRun.count _ int.pageRun.count - higherPartInt.pageRun.count; int _ higherPartInt; END ELSE int _ RBTLookup[logMapHandle, currentFirstPage]; DO -- on entry int starts at currentFirstPage or is NIL if nothing starts there. IF int = NIL THEN BEGIN overlap: BOOLEAN; newInt: YggLogMapPrivate.Intention; int _ RBTLookupNextLarger[logMapHandle, currentFirstPage]; overlap _ ((int # NIL) AND (int.pageRun.firstPage < currentFirstPage + currentCount)); newInt _ NEW[YggLogMapPrivate.IntentionObject _ [trans, [currentFirstPage, (IF overlap THEN int.pageRun.firstPage - currentFirstPage ELSE currentCount)], logRecordID, FALSE, , , ]]; -- newInt starts at currentFirstPage. RBTInsert[logMapHandle, newInt, newInt.pageRun.firstPage]; IF NOT overlap THEN EXIT; currentCount _ currentCount - newInt.pageRun.count; currentFirstPage _ int.pageRun.firstPage; END; <> IF ((int.trans # trans) OR (int.checkedOut)) THEN RETURN WITH ERROR ProbableLockingFailure; IF int.pageRun.count > currentCount THEN BEGIN -- fission off the higher part. higherPartInt: YggLogMapPrivate.Intention _ NEW[YggLogMapPrivate.IntentionObject _ [trans, [currentFirstPage + currentCount, int.pageRun.count - currentCount], int.logRecordID, FALSE, , , ]]; RBTInsert[logMapHandle, higherPartInt, higherPartInt.pageRun.firstPage]; int.pageRun.count _ currentCount; END; int.logRecordID _ logRecordID; IF (currentCount _ currentCount - int.pageRun.count) = 0 THEN EXIT; currentFirstPage _ currentFirstPage + int.pageRun.count; int _ RBTLookup[logMapHandle, currentFirstPage]; ENDLOOP; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, TRUE]; TRUSTED BEGIN IF YggTransactionMap.IsCommitted[trans] THEN ERROR Horrible; END; MonitoredRegisterPages[logMapHandle]; END; < does not exactly match a checked out entry in the LogMap, a fatal error is raised.>> UnregisterPages: PUBLIC PROCEDURE[file: YggInternal.Document, pageRun: YggEnvironment.PageRun] = BEGIN -- non-fatal errors: none. MonitoredUnregisterPages: ENTRY PROCEDURE[logMapHandle: LogMap] = BEGIN -- non-fatal errors: none. intention: YggLogMapPrivate.Intention _ RBTLookup[logMapHandle, pageRun.firstPage]; IF ((intention = NIL) OR (NOT intention.checkedOut) OR (intention.pageRun.count # pageRun.count)) THEN RETURN WITH ERROR Horrible; [] _ RBTDelete[logMapHandle, pageRun.firstPage]; BROADCAST IntentionFreed; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; IF logMapHandle = NIL THEN ERROR Horrible; MonitoredUnregisterPages[logMapHandle]; END; IntentionFreed: CONDITION; <> <> LocatePages: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle, pageRun: YggEnvironment.PageRun, checkOut: YggLogMap.CheckOutOption] RETURNS[mappedPageRun: YggLogMap.MappedPageRun] = BEGIN -- non-fatal errors: Error[exceedsFileSize]. MonitoredLocatePages: ENTRY PROCEDURE[logMapHandle: LogMap] RETURNS[mappedPageRun: YggLogMap.MappedPageRun] = BEGIN -- non-fatal errors: Error[exceedsFileSize]. int: YggLogMapPrivate.Intention; currentCount: INT; DO IF pageRun.firstPage + pageRun.count > (IF logMapHandle.sizeUncommittedTrans = trans THEN logMapHandle.sizeUncommitted ELSE logMapHandle.sizeCommitted) THEN RETURN WITH ERROR Error[exceedsFileSize]; int _ RBTLookup[logMapHandle, pageRun.firstPage]; IF (int # NIL) THEN currentCount _ MIN[pageRun.count, int.pageRun.count] ELSE BEGIN int _ RBTLookupNextSmaller[logMapHandle, pageRun.firstPage]; IF ((int # NIL) AND (int.pageRun.firstPage + int.pageRun.count > pageRun.firstPage)) THEN currentCount _ MIN[int.pageRun.firstPage + int.pageRun.count, pageRun.firstPage + pageRun.count] - pageRun.firstPage ELSE BEGIN int _ RBTLookupNextLarger[logMapHandle, pageRun.firstPage]; IF int # NIL THEN BEGIN currentCount _ IF int.pageRun.firstPage < pageRun.firstPage + pageRun.count THEN int.pageRun.firstPage - pageRun.firstPage ELSE pageRun.count; int _ NIL; END ELSE currentCount _ pageRun.count; END; END; TRUSTED BEGIN IF ((int = NIL) OR ((int.trans # trans) AND (NOT YggTransactionMap.IsCommitted[int.trans]))) THEN RETURN[[[pageRun.firstPage, currentCount], base[]]]; END; IF int.trans = trans THEN RETURN[[[pageRun.firstPage, currentCount], log[int.logRecordID, int.pageRun, FALSE]]]; IF checkOut = checkOut THEN BEGIN IF int.checkedOut THEN BEGIN WAIT IntentionFreed; LOOP; END ELSE int.checkedOut _ TRUE; END; RETURN[[[pageRun.firstPage, currentCount], log[int.logRecordID, int.pageRun, (checkOut = checkOut)]]]; ENDLOOP; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; IF logMapHandle = NIL THEN RETURN[[pageRun, base[]]]; RETURN[MonitoredLocatePages[logMapHandle]]; END; <> LocateAnyPagesForTrans: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] RETURNS[found: BOOLEAN, logRecordID: YggInternal.LogRecordID, logMapPageRun: YggEnvironment.PageRun] = BEGIN -- non-fatal errors: none. MonitoredLocateAnyPagesForTrans: ENTRY PROCEDURE[logMapHandle: LogMap] = BEGIN -- non-fatal errors: none. FOR intention: YggLogMapPrivate.Intention _ RBTLookupSmallest[logMapHandle], RBTLookupNextLarger[logMapHandle, intention.pageRun.firstPage] UNTIL intention = NIL DO IF ((intention.trans = trans) AND (NOT intention.checkedOut)) THEN BEGIN found _ TRUE; intention.checkedOut _ TRUE; logRecordID _ intention.logRecordID; logMapPageRun _ intention.pageRun; RETURN; END; ENDLOOP; DO FOR intention: YggLogMapPrivate.Intention _ RBTLookupSmallest[logMapHandle], RBTLookupNextLarger[logMapHandle, intention.pageRun.firstPage] UNTIL intention = NIL DO IF intention.trans = trans THEN BEGIN IF (NOT intention.checkedOut) THEN RETURN WITH ERROR Horrible; WAIT IntentionFreed; EXIT; END; REPEAT FINISHED => GOTO allDone; ENDLOOP; REPEAT allDone => NULL; ENDLOOP; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; found _ FALSE; IF logMapHandle # NIL THEN MonitoredLocateAnyPagesForTrans[logMapHandle]; END; <> UnregisterTrans: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] = BEGIN -- non-fatal errors: none. MonitoredUnregisterTrans: ENTRY PROCEDURE[logMapHandle: LogMap] = BEGIN -- non-fatal errors: none. ClearTransFromLogMapHandle: INTERNAL PROCEDURE RETURNS[LogMap] = BEGIN -- non system fatal errors: none. FOR intention: YggLogMapPrivate.Intention _ RBTLookupSmallest[logMapHandle], RBTLookupNextLarger[logMapHandle, intention.pageRun.firstPage] UNTIL intention = NIL DO IF intention.trans = trans THEN BEGIN IF intention.checkedOut THEN RETURN WITH ERROR Horrible; [] _ RBTDelete[logMapHandle, intention.pageRun.firstPage]; END; ENDLOOP; IF logMapHandle.createTrans = trans THEN logMapHandle.createTrans _ NIL; IF logMapHandle.deleteTrans = trans THEN logMapHandle.deleteTrans _ NIL; IF logMapHandle.sizeUncommittedTrans = trans THEN BEGIN logMapHandle.sizeUncommittedTrans _ NIL; logMapHandle.sizeUncommitted _ LAST[YggEnvironment.PageCount]; END; IF ((RBTLookupSmallest[logMapHandle] = NIL) AND (logMapHandle.createTrans = NIL) AND (logMapHandle.deleteTrans = NIL) AND (logMapHandle.sizeUncommittedTrans = NIL) ) THEN RETURN[NIL] ELSE RETURN[logMapHandle]; END; YggDIDMap.ClearLogMapHandle[file, ClearTransFromLogMapHandle]; END; logMapHandle: LogMap _ GetOrReportOnLogMapHandle[file, FALSE]; IF logMapHandle # NIL THEN MonitoredUnregisterTrans[logMapHandle]; END; <> GetKeyProc: RedBlackTree.GetKey -- PROC [data: UserData] RETURNS [Key] = { RETURN[ data ]; }; CompareProc: RedBlackTree.Compare -- PROC [k: Key, data: UserData] RETURNS [Basics.Comparison] = { dataIntention: YggLogMapPrivate.Intention = NARROW[ data ]; WITH k SELECT FROM pnRef: REF YggEnvironment.PageNumber => RETURN[Basics.CompareInt[pnRef^, dataIntention.pageRun.firstPage]]; keyIntention: YggLogMapPrivate.Intention => RETURN[Basics.CompareInt[keyIntention.pageRun.firstPage, dataIntention.pageRun.firstPage]]; ENDCASE => ERROR; }; <> GetOrReportOnLogMapHandle: PROCEDURE[fileHandle: YggDIDMap.Document, create: BOOLEAN] RETURNS[logMapHandle: LogMap] = BEGIN -- non system fatal errors: none. CreateLogMapHandle: PROCEDURE RETURNS[logMapHandle: LogMap] = BEGIN -- non system fatal errors: none. logMapHandle _ IF create THEN NEW[LogMapRep _ [ createTrans: NIL, deleteTrans: NIL, sizeUncommitted: LAST[YggEnvironment.PageCount], sizeUncommittedTrans: NIL, sizeCommitted: LAST[YggEnvironment.PageCount], highWaterMarkCommitted: LAST[YggEnvironment.PageCount], intentionsTable: RedBlackTree.Create[getKey: GetKeyProc, compare: CompareProc], rbKeyRef: NEW[YggEnvironment.PageNumber _ 0]] ] ELSE NIL; END; logMapHandle _ YggDIDMap.VerifyLogMapHandle[fileHandle, CreateLogMapHandle]; END; <> RBTLookupProc: TYPE = PROCEDURE[ logMapHandle: LogMap, key: YggEnvironment.PageNumber ] RETURNS [YggLogMapPrivate.Intention]; RBTLookup: INTERNAL RBTLookupProc = { logMapHandle.rbKeyRef^ _ key; RETURN[ NARROW[RedBlackTree.Lookup[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef]] ]; }; RBTLookupNextLarger: INTERNAL RBTLookupProc = { logMapHandle.rbKeyRef^ _ key; RETURN[ NARROW[RedBlackTree.LookupNextLarger[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef]] ]; }; RBTLookupNextSmaller: INTERNAL RBTLookupProc = { logMapHandle.rbKeyRef^ _ key; RETURN[ NARROW[RedBlackTree.LookupNextSmaller[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef]] ]; }; RBTLookupLargest: INTERNAL PROCEDURE[ logMapHandle: LogMap ] RETURNS [YggLogMapPrivate.Intention] = { RETURN[ NARROW[RedBlackTree.LookupLargest[ logMapHandle.intentionsTable]] ]; }; RBTLookupSmallest: INTERNAL PROCEDURE[ logMapHandle: LogMap ] RETURNS [YggLogMapPrivate.Intention] = { RETURN[ NARROW[RedBlackTree.LookupSmallest[ logMapHandle.intentionsTable ]] ]; }; RBTDelete: INTERNAL PROCEDURE[ logMapHandle: LogMap, key: YggEnvironment.PageNumber ] RETURNS [YggLogMapPrivate.Intention] = { n: RedBlackTree.Node; logMapHandle.rbKeyRef^ _ key; n _ RedBlackTree.Delete[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef]; RETURN[ IF n=NIL THEN NIL ELSE NARROW[n.data] ]; }; RBTInsert: INTERNAL PROCEDURE[ logMapHandle: LogMap, refChunk: YggLogMapPrivate.Intention, key: YggEnvironment.PageNumber ] = { logMapHandle.rbKeyRef^ _ key; RedBlackTree.Insert[ logMapHandle.intentionsTable, refChunk, logMapHandle.rbKeyRef ]; }; <

> END. <> <> <> <<>>