MultiLevelTagLookup.bsv

Todones

rules/functions processing different states:

- Init: 
  - doLookup condition !Init
- Idle: 
  - Slave cache.request.canPut(), put(), 
  - doLookup condition !Idle
- ReadTag, SetTag, ClearTag:
  - used in doLookup
  - set in Slave cache.request.put(req)
- FoldZeroes:
  - used in doLookup
  - set in doLookup, 

rules triggered by getReq.send():

-> rule drainMemRsp: // done


rule doLookup:

-> ClearTags: 
   -> getOldTagsEntry() // done // do nothing if flat table.
   -> getReq.send() // done
   -> doTransition() // done

Slave:
-> request.put():
   -> craftTagReadReq() // done
      -> getTableAddr() // done
   -> read -> nextState = ReadTag -> rule doLookup // done
   -> write:
      -> nextState = Idle -> rule doLookup // done
      -> nextState = ClearTag -> rule doLookup // done
      -> nextState = SetTag -> rule doLookup // done
   -> set globals 
      - pendingCapNumber, used in rule doLookup, send this to functions getTableEntry(,,), getTableAddr(,), craftTagReadReq(,),craftTagWriteReq(,,,,), getNewTagsEntry(,),getOldTagsEntry(,,)    // todo
      - pendingTags, used in rule doLookup, send this to functions craftTagWriteReq(,,,,),getNewTagsEntry(,)  // todo
      - pendingCapEnable, used in rule doLookup, send this to functions craftTagWriteReq(,,,,),getNewTagsEntry(,,,,) // todo
    -> doTransition()
      -> tagCacheReq.enq(mr) // rule feedTagCache: forward from tagCacheReq to tagCache module // done
      -> useNextRsp.enq(useRsp) // used in rule drainMemRsp: drain unused response; used in rule doLookup condition: only if not full, doLookup will be triggered.
      -> state <= newState; // new state in effect.

-> response.get(): return lookupRsp.first // done.

Reference 1

Parameters:

  • ways = 4, keyBits is Indices - 1, inFlight = 1

  • cacheID = 12,

  • writeMissBehavior = WriteAllocate,

  • responseBehavior = ResponseAll,

  • orderBehavior = InOrder,

  • whichCache = TCache,

  • memReqFifoSpace = zeroExtend(mReqs.remaining()),

  • memReqs = ff2fifof(mReqs),

  • memRsps = ff2fifof(mRsps)

Return struct CheriTagResponse

// cherilibs/trunk/MultiLevelTagLookup.bsv

// interface types
///////////////////////////////////////////////////////////////////////////////

typedef Vector#(4,Bit#(CapsPerFlit)) LineTags;
typedef union tagged {
  void Uncovered;
  LineTags Covered;
} CheriTagResponse deriving (Bits,FShow);

Interfaces - TagLookupIfc

// cherilibs/trunk/MultiLevelTagLookup.bsv

interface TagLookupIfc;
  interface Slave#(CheriMemRequest, CheriTagResponse) cache;
  interface Master#(CheriMemRequest, CheriMemResponse) memory;
  `ifdef STATCOUNTERS
  interface Get#(ModuleEvents) cacheEvents;
  `endif
endinterface

same as in TagLookup.bsv

Internal Types

  • State: Init, Idle, ReadTag, SetTag, ClearTag, FoldZeroes
    • ReadTag,
    • SetTag,
    • ClearTag,
    • FoldZeroes,
    • Only handle one request a time; State will tell us which kind of operation the request has. The state is set during Slave request - put interface

Table Node Leaf

Node:

  • if node is 0, means all the tags under its covered addr range are 0s; This case will improve the search performance;
  • If node is 1, means at least one of tags under its covered addr is 1, then we will need to got to next level of node to search for tag values; This case will hurt the search performance.

Leaf: the tags for every address is stored and can be accessed directly. Usually it will contain non-zero tags.

  • TableEntry deriving(Bits)

    • Bool Node
    • LineTags Leaf; tags of 4 flits.

  • Tablelvl deriving(FShow)

    • CheriPhyAddr startAddr;
    • int size
    • int shiftAmnt;
    • int groupFactor;
    • int groupFactorLog;

  • TDepth: maximum table depth of 8;

state

Parameters/Instantiate

  • CheriMasterID mID, (= 12)
  • CheriPhyAddr tagTabEndAddr, (= 40’h4000_0000)
  • Vector#(tdepth, Integer) tableStructure, ( = ???, in TagTableStructure.bsv generated by tagsparams.py)
  • Integer memCoveredSize

Interface TagLookupIfc arguments:

  • ways = 4, keyBits is Indices - 1, inFlight = 1

  • cacheID = 12,

  • writeMissBehavior = WriteAllocate,

  • responseBehavior = ResponseAll,

  • orderBehavior = InOrder,

  • whichCache = TCache,

  • memReqFifoSpace = zeroExtend(mReqs.remaining()),

  • memReqs = ff2fifof(mReqs),

  • memRsps = ff2fifof(mRsps)

