<> <> <> <> <> <> DIRECTORY DBCommon USING[WordsPerPage], DBEnvironment USING[InternalError], DBStats, DBStorageVec, DBStorageTID USING[TIDSlotMask], PrincOpsUtils; DBStorageVecImpl: CEDAR PROGRAM IMPORTS DBEnvironment, DBStats, DBStorageVec, I: PrincOpsUtils EXPORTS DBStorageVec SHARES DBStorageVec = BEGIN OPEN DBEnvironment; VecPage: TYPE = DBStorageVec.VecPage; Slot: TYPE = DBStorageVec.Slot; VecHeader: TYPE = DBStorageVec.VecHeader; <> <> <> FreeSlotIndex: DBStorageVec.SlotIndexField = 0; <> NonsenseSlotIndex: CARDINAL = LAST[CARDINAL]; <> <> ValidateInput: BOOL = TRUE; <> <<(Don't exhaustively check input pages).>> CheckPage: BOOL = TRUE; <> <<(Don't exhaustively check input pages).>> ExhaustivelyCheckPage: BOOL = FALSE; <> <> <> VecOfOffset: PROC[p: LONG POINTER TO VecPage, offset: CARDINAL] RETURNS[LONG POINTER TO VecHeader] = TRUSTED INLINE BEGIN RETURN[LOOPHOLE[p+offset, LONG POINTER TO VecHeader]]; END;--VecOfOffset FreeVecOffset: PROC[p: LONG POINTER TO VecPage] RETURNS[CARDINAL] = TRUSTED INLINE BEGIN <> RETURN[LOOPHOLE[p + (DBCommon.WordsPerPage-SIZE[Slot]), LONG POINTER TO Slot].vecOffset]; END;--FreeVecOffset FreeVecPtr: PROC[p: LONG POINTER TO VecPage] RETURNS[LONG POINTER TO VecHeader] = TRUSTED INLINE BEGIN <> RETURN[VecOfOffset[p, FreeVecOffset[p]]]; END;--FreeVecPtr InitializeVecPage: PUBLIC PROC[ p: LONG POINTER TO VecPage, pageTag: CARDINAL] = TRUSTED BEGIN <> <> WordsFree: CARDINAL = DBCommon.WordsPerPage - SIZE[VecPage] - SIZE[Slot]; <> DBStats.Inc[StorageInitVecPage]; p^ _ VecPage[tag: pageTag, highSlot: 0, nFreeSlots: 0, nWordsInFreeVecs: WordsFree]; LOOPHOLE[p+SIZE[VecPage], LONG POINTER TO VecHeader]^ _ VecHeader[slotIndex: FreeSlotIndex, length: WordsFree]; LOOPHOLE[p+DBCommon.WordsPerPage-SIZE[Slot], LONG POINTER TO Slot]^ _ Slot[type: DBStorageVec.UnFreeType, vecOffset: SIZE[VecPage]]; END;--InitializeVecPage CheckVecPage: PUBLIC PROC[ p: LONG POINTER TO VecPage, pageTag: CARDINAL] = TRUSTED BEGIN <> <> <> OPEN pageHdr: p; Assert: PROC[condition: BOOL] = CHECKED BEGIN IF ~condition THEN ERROR InternalError; -- CheckVecPageFailed END;--Assert <> DBStats.Inc[StorageCheckVecPage]; Assert[pageTag = DBStorageVec.TagOfPage[p]]; <> BEGIN nFreeSlots: CARDINAL _ 0; curSlot: CARDINAL; FOR curSlot IN [1..DBStorageVec.HighSlotIndexOfPage[p]] DO IF DBStorageVec.TypeOfSlot[p, curSlot] = DBStorageVec.FreeType THEN nFreeSlots _ nFreeSlots + 1; ENDLOOP; Assert[nFreeSlots = pageHdr.nFreeSlots]; END; <> BEGIN freeVecPtr: LONG POINTER TO VecHeader _ FreeVecPtr[p]; Assert[LOOPHOLE[p+DBCommon.WordsPerPage-SIZE[Slot], LONG POINTER TO Slot].type = DBStorageVec.UnFreeType]; Assert[freeVecPtr.slotIndex = FreeSlotIndex]; Assert[LOOPHOLE[freeVecPtr + freeVecPtr.length, LONG POINTER TO Slot] = DBStorageVec.IndexToSlot[p, DBStorageVec.HighSlotIndexOfPage[p]]]; END; <> <> <> BEGIN freeWords: CARDINAL _ FreeVecPtr[p].length; nonFreeVecs: CARDINAL _ 0; curVecPtr: LONG POINTER TO VecHeader _ VecOfOffset[p, SIZE[VecPage]]; WHILE curVecPtr # FreeVecPtr[p] DO IF curVecPtr.slotIndex = FreeSlotIndex THEN freeWords _ freeWords + curVecPtr.length ELSE BEGIN Assert[DBStorageVec.TypeOfSlot[p, curVecPtr.slotIndex] # DBStorageVec.FreeType]; Assert[DBStorageVec.VecOfSlot[p, curVecPtr.slotIndex] = curVecPtr]; nonFreeVecs _ nonFreeVecs + 1; END;--IF curVecPtr _ curVecPtr + curVecPtr.length; ENDLOOP; Assert[freeWords = pageHdr.nWordsInFreeVecs]; Assert[nonFreeVecs + pageHdr.nFreeSlots = pageHdr.highSlot]; END; END;--CheckVecPage AllocVec: PUBLIC PROC[p: LONG POINTER TO VecPage, nWords: CARDINAL] RETURNS[--slotIndex-- CARDINAL, --success-- BOOL] = TRUSTED BEGIN <> <> <> OPEN pageHdr: p; newSlotIndex: CARDINAL; BEGIN--block for exit GOTOs newSlotPtr: LONG POINTER TO Slot; freeVecPtr: LONG POINTER TO VecHeader _ FreeVecPtr[p]; oldFreeVecLength: CARDINAL; DBStats.Inc[StorageAllocVec]; IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; IF ValidateInput AND (nWords < SIZE[VecHeader]) THEN ERROR InternalError; -- NWordsTooSmall IF pageHdr.nFreeSlots = 0 THEN BEGIN IF pageHdr.nWordsInFreeVecs < nWords+SIZE[VecHeader]+SIZE[Slot] THEN GOTO Failure; IF pageHdr.highSlot = DBStorageTID.TIDSlotMask THEN GOTO Failure; IF freeVecPtr.length = SIZE[VecHeader] THEN BEGIN CompactPage[p]; freeVecPtr _ FreeVecPtr[p]; END;--IF <> newSlotIndex _ pageHdr.highSlot _ pageHdr.highSlot + 1; newSlotPtr _ DBStorageVec.IndexToSlot[p, newSlotIndex]; IF CheckPage AND (freeVecPtr + freeVecPtr.length-1 # LOOPHOLE[newSlotPtr, LONG POINTER TO VecHeader]) THEN ERROR InternalError; -- FreeVecSmashed <> freeVecPtr.length _ freeVecPtr.length - SIZE[Slot]; IF CheckPage AND (freeVecPtr.length < SIZE[VecHeader]) THEN ERROR InternalError; -- FreeVecSmashed pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs - SIZE[Slot]; END ELSE BEGIN--pageHdr.nFreeSlots > 0 IF pageHdr.nWordsInFreeVecs < nWords+SIZE[VecHeader] THEN GOTO Failure; <> FOR newSlotIndex IN [1..pageHdr.highSlot] DO IF DBStorageVec.TypeOfSlot[p, newSlotIndex] = DBStorageVec.FreeType THEN EXIT; REPEAT FINISHED => ERROR InternalError; -- FreeSlotsSmashed ENDLOOP; newSlotPtr _ DBStorageVec.IndexToSlot[p, newSlotIndex]; pageHdr.nFreeSlots _ pageHdr.nFreeSlots - 1; END;--IF <> IF freeVecPtr.length < nWords+SIZE[VecHeader] THEN BEGIN CompactPage[p]; freeVecPtr _ FreeVecPtr[p]; END;--IF <> oldFreeVecLength _ freeVecPtr.length; IF CheckPage AND (oldFreeVecLength < nWords+SIZE[VecHeader]) THEN ERROR InternalError; -- FreeVecSmashed freeVecPtr^ _ [slotIndex: newSlotIndex, length: nWords]; newSlotPtr^ _ [type: DBStorageVec.UnFreeType, vecOffset: FreeVecOffset[p]]; freeVecPtr _ freeVecPtr + nWords; freeVecPtr^ _ [slotIndex: FreeSlotIndex, length: oldFreeVecLength-nWords]; newSlotPtr _ LOOPHOLE[p + (DBCommon.WordsPerPage - SIZE[Slot]), LONG POINTER TO Slot]; -- point to freeSlot newSlotPtr.vecOffset _ newSlotPtr.vecOffset + nWords; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs - nWords; GOTO Success; EXITS Success => BEGIN IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; RETURN[newSlotIndex, TRUE]; END;--Success Failure => BEGIN IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; RETURN[NonsenseSlotIndex, FALSE]; END;--Failure END; END;--AllocVec WordsInLargestAllocableVec: PUBLIC PROC[p: LONG POINTER TO VecPage] RETURNS[--nWords-- CARDINAL] = TRUSTED { OPEN pageHdr: p; wordsOfVecSpace: CARDINAL = pageHdr.nWordsInFreeVecs - SIZE[VecHeader]; wordsNeededForSlots: CARDINAL = IF pageHdr.nFreeSlots = 0 THEN SIZE[Slot] ELSE 0; RETURN[IF wordsOfVecSpace <= wordsNeededForSlots THEN 0 ELSE wordsOfVecSpace-wordsNeededForSlots]; };--WordsInLargestAllocableVec FreeVec: PUBLIC PROC[p: LONG POINTER TO VecPage, slotIndex: CARDINAL] = TRUSTED BEGIN <> OPEN pageHdr: p; slotPtr: LONG POINTER TO Slot; DBStats.Inc[StorageFreeVec]; IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; IF ValidateInput AND (slotIndex = 0 OR slotIndex > pageHdr.highSlot) THEN ERROR InternalError; -- NotASlot slotPtr _ DBStorageVec.IndexToSlot[p, slotIndex]; IF ValidateInput AND (slotPtr.type = DBStorageVec.FreeType) THEN ERROR InternalError; -- SlotIsFree BEGIN vecPtr: LONG POINTER TO VecHeader _ LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader]; vecPtr.slotIndex _ FreeSlotIndex; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecPtr.length; END; IF slotIndex # pageHdr.highSlot THEN BEGIN slotPtr^ _ Slot[type: DBStorageVec.FreeType, vecOffset: 0]; pageHdr.nFreeSlots _ pageHdr.nFreeSlots + 1; END ELSE BEGIN freeWordsReclaimed: CARDINAL _ 1; <> IF CheckPage AND (DBStorageVec.IndexToSlot[p, FreeSlotIndex].type # DBStorageVec.UnFreeType) THEN ERROR InternalError; -- FreeVecSmashed DO IF (slotPtr+freeWordsReclaimed).type # DBStorageVec.FreeType THEN EXIT; freeWordsReclaimed _ freeWordsReclaimed + 1; ENDLOOP; pageHdr.highSlot _ pageHdr.highSlot - freeWordsReclaimed; pageHdr.nFreeSlots _ pageHdr.nFreeSlots - (freeWordsReclaimed-1); BEGIN freeVecPtr: LONG POINTER TO VecHeader _ FreeVecPtr[p]; freeVecPtr.length _ freeVecPtr.length + freeWordsReclaimed; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + freeWordsReclaimed; END; END;--IF IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; RETURN; END;--FreeVec ModifyVec: PUBLIC PROC [ p: LONG POINTER TO VecPage, slotIndex: CARDINAL, deltaWords: INTEGER, preserveContents: BOOL] RETURNS[--success-- BOOL] = TRUSTED BEGIN <> <0 and>> <> <> <> OPEN pageHdr: LOOPHOLE[p, LONG POINTER TO VecPage]; BEGIN -- Block for EXITS GOTOs slotPtr: LONG POINTER TO Slot; -- points to slot whose vec we're modifying vecPtr: LONG POINTER TO VecHeader; -- points to vec we're modifying vecLen: CARDINAL; -- original length of vec we're modifying newVecLen: CARDINAL; -- length after modification DBStats.Inc[StorageModifyVec]; IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; IF ValidateInput AND (slotIndex = 0 OR slotIndex > pageHdr.highSlot) THEN ERROR InternalError; -- NotASlot slotPtr _ DBStorageVec.IndexToSlot[p, slotIndex]; IF ValidateInput AND (slotPtr.type = DBStorageVec.FreeType) THEN ERROR InternalError; -- SlotIsFree vecPtr _ LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader]; vecLen _ vecPtr.length; IF deltaWords > 0 THEN BEGIN valPtr: LONG POINTER; valPtrRef: REF Block; Block: TYPE = RECORD [SEQUENCE length: CARDINAL OF CARDINAL]; valWasAllocated: BOOL _ FALSE; -- TRUE later if valPtr points to heap storage IF deltaWords + SIZE[VecHeader] > pageHdr.nWordsInFreeVecs THEN--it just won't fit GOTO Failure; <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> newVecLen _ vecLen + deltaWords; IF newVecLen + SIZE[VecHeader] > pageHdr.nWordsInFreeVecs THEN BEGIN <> IF preserveContents THEN BEGIN -- copy current value to temp storage DBStats.Inc[StorageModifyDifficultVec]; valPtrRef _ NEW[Block[vecLen-SIZE[VecHeader]]]; valPtr_ LOOPHOLE[valPtrRef, LONG POINTER]+SIZE[Block[0]]; <> I.LongCopy[ from: vecPtr+SIZE[VecHeader], nwords: vecLen-SIZE[VecHeader], to: valPtr]; valWasAllocated _ TRUE; END;--IF vecPtr.slotIndex _ FreeSlotIndex; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecLen; CompactPage[p]; END ELSE BEGIN <> IF ~preserveContents THEN BEGIN --free old vec now, before possible compaction vecPtr.slotIndex _ FreeSlotIndex; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecLen; END;--IF IF newVecLen + SIZE[VecHeader] > FreeVecPtr[p].length THEN BEGIN CompactPage[p]; vecPtr _ LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader]; END;--IF IF preserveContents THEN BEGIN valPtr _ vecPtr + SIZE[VecHeader]; -- safe because no compaction can happen now. vecPtr.slotIndex _ FreeSlotIndex; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecLen; END;--IF END;--IF <> <> <> <> <> <> <> IF CheckPage AND newVecLen + SIZE[VecHeader] > FreeVecPtr[p].length THEN ERROR InternalError; -- Unknown slotPtr.vecOffset _ FreeVecOffset[p]; vecPtr _ LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader]; IF preserveContents THEN BEGIN -- Copy preserved value back I.LongCopy[from: valPtr, nwords: vecLen-SIZE[VecHeader], to: vecPtr+SIZE[VecHeader]]; END;--IF vecLen _ vecPtr.length; -- Length of freeVec before allocation vecPtr^ _ VecHeader[slotIndex: slotIndex, length: newVecLen]; <> vecPtr _ vecPtr + newVecLen; -- Point to freeVec vecPtr^ _ VecHeader[slotIndex: FreeSlotIndex, length: vecLen - newVecLen]; slotPtr _ LOOPHOLE[ p + (DBCommon.WordsPerPage - SIZE[Slot]), LONG POINTER TO Slot]; -- point to FreeSlot slotPtr.vecOffset _ slotPtr.vecOffset + newVecLen; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs - newVecLen; END ELSE BEGIN--deltaWords<=0 IF deltaWords = 0 THEN GOTO Success; <> <> deltaWords _ -deltaWords; IF ValidateInput AND LOOPHOLE[deltaWords, CARDINAL] > vecLen THEN InternalError; -- DeltaTooSmall newVecLen _ LOOPHOLE[vecLen - deltaWords, CARDINAL]; vecPtr.length _ newVecLen; vecPtr _ vecPtr + newVecLen; --point to the fragment we're freeing vecPtr^ _ VecHeader[slotIndex: FreeSlotIndex, length: deltaWords]; pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + deltaWords; END;--IF GOTO Success; EXITS Success => BEGIN IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; RETURN[TRUE]; END;--Success Failure => BEGIN IF ExhaustivelyCheckPage THEN DBStorageVec.CheckVecPage[p, pageHdr.tag]; RETURN[FALSE]; END;--Failure END; END;--ModifyVec CompactPage: PROC[p: LONG POINTER TO VecPage] = TRUSTED BEGIN <> <> <> OPEN pageHdr: p; highSlotOff: CARDINAL _ DBStorageVec.IndexToOffset[DBStorageVec.HighSlotIndexOfPage[p]]; curSrc: CARDINAL _ SIZE[VecPage]; curDst: CARDINAL; <> s, l: CARDINAL; nAllocVecs: CARDINAL _ 0; BEGIN-- block for exit GOTOs DBStats.Inc[StorageCompactPage]; DO <> IF VecOfOffset[p, curSrc].slotIndex = FreeSlotIndex THEN EXIT; nAllocVecs _ nAllocVecs + 1; curSrc _ curSrc + VecOfOffset[p, curSrc].length; IF CheckPage AND (curSrc >= highSlotOff) THEN GOTO NoFreeVecs; REPEAT NoFreeVecs => ERROR InternalError; -- FreeVecSmashed, freeVec should be present ENDLOOP; <> curDst _ curSrc; curSrc _ curSrc + VecOfOffset[p, curSrc].length; IF curSrc >= highSlotOff THEN BEGIN IF ~CheckPage OR (curSrc = highSlotOff) THEN GOTO Compacted ELSE ERROR InternalError; -- Unknown END;--IF DO <> DO <> IF VecOfOffset[p, curSrc].slotIndex # FreeSlotIndex THEN EXIT; curSrc _ curSrc + VecOfOffset[p, curSrc].length; IF curSrc >= highSlotOff THEN GOTO SeenAllVecs; ENDLOOP; <> nAllocVecs _ nAllocVecs + 1; s _ VecOfOffset[p, curSrc].slotIndex; l _ VecOfOffset[p, curSrc].length; I.LongCopy[from: p+curSrc, nwords: l, to: p+curDst]; DBStorageVec.IndexToSlot[p, s].vecOffset _ curDst; curDst _ curDst + l; curSrc _ curSrc + l; IF curSrc >= highSlotOff THEN GOTO SeenAllVecs; REPEAT SeenAllVecs => BEGIN IF ~CheckPage OR (curSrc=highSlotOff) THEN BEGIN DBStorageVec.IndexToSlot[p, FreeSlotIndex].vecOffset _ curDst; VecOfOffset[p, curDst]^ _ VecHeader[slotIndex: FreeSlotIndex, length: curSrc - curDst]; GOTO Compacted; END ELSE ERROR InternalError; END;--SeenAllVecs ENDLOOP; EXITS Compacted => BEGIN IF CheckPage AND (VecOfOffset[p, curDst].length # pageHdr.nWordsInFreeVecs) THEN ERROR InternalError; RETURN; END;--Compacted END;--EXITS END;--CompactPage END.--StorageVecImpl <> Created by MBrown on February 15, 1980 10:39 PM <> <<(before design was "debugged" and documented, interface formalized).>> Changed by MBrown on February 17, 1980 4:58 PM <> <> Changed by MBrown on February 17, 1980 10:25 PM <> Changed by MBrown on February 18, 1980 10:46 AM <> Changed by MBrown on February 18, 1980 6:30 PM <> <> <> <> Changed by MBrown on February 19, 1980 3:41 PM <> Changed by MBrown on 20-Feb-80 11:52 <> <> <> <> <> <> <> Changed by MBrown on February 24, 1980 11:55 AM <> Changed by MBrown on June 11, 1980 4:29 PM <> Changed by MBrown on August 22, 1980 4:37 PM <> Changed by MBrown on August 24, 1980 10:51 AM <> <> Changed by MBrown on September 26, 1980 4:18 PM <> Changed by MBrown on December 6, 1980 11:28 PM <> <> Changed by MBrown on February 27, 1981 5:28 PM <> Changed by MBrown on August 7, 1982 9:56 pm <> <<>> Changed by Willie-Sue on February 15, 1985 <>