CacheCore.bsv

Q&A

  • Does it treat the memory tags read/write request differently?

    • no. tag read/write can only be distinguished by masterID. However, master ID does not change the logic routines in CacheCore. CacheCore only transfer this master ID from request to response.

  • Who calls this and what is the input?

    • DCache
    • calls this to send request and get response via core.put(CheriMemRequest reqIn) and core.response.get
    • init: CacheCore#(4, TSub#(Indices,1), 1) core <- mkCacheCore(cacheId, wmb, RespondAll, InOrder, DCache, zeroExtend(memReqs.remaining()), ff2fifof(memReqs), memRsps);
    • ICache
    • calls this to send request and get response via core.put(CheriMemRequest mem_req) and core.response.get()
    • init: CacheCore#(2, Indices, 1) core <- mkCacheCore(cacheId, WriteThrough, OnlyReadResponses, InOrder, ICache,zeroExtend(memReqs.remaining()), ff2fifof(memReqs), ff2fifof(memRsps));
    • L2Cache
    • calls this to send request to and get response from CacheCore via
      • core.put(CheriMemRequest cmr)
      • CheriMemResponse unused <- core.response.get(); and CheriMemResponse resp = core.response.peek();
    • init: CacheCore#(4, TAdd#(Indices, 2), 4) core <- mkCacheCore(8, WriteAllocate, RespondAll, InOrder, L2,zeroExtend(memReqs.remaining()),ff2fifof(memReqs), ff2fifof(memRsps));
    • TagCache
    • send request: core.put(CheriMemRequest tabReq);
    • get response: CheriMemResponse memResp <- core.response.get();
    • init: CacheCore#(4, TSub#(Indices, 1), 1) core <- mkCacheCore(12, WriteAllocate, OnlyReadResponses, InOrder, TCache, zeroExtend(tabReqs.remaining()), ff2fifof(tabReqs), ff2fifof(tabRsps));
    • MultiLevelTagLookup
    • init: ``
    • TagLookup
    • init: ``

  • Where does it go?

    • From request goes to:
    • next level request
    • sending response back
    • Multilevel reused Interfaces: goes to theMemMerge.slave[1], then l2Cache, in Memory.bsv:
    • mkConnection(dCache.memory, theMemMerge.slave[1]);
    • mkConnection(theMemMerge.merged, l2Cache.cache);

  • How does CacheCore handles that tag?

    • How to change number of bits?
    • Where does it check tags at runtime?
    • Can we gather & check multiple contigous bits at sametime?
    • See TagController.bsv

File: cherilibs/trunk/CacheCore.bsv

Note from source code:

The CacheCore module is a generic cache engine that is parameterisable by number of sets, number of ways, number of outstanding request, and selectable write-allocate or write-through behaviours. In addition, if the cache core is used as a level1 cache (ICache or DCache) it will return the 64-bit word requested in the bottom of the data field.

Return 64-bit word requested in the bottom of the data field.