State Registers:

  • state,
  • zeroAddr, init as tagTabStrtAddr
  • transNum, transaction number for mem requests
  • currentDepth,
  • pendingCapNumber,
  • pendingTags,
  • pendingCapEnable

Vectors:

  • Vector#(tdepth, Tablelvl) tableDesc = genWith(lvlDesc)
    • call lvlDesc from 0 to tdepth - 1;
    • return values composes the Vector#
  • Vector#(tdepth, Reg#(Bit#(CheriDataWidth))) oldTags

FIFOs:

  • readReqs
  • lookupRsp
  • mReqs
  • mRsps
  • useNextRsp
  • tagCacheReq
  • PulseWire getReq <- mkPulseWire(); // ??

Submodules:

  • CacheCore#(4, TSub#(Indices, 1), 1) tagCache <- mkCacheCore(12, WriteAllocate, RespondAll, InOrder, TCache, zeroExtend(mReqs.remaining()), ff2fifof(mReqs), ff2fifof(mRsps));

CacheCore instance

// cherilibs/trunk/MultiLevelTagLookup.bsv:

// tag cache CacheCore module

CacheCore#(4, TSub#(Indices, 1), 1)  tagCache <- mkCacheCore(
    12, WriteAllocate, RespondAll, InOrder, TCache,
    zeroExtend(mReqs.remaining()), ff2fifof(mReqs), ff2fifof(mRsps));


// cherilibs/trunk/CacheCore.bsv:

