
    <<DirectMapCacheImpl.mesa>>
        <<Copyright © 1985 by Xerox Corporation.  All rights reserved.>>
        <<Bertrand Serlet, October 17, 1985 4:22:04 pm PDT, stolen from CacheModelImpl.mesa>>
        <<Last Edited by: Serlet, April 12, 1985 2:39:09 pm PST>>
        <<Last Edited by: Barth, April 16, 1985 3:58:10 pm PST>>
        <<Last Edited by: Sindhu, May 1, 1985 7:45:54 pm PDT>>
        <<Pradeep Sindhu October 18, 1985 0:19:49 am PDT>>

    DIRECTORY
        DirectMapCache,
        Basics USING [BITSHIFT],
        CacheModels,
        Convert,
        DragOpsCross USING [Half, Word, ZerosWord],
        DragOpsCrossUtils USING [AddDelta, HalfToCard, LowHalf, SingleWordShiftRight],
        IO, Rope;

    DirectMapCacheImpl: CEDAR PROGRAM
        IMPORTS Basics, Convert, DragOpsCrossUtils, IO
        EXPORTS DirectMapCache
        = BEGIN OPEN DragOpsCross, DragOpsCrossUtils;

        <<Private types>>

            Cache: TYPE = CacheModels.Cache;

            wordsPerQuad: NAT = 4;
            maxQuadsPerLine: NAT = 64;
            maxLines: NAT = 16*1024;
            wordsPerPage: CARDINAL = CacheModels.wordsPerPage;
            QuadIndex: TYPE =  [0..maxQuadsPerLine);

            PageEntry: TYPE = REF PageEntryRep;
            PageEntryRep: TYPE = RECORD [
                next: PageEntry _ NIL,
                pageAddr: Word _ ZerosWord,
                useCount: INT _ 0
                ];

            QuadBitVector: TYPE = PACKED ARRAY QuadIndex OF BOOL;

            None: QuadBitVector = ALL[FALSE];

            HashEntry: TYPE = REF HashEntryRep;
            HashEntryRep: TYPE = RECORD [
                next: HashEntry _ NIL,
                lineAddr: Word _ ZerosWord,
                valid: BOOL _ FALSE,
                chunkPresent: QuadBitVector _ None,
                dirty: QuadBitVector _ None,
                referenced: QuadBitVector _ None
                ];

            CacheData: TYPE = REF CacheDataRep;
            CacheDataRep: TYPE = RECORD [
                stats: CacheStats _ [],
                hashVector: HashVector _ NIL,
                pageEntryCount: INT _ 0,
                pageList: PageEntry _ NIL,
                freePageList: PageEntry _ NIL,
                victimIndex: CARDINAL _ 0,
                rover: NAT _ 0,
                quadsPerLine: NAT _ 1,
                wordsPerQuad: NAT _ 4,
                logWordsPerQuad: NAT,
                realCache: CacheModels.Cache _ NIL,
                mapCache: CacheModels.Cache _ NIL,
                lineTable: SEQUENCE linesInCache: NAT OF HashEntry
                ];

            CacheStats: TYPE = RECORD [
                probes: INT _ 0,
                readProbes: INT _ 0,
                writeProbes: INT _ 0,
                writeMisses: INT _ 0,
                writeClean: INT _ 0,
                chunkMisses: INT _ 0,
                lineMisses: INT _ 0,
                jumpMisses: INT _ 0,
                mapMisses: INT _ 0,
                dirtyWrites: INT _ 0
                ];

            HashLim: CARDINAL = 512;
            HashVector: TYPE = REF HashVectorRep;
            HashVectorRep: TYPE = ARRAY [0..HashLim) OF HashEntry;

        LogBaseTwo: PROC [n: NAT] RETURNS [NAT] = {
        IF n = 1 THEN RETURN[0] ELSE RETURN[1+LogBaseTwo[n/2]];
        };


        NewCache: PUBLIC PROC [lines: NAT _ 512, quadsPerLine: NAT _ 1, wordsPerQuad: NAT _ 4, realCache, mapCache: CacheModels.Cache _ 
        NIL] RETURNS [cache: CacheModels.Cache] = {
            <<Creates a new cache on the specified shared memory.>>
            IF quadsPerLine > maxQuadsPerLine THEN quadsPerLine _ maxQuadsPerLine;
            IF lines > maxLines THEN lines _ maxLines;
            cache _ NEW[CacheModels.CacheRec _ [
                private: NEW[CacheDataRep[lines] _ [quadsPerLine: quadsPerLine, wordsPerQuad: wordsPerQuad, logWordsPerQuad: 
                LogBaseTwo[wordsPerQuad], realCache: realCache, mapCache: mapCache, lineTable: NULL]],
                fetch: Fetch, store: Store, reset: Reset, flush: Flush, print: Print, 
                data: NIL]];
            Reset[cache];
            };

        Reset: PUBLIC CacheModels.CacheResetProc -- [cache: CacheModels.Cache] --  = {
            <<Resets the given cache to its initial state (all empty).>>
            private: CacheData = NARROW[cache.private];
            private.pageList _ NIL;
            private.hashVector _ NEW[HashVectorRep _ ALL[NIL]];
            private.victimIndex _ 0;
            private.pageEntryCount _ 0;
            FOR i: NAT IN [0..private.linesInCache) DO
                private[i] _ NEW[HashEntryRep];
                ENDLOOP;
            private.stats _ []; -- zero out statistics
            IF private.realCache # NIL THEN private.realCache.reset[private.realCache];
            IF private.mapCache # NIL THEN private.mapCache.reset[private.mapCache];
            };

        Flush: PUBLIC CacheModels.CacheFlushProc -- [cache: CacheModels.Cache] --  = {
            <<Resets the given cache to its initial state (all empty).>>
            private: CacheData = NARROW[cache.private];
            private.pageList _ NIL;
            private.hashVector^ _ ALL[NIL];
            private.victimIndex _ 0;
            private.pageEntryCount _ 0;
            FOR i: NAT IN [0..private.linesInCache) DO
                private[i]^ _ [valid: FALSE];
                ENDLOOP;
            IF private.realCache # NIL THEN private.realCache.flush[private.realCache];
            IF private.mapCache # NIL THEN private.mapCache.flush[private.mapCache];
            };

        Print: PUBLIC CacheModels.CachePrintProc -- [cache: CacheModels.Cache, stream: STREAM, name: ROPE, resetStatistics: BOOL _ TRUE] -- 
         = {
            Realn: PROC [r: REAL, n: NAT] RETURNS [IO.Value] = {
                RETURN [[rope[Convert.RopeFromReal[r, n]]]]};
            private: CacheData = NARROW[cache.private];
            quadMisses: INT _ private.stats.chunkMisses;
            misses: INT _ quadMisses + private.stats.lineMisses;
            probes: INT _ private.stats.probes;
            rProbes: REAL _ probes;
            rMisses: REAL _ misses;
            stream.PutF[
                "\nStats for %g (directMap, lines: %g, quads/line: %g, words/quad: %g)\n  probes: %g",
                [rope[name]], 
                [integer[private.linesInCache]], [integer[private.quadsPerLine]], [integer[private.wordsPerQuad]], [integer[probes]]];
            IF probes = 0 THEN RETURN;
            stream.PutF[
                "  (read: %g, write: %g)\n",
                [integer[private.stats.readProbes]], [integer[private.stats.writeProbes]]];
            stream.PutF[
                "  write misses: %g, writes to clean quads: %g\n",
                [integer[private.stats.writeMisses]], [integer[private.stats.writeClean]]];
            stream.PutF[
                "  misses: %g (%g (%g%%) existing line)\n",
                [integer[misses]], [integer[private.stats.chunkMisses]], 
                IF misses = 0 THEN [rope["-"]] ELSE Realn[(quadMisses/rMisses)*100, 3]];
            IF private.stats.jumpMisses # 0 THEN stream.PutF[
                "  misses caused by jumps: %g (%g%% of probes)\n",
                [integer[private.stats.jumpMisses]], Realn[(private.stats.jumpMisses/rProbes)*100, 3]];
            IF probes # 0 THEN stream.PutF[
                "  miss rate: %g%%\n",
                Realn[(misses/rProbes)*100, 3]];
            stream.PutF[
                "  map misses: %g (%g%%)\n  dirty writes: %g\n",
                [integer[private.stats.mapMisses]], Realn[(private.stats.mapMisses/rProbes)*100, 3], [integer[private.stats.dirtyWrites]]];
            };

        Fetch: PUBLIC CacheModels.CacheFetchProc -- [cache: CacheModels.Cache, addr: DragOpsCross.Word, fromJump: BOOL _ FALSE] --  = {
            Access[cache, addr, fromJump, FALSE];
            };

        Store: PUBLIC CacheModels.CacheStoreProc -- [cache: CacheModels.Cache, addr: DragOpsCross.Word] --  = {
            Access[cache, addr, FALSE, TRUE];
            };

        Method: TYPE = {advanceOnMiss, shiftOnHit};
        method: Method _ advanceOnMiss;

        Access: PROC [cache: Cache, addr: Word, fromJump, write: BOOL] = {
            data: CacheData = NARROW[cache.private];
            wordsPerLine: NAT = data.quadsPerLine * data.wordsPerQuad;
            indexInLine: NAT = HalfToCard[LowHalf[addr]] MOD wordsPerLine;
            chunk: QuadIndex = Basics.BITSHIFT[indexInLine, -data.logWordsPerQuad];
            lineAddr: Word = AddDelta[-INT[indexInLine], addr];
            hashIndex: CARDINAL _ (HalfToCard[LowHalf[lineAddr]] / wordsPerLine) MOD data.linesInCache;
            hashEntry: HashEntry _ data.lineTable[hashIndex];
            indexInPage: CARDINAL = HalfToCard[LowHalf[lineAddr]] MOD wordsPerPage;
            pageAddr: Word = AddDelta[-INT[indexInPage], lineAddr];
            pageId: Word _ SingleWordShiftRight[pageAddr, CacheModels.logWordsPerPage];

            data.stats.probes _ data.stats.probes + 1;
            IF write THEN data.stats.writeProbes _ data.stats.writeProbes + 1 ELSE data.stats.readProbes _ data.stats.readProbes + 1;

            <<Check if the addressed quad is in the cache>>
            IF (hashEntry.lineAddr # lineAddr) OR ~ hashEntry.valid
                THEN { -- the quad's line itself is not in cache
                    IF fromJump THEN data.stats.jumpMisses _ data.stats.jumpMisses + 1;
                    data.stats.lineMisses _ data.stats.lineMisses + 1;
                    IF write THEN data.stats.writeMisses _ data.stats.writeMisses + 1;
                    data.stats.mapMisses _ data.stats.mapMisses+1;
                    IF data.mapCache # NIL THEN data.mapCache.fetch[data.mapCache, pageId];
                    <<>>
                    <<Write out any dirty entries>>
                    IF hashEntry.dirty # None THEN {
                        qi: QuadIndex;
                        FOR qi IN [0..data.quadsPerLine) DO
                            IF hashEntry.dirty[qi] THEN {
                                IF data.realCache # NIL THEN
                                    data.realCache.store[data.realCache, AddDelta[qi*data.wordsPerQuad, hashEntry.lineAddr]];
                                data.stats.dirtyWrites _ data.stats.dirtyWrites + 1;
                                };
                            ENDLOOP;
                        hashEntry.dirty _ None;
                        };

                    hashEntry.valid _ TRUE;
                    hashEntry.lineAddr _ lineAddr;
                    hashEntry.chunkPresent _ None; hashEntry.chunkPresent[chunk] _ TRUE;
                    IF data.realCache # NIL THEN data.realCache.fetch[data.realCache, addr];
                    }
                ELSE { -- check if quad is in
                    IF ~ hashEntry.chunkPresent[chunk] THEN {
                        IF fromJump THEN data.stats.jumpMisses _ data.stats.jumpMisses + 1;
                        data.stats.chunkMisses _ data.stats.chunkMisses + 1;
                        IF write THEN data.stats.writeMisses _ data.stats.writeMisses + 1;

                        hashEntry.chunkPresent[chunk] _ TRUE;
                        IF data.realCache # NIL THEN data.realCache.fetch[data.realCache, addr];
                        }
                    };

            hashEntry.referenced[chunk] _ TRUE;
            IF write THEN {
                IF NOT hashEntry.dirty[chunk] THEN data.stats.writeClean _ data.stats.writeClean + 1;
                hashEntry.dirty[chunk] _ TRUE;
                };
            };
        END.