Parameters and Provisos

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)) provisos ( Bits#(CheriPhyAddr, paddr_size), // CheriPhyAddr can be cast to/from Bit#(paddr_size), that is 40-bit addr. ifdef MEM128 // The line size is different for each bus width. Log#(64, offset_size), elsif MEM64 Log#(32, offset_size), else Log#(128, offset_size), endif Add#(TAdd#(offset_size, keyBits), tagBits, paddr_size), // Lele: offset_size + keyBits + tagBits = paddr_size = 40 bit addr. Add#(smaller1, TLog#(ways), keyBits), Add#(smaller2, TLog#(ways), tagBits), Add#(smaller3, tagBits, 30), Add#(0, TLog#(TMin#(TExp#(keyBits), 16)), wayPredIndexSize), Add#(smaller4, wayPredIndexSize, keyBits), Add#(smaller5, 4, keyBits), Add#(a__, TAdd#(TLog#(inFlight), 1), 8), Bits#(CacheAddress#(keyBits, tagBits), 40) );

Cache Basics

Cache basics: Cache Basics

  • cache line: also cache block. The basic unit for cache storage. May contain multiple bytes/words of data. Not the same thing as “row” of cache.
  • cache set: A “row” in the cache. The number of blocks/lines per set is determined by the layout of the cache (e.g. direct mapped, set-associate, or fully associate)
  • tag: a unique identifier for a group of data. Because different regions of memory may be mapped into a block, the tag is used to differentiate between them.
  • valid bit: a bit of information that indicates whether the data in a block is valid(1) or not(0).

A divisioin of address for cache use:

-------------------------------------------------------------
| -------- tag --------- | --- set index --- | block offset |
-------------------------------------------------------------
         t bits                  s bits             b bits

Bytes vs Word (vs Bits) Addressing format: the design need to be consistent with the block size and requested address format.

structs

CacheAddress#


// cherilibs/trunk/CacheCore.bsv

typedef Bit#(tagBits) Tag#(numeric type tagBits);
typedef Bit#(keyBits) Key#(numeric type keyBits);
typedef 2 BankBits;
typedef Bit#(BankBits)     Bank;
typedef CheriPhyByteOffset Offset;

typedef struct {
  Tag#(tagBits)    tag;
  Key#(keyBits)    key;
  Bank            bank;
  Offset        offset;  // Lele: an offset between [0, CheriBusBytes]
} CacheAddress#(numeric type keyBits, numeric type tagBits) deriving (Bits, Eq, Bounded, FShow);

TagLine#


typedef struct {
  Tag#(tagBits)                     tag;
  Bool                          pendMem;
  Bool                            dirty;
  Vector#(TExp#(BankBits), Bool)  valid;
} TagLine#(numeric type tagBits) deriving (Bits, Eq, Bounded, FShow);

see more type def

interface CacheCore

methods

  • Bool canPut();
  • Action put(CheriMemRequest req);
  • CheckedGet#(CheriMemResponse) response();
  • Action nextWillCommit(Bool nextCommitting);
  • Action invalidate (CheriPhyAddr addr);
  • ActionValue#(bool) invalidateDone();

method put()

method Action put(CheriMemRequest req) if (putCondition);

condition putCondition

steps:

  • unpack request address: CacheAddress#(keyBits, tagBits) ca = unpack(pack(req.addr));
  • get request id: ReqId id = getReqId(req);
  • put id to fifo next (or nextSet for OOO)
    • at the same time: update newReq as this req;
    • nextIncomingReqId to be the next one after this req: nextIncomingReqId <= ReqId{masterID: id.masterID, transactionID: id.transactionID + 1};

CapTag in Cache Read/Write

defined in rule finishLookup: L545 ~ 1536

TODO

Source: Type definitions

// cherilibs/trunk/CacheCore.bsv

typedef Bit#(tagBits) Tag#(numeric type tagBits);
typedef Bit#(keyBits) Key#(numeric type keyBits);
typedef 2 BankBits;
typedef Bit#(BankBits)     Bank;
typedef CheriPhyByteOffset Offset; 

typedef struct {
  Tag#(tagBits)    tag;
  Key#(keyBits)    key;
  Bank            bank;
  Offset        offset;
} CacheAddress#(numeric type keyBits, numeric type tagBits) deriving (Bits, Eq, Bounded, FShow);
typedef Bit#(TLog#(ways)) Way#(numeric type ways);


typedef struct {
  Key#(keyBits) key;
  Bank          bank;
} DataKey#(numeric type ways, numeric type keyBits) deriving (Bits, Eq, Bounded, FShow);

typedef struct {
  CheriTransactionID id;
  Bool           commit;
} CacheCommit deriving (Bits, Eq, Bounded, FShow);

typedef struct {
  Tag#(tagBits)                     tag;
  Bool                          pendMem;
  Bool                            dirty;
  Vector#(TExp#(BankBits), Bool)  valid;
} TagLine#(numeric type tagBits) deriving (Bits, Eq, Bounded, FShow);

typedef enum {Init, Serving} CacheState deriving (Bits, Eq, FShow);
typedef enum {Serve, Writeback, MemResponse} LookupCommand deriving (Bits, Eq, FShow);

typedef enum {WriteThrough, WriteAllocate}   WriteMissBehaviour deriving (Bits, Eq, FShow);
typedef enum {OnlyReadResponses, RespondAll} ResponseBehaviour deriving (Bits, Eq, FShow);
typedef enum {InOrder, OutOfOrder} OrderBehaviour deriving (Bits, Eq, FShow);

typedef struct {
  CacheAddress#(keyBits, tagBits) addr;
  TagLine#(tagBits)                tag;
  Way#(ways)                       way;
  Bool                          cached;
  ReqId                          reqId;
} AddrTagWay#(numeric type ways, numeric type keyBits, numeric type tagBits) deriving (Bits, FShow);

typedef struct {
  Tag#(tagBits)                    tag;
  Key#(keyBits)                    key;
  Way#(ways)                       way;
  Bool                           valid;
} InvalidateToken#(numeric type ways, numeric type keyBits, numeric type tagBits) deriving (Bits, FShow);

typedef struct {
  LookupCommand                               command;
  CheriMemRequest                                 req; // Original request that triggered the lookup.
  CacheAddress#(keyBits, tagBits)                addr; // Byte address of the frame that was fetched.
  BytesPerFlit                              readWidth; // Latch read width for speed, in case it is a read.
  DataKey#(ways, keyBits)                     dataKey; // Datakey used in the fetch (which duplicates some of addr and adds the way).
  Way#(ways)                                      way;
  Bool                                           last;
  Bool                                          fresh;
  InvalidateToken#(ways, keyBits, tagBits) invalidate; // Token containing any invalidate request
  Error                                      rspError;
} ControlToken#(numeric type ways, numeric type keyBits, numeric type tagBits) deriving (Bits, FShow);

typedef struct {
  CheriMemResponse     resp;
  CheriMemRequest       req; // Request to potentially enq into retryReqs.
  Bank              rspFlit;
  Maybe#(ReqId)       rspId;
  Bool              deqNext;
  ReqId               deqId;
  Bool        deqReqCommits;
  Bool          enqRetryReq;
  Bool         deqRetryReqs;
} ResponseToken deriving (Bits, FShow);

function ReqId getReqId(CheriMemRequest req);
  //Bool reqWrite = False;
  //if (req.operation matches tagged Write .wop) reqWrite = True;
  return ReqId{masterID: req.masterID, transactionID: req.transactionID};
endfunction

function ReqId getRespId(CheriMemResponse resp);
  //Bool respWrite = False;
  //if (resp.operation matches tagged Write .wop) respWrite = True;
  return ReqId{masterID: resp.masterID, transactionID: resp.transactionID};
endfunction

typedef struct {
  Key#(keyBits)                       key;
  ReqId                              inId;
  Bool                             cached;
  Vector#(ways,TagLine#(tagBits)) oldTags;
  Way#(ways)                       oldWay;
  Bool                           oldDirty;
  Bool                              write;
  Bank                          noOfFlits;
} RequestRecord#(numeric type ways, numeric type keyBits, numeric type tagBits) deriving (Bits, Eq, FShow);

typedef struct {
  Bank first;
  Bank last;
} BankBurst deriving (Bits, Eq, FShow);

typedef struct {
  ReqId inId;
  Bool isSC;
  Bool scResult;
} ReqIdWithSC deriving (Bits, Eq, FShow);

typedef struct {
  Bool                            doWrite;
  Key#(keyBits)                       key;
  Vector#(ways,TagLine#(tagBits)) newTags;
} TagUpdate#(numeric type ways, numeric type keyBits, numeric type tagBits) deriving (Bits, Eq, FShow);

typedef Vector#(TDiv#(CheriDataWidth,8), Bool) ByteEnable;

Reference 1

  1. github/beri ↩
Created May 5, 2020 // Last Updated May 23, 2020

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

... what would you change?