module mkCacheCore#(Bit#(16) cacheId, 
                    WriteMissBehaviour writeBehaviour, 
                    ResponseBehaviour responseBehaviour,
                    OrderBehaviour orderBehaviour,
                    WhichCache whichCache,
                    // Must be > 5 or we can't issue reads with evictions!
                    // This means that a write-allocate cache must have >=5 capacity in the output fifo.
                    Bit#(10) memReqFifoSpace,
                    FIFOF#(CheriMemRequest) memReqs,
                    FIFOF#(CheriMemResponse) memRsps)
                   (CacheCore#(ways, keyBits, inFlight))

Functions

  • function TableLvl lvlDesc(Integer d);
  • function Bool isCovered(CheriPhyAddr addr);
  • function CheriPhyBitAddr getTableAddr(TDepth cd, CapNumber cn);
  • function TableEntry getTableEntry(TDepth cd, CapNumber cn, Bit#(CheriDataWidth) tags);
  • function Bit#(CheriDataWidth) getOldTagsEntry(TDepth cd, CapNumber cn, Bit#(CheriDataWidth) tags);
  • function Bit#(CheriDataWidth) getNewTagsEntry(…);
  • function CheriMemRequest craftTagReadReq(TDepth d, CapNumber cn);
  • function CheriMemRequest craftTagWriteReq(…);
  • function Action doTransition(…);

function getOldTagsEntry

Overview: when table only have one level, it does no transformation to tags, and will return the input as output

function getTableEntry

function craftTagWriteReq

function doTransition

Overview: put memory request in the fifo so it will be fed to tagCache, at the same time, put a bool switch useRsp to flag whether the response will be ignored or not in rule doLookup;

// file: cherilibs/trunk/MultiLevelTagLookup.bsv

function Action doTransition (
    Maybe#(CheriMemRequest) mmr, // Contains one valid bit, and then request.
    TDepth newDepth,
    State newState,
    Bool useRsp
    ) = action
    debug2("taglookup",
      $display("<time %0t TagLookup> table structure -", $time, fshow(tableDesc)
    ));

    case (mmr) matches
      tagged Valid .mr: begin
        // send the tag cache request and increment the transaction number
        debug2("taglookup",
          $display("<time %0t TagLookup> sending lookup: ",
          $time, fshow(mr)
        ));
        tagCacheReq.enq(mr);
        useNextRsp.enq(useRsp);
        transNum <= transNum + 1;
      end
    endcase
    // update lookup depth
    currentDepth <= newDepth;
    // do state transistion
    state <= newState;
    debug2("taglookup",
      $display("<time %0t TagLookup> pendingCapNumber %x, currentDepth %d -> %d, state ",
      $time, pendingCapNumber, currentDepth, newDepth, fshow(state), " -> ", fshow(newState)
    ));
  endaction;

If a valid memory request, send the cache request and increment the transaction number

  • tagCacheReq.enq(mr); // request will then be fed to tagCache.put(tagCacheReq.first())
  • useNextRsp.enq(useRsp); // whether this request will have a response being parsed in rule doLookup. ???
  • transNum <= transNum + 1;

Rules

  • rule feedTagCache;
  • rule initialise (state == Init);
  • rule stuffCommits;
  • rule drainMemRsp(…)
  • rule doLookup(…)

rule doLookup

Overview: lookup the multi level table

By default only one-level table is used. That is all nodes are leaf nodes.

TODO: where does the read response generated?

Check the current state

  • Check current state

  • if ReadTag: check the table entry’s union type

    • If Node type entry: check Node value for short cut (all 0 tags), or go to next level table entry by calling craftTagReadReq //
    • If Leaf type entry: enqueue lookupRsp the leaf LineTags, where the first bit is the start of the requested capNumber’s flit’s tags.
    • getReq.send() // drain unused memory response (for unused write responses)
    • doATransition = True // will call doTransition() to put request to tagCache, the request can be invalid.

  • if SetTag:

    • Only triggered when memRspReady meaning the memory content to be written has been loaded from memory into the tagCache.
    • If Node ….
    • If Leaf table entry: set state to Idle; // already done write???
    • getReq.send() // drain unused memory response (for unused write responses)
    • doATransition = True // will call doTransition() to put request to tagCache

  • if ClearTag:

    • only triggered when memRspReady, meaning the memory is loaded into the cache already;
    • get all the tags: getOldTagsEntry(dpth,capNumber,rspData) // todo
    • if Node table entry …
    • if Leaf table entry:
      • craft a tag write memory request
      • set state to Idle
    • getReq.send() // drain unused memory response (for unused write responses)
    • doATransition = True // will call doTransition() to put request to tagCache

  • if FoldZeroes …

  • doTransition(): put mem request to tagCache

Interface - Slave

interface Slave cache; two subinterfaces

  • interface CheckedPut request;
  • interface CheckedGet response;

Slave - request

  • Bool canPut() = (state == Idle); // only can receive request when Idle

  • Action put(CheriMemRequest req) if (state == Idle); // only when Idle

The put method, in steps:

  • doTagLookup = isCovered(req.addr);
  • newPendingTags: temporal store number of tags in a flit;
  • newPendingCapEnable: temporal store enable bits for each cap in a flit;
  • create a mem request to initialise a toplevel table lookup.
    • CheriMemRequest mReq = craftTagReadReq(rootLvl, capAddr.capNumber)
  • if read: read tags:
    • readReqs.enq(doTagLookup);
    • nextState = ReadTag; // will trigger code only in rule doLookup
  • if write: write tags:
    • use capEnable to mask the cap bits to be written in a flit;
    • get capTags from the request;
    • compute bool vector andTags = capEnable & newPendingTags;
    • check capEnable: set to IDLE if all disabled, i.e. no write ops;
    • check andTags: if all 0, mean all tag to write is 0, then set to ClearTag state. // Lele: we might use similar solution to initialize color tags in scale.
    • if has at least one non-zero tag, craft a tag write memory request and set next state as SetTag
  • set globals
    • pendingCapNumber <= capAddr.capNumber; // the cap aligned address
    • pendingTags <= newPendingTags; // tags to be written, 0 if read;
    • pendingCapEnable <= newPendingCapEnable; // enabled cap bits to be written, 0 if read.
  • call doTransition(tagged Valid mReq, rootLvl, nextState, True)
    • put mReq to tagCache: tagCacheReq.enq(mr);
    • put one bool in fifo: useNextRsp.enq(useRsp);
    • trigger rules by change state to newState

Slave - response

The get method, for tagController to get response from here. Returned struct is CheriTagResponse, a tagged union, contain LineTags tagged as Covered as valid type; LineTags is a vector of tags in 4*flits width (every bit is a tag)

The get() steps:

  • condition: !readReqs.first() || lookupRsp.notEmpty()
    • no read request in queue (not covered?) or
    • has a response in queue
  • if readReq.first(), meaning the request addr is covered (valid), grab the rsp from fifo and return CheriTagResponse tr = tagged Covered lookupRsp.first();
  • if readReq.first() is not true, an invalid addr (not covered), return invalid response (CheriTagResponse tr = tagged Uncovered;)

Interface - Master

interface Master memory; two subinterfaces

  • interface request = toCheckedGet(ff2fifof(mReqs));
  • interface response = toCheckedPut(ff2fifof(mRsps));

Physical Memory Region

// Constant physical memory region

// file: cherilibs/trunk/MultiLevelTagLoopup.bsv

// static parameters
/////////////////////////////////////////////////////////////////////////////

// covered region include DRAM and BROM
// starting address of the covered region
CheriPhyAddr coveredStrtAddr = unpack(40'h00000000);
// ending address of the covered region
CheriPhyAddr coveredEndAddr  = unpack(40'h40010000); // Lele: 1GB + 64KB. Why 64KB here?
// tagd table is at top of DRAM
// starting address of the tags table
CheriPhyAddr tagTabStrtAddr  = unpack(40'h3F000000);
  1. reference ↩
Created May 8, 2020 // Last Updated May 18, 2021

If you could revise
the fundmental principles of
computer system design
to improve security...

... what would you change?