零零散散记录看缓存替换算法源代码时，看到的一些能够和平时理论对应上，并能够加以解释的部分源代码。

  1. gem5/src/mem/cache/tags/base_set_assoc.hh路径下的CacheBlk* findVictim(Addr addr) override{}函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
     * Find an invalid block to evict for the address provided.
     * If there are no invalid blocks, this will return the block
     * in the least-recently-used position.
     * @param addr The addr to a find a replacement candidate for.
     * @return The candidate block.
     */
    CacheBlk* findVictim(Addr addr) override
    {
        BlkType *blk = nullptr;
        int set = extractSet(addr);

        // prefer to evict an invalid block
        for (int i = 0; i < allocAssoc; ++i) {
            blk = sets[set].blks[i];
            if (!blk->isValid())
                break;
        }

        return blk;
    }

参数为一个地址，findVictim函数需要为该地址找到一个无效块踢出，如果没有无效块的话，将淘汰优先级最高位置的块踢出去。函数主体部分，首先对参数地址进行解析，得到该地址所属的set，sets与blks为按照缓存替换算法规则进行过排序的地址对应的sets和blks。

以LRU算法为例：

比如说在L1与L2之间的缓存替换中，数据访问请求的数据块A不在L1中，L1缺失，此时在L2中找到数据块A，对应的地址为addr，该地址在L2中对应的组号为set，把数据块A从L2调入L1，L1中是否有位置？需要找一个位置给数据块A，这个位置就是受害者。遍历L2的set对应位置的组sets下的块，若L1该组sets未满，直到遍历到!isValid的块位置，为受害者，若L1该组sets满了，块位置一直isValid，则一直遍历直到最后一个数据块blks[allocAssoc]，即最久未被使用的块，作为受害者被淘汰出去，其实就是该位置的数据被替换掉。

这是因为blks数组中的块已经在函数accessBlock()中按照LRU算法，在moveToHead()函数的作用下，不断交换位置，最后blks[0]表示最近刚刚使用过的块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 /**
     * Insert the new block into the cache.
     * @param pkt Packet holding the address to update
     * @param blk The block to update.
     */
 //pkt为新块包，blk为要淘汰的旧块

     void insertBlock(PacketPtr pkt, CacheBlk *blk) override
     {
     //根据新块包pkt获取新块的地址以及包请求的masterID与taskID

         Addr addr = pkt->getAddr();
         MasterID master_id = pkt->req->masterId();
         uint32_t task_id = pkt->req->taskId();
//如果旧块没有被touch过，那么可以被touch并标记为istouch
         if (!blk->isTouched) {
             tagsInUse++;
             blk->isTouched = true;
             if (!warmedUp && tagsInUse.value() >= warmupBound) {
                 warmedUp = true;
                 warmupCycle = curTick();
             }
         }

         // If we're replacing a block that was previously valid update
         // stats for it. This can't be done in findBlock() because a
         // found block might not actually be replaced there if the
         // coherence protocol says it can't be.
//如果blk旧块为isValid，好像意思就是该块不为空，一系列操作后标记blk
//为invalidate，lru.cc中还将其移到淘汰优先级队列末位，下一步马上被淘汰，并且为isTouched。
         if (blk->isValid()) {
lru.cc中还将其移到淘汰优先级队列末位，下一步马上被淘汰，并且为isTouched。
         if (blk->isValid()) {
             replacements[0]++;
             totalRefs += blk->refCount;
             ++sampledRefs;
             blk->refCount = 0;

             // deal with evicted block
             assert(blk->srcMasterId < cache->system->maxMasters());
             occupancies[blk->srcMasterId]--;

             blk->invalidate();
         }

         blk->isTouched = true;

         // Set tag for new block.  Caller is responsible for setting status.
         blk->tag = extractTag(addr);

         // deal with what we are bringing in
         assert(master_id < cache->system->maxMasters());
         occupancies[master_id]++;
         blk->srcMasterId = master_id;
         blk->task_id = task_id;
         blk->tickInserted = curTick();

         // We only need to write into one tag and one data block.
         tagAccesses += 1;
         dataAccesses += 1;
     }