cache/tags/fa_lru.cc

/*
 * Copyright (c) 2013,2016-2017 ARM Limited
 * All rights reserved.
 *
 * The license below extends only to copyright in the software and shall
 * not be construed as granting a license to any other intellectual
 * property including but not limited to intellectual property relating
 * to a hardware implementation of the functionality of the software
 * licensed hereunder.  You may use the software subject to the license
 * terms below provided that you ensure that this notice is replicated
 * unmodified and in its entirety in all distributions of the software,
 * modified or unmodified, in source code or in binary form.
 *
 * Copyright (c) 2003-2005 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Erik Hallnor
 */

/**
 * @file
 * Definitions a fully associative LRU tagstore.
 */

#include "mem/cache/tags/fa_lru.hh"

#include <cassert>
#include <sstream>

#include "base/intmath.hh"
#include "base/logging.hh"

FALRU::FALRU(const Params *p)
    : BaseTags(p), cacheBoundaries(nullptr)
{
    if (!isPowerOf2(blkSize))
        fatal("cache block size (in bytes) `%d' must be a power of two",
              blkSize);
    if (!isPowerOf2(size))
        fatal("Cache Size must be power of 2 for now");

    // Track all cache sizes from 128K up by powers of 2
    numCaches = floorLog2(size) - 17;
    if (numCaches > 0){
        cacheBoundaries = new FALRUBlk *[numCaches];
        cacheMask = (ULL(1) << numCaches) - 1;
    } else {
        cacheMask = 0;
    }

    blks = new FALRUBlk[numBlocks];
    head = &(blks[0]);
    tail = &(blks[numBlocks-1]);

    head->prev = nullptr;
    head->next = &(blks[1]);
    head->inCache = cacheMask;
    head->data = &dataBlks[0];

    tail->prev = &(blks[numBlocks-2]);
    tail->next = nullptr;
    tail->inCache = 0;
    tail->data = &dataBlks[(numBlocks-1)*blkSize];

    unsigned index = (1 << 17) / blkSize;
    unsigned j = 0;
    int flags = cacheMask;
    for (unsigned i = 1; i < numBlocks - 1; i++) {
        blks[i].inCache = flags;
        if (i == index - 1){
            cacheBoundaries[j] = &(blks[i]);
            flags &= ~ (1<<j);
            ++j;
            index = index << 1;
        }
        blks[i].prev = &(blks[i-1]);
        blks[i].next = &(blks[i+1]);
        blks[i].set = 0;
        blks[i].way = i;

        // Associate a data chunk to the block
        blks[i].data = &dataBlks[blkSize*i];
    }
    assert(j == numCaches);
    assert(index == numBlocks);
    //assert(check());
}

FALRU::~FALRU()
{
    if (numCaches)
        delete[] cacheBoundaries;

    delete[] blks;
}

void
FALRU::regStats()
{
    BaseTags::regStats();
    hits
        .init(numCaches+1)
        .name(name() + ".falru_hits")
        .desc("The number of hits in each cache size.")
        ;
    misses
        .init(numCaches+1)
        .name(name() + ".falru_misses")
        .desc("The number of misses in each cache size.")
        ;
    accesses
        .name(name() + ".falru_accesses")
        .desc("The number of accesses to the FA LRU cache.")
        ;

    for (unsigned i = 0; i <= numCaches; ++i) {
        std::stringstream size_str;
        if (i < 3){
            size_str << (1<<(i+7)) <<"K";
        } else {
            size_str << (1<<(i-3)) <<"M";
        }

        hits.subname(i, size_str.str());
        hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
        misses.subname(i, size_str.str());
        misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
    }
}

FALRUBlk *
FALRU::hashLookup(Addr addr) const
{
    tagIterator iter = tagHash.find(addr);
    if (iter != tagHash.end()) {
        return (*iter).second;
    }
    return nullptr;
}

void
FALRU::invalidate(CacheBlk *blk)
{
    BaseTags::invalidate(blk);

    // Move the block to the tail to make it the next victim
    moveToTail((FALRUBlk*)blk);

    // Erase block entry in the hash table
    tagHash.erase(blk->tag);
}

CacheBlk*
FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
{
    return accessBlock(addr, is_secure, lat, 0);
}

CacheBlk*
FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
{
    accesses++;
    int tmp_in_cache = 0;
    Addr blkAddr = blkAlign(addr);
    FALRUBlk* blk = hashLookup(blkAddr);

    if (blk && blk->isValid()) {
        // If a cache hit
        lat = accessLatency;
        // Check if the block to be accessed is available. If not,
        // apply the accessLatency on top of block->whenReady.
        if (blk->whenReady > curTick() &&
            cache->ticksToCycles(blk->whenReady - curTick()) >
            accessLatency) {
            lat = cache->ticksToCycles(blk->whenReady - curTick()) +
            accessLatency;
        }
        assert(blk->tag == blkAddr);
        tmp_in_cache = blk->inCache;
        for (unsigned i = 0; i < numCaches; i++) {
            if (1<<i & blk->inCache) {
                hits[i]++;
            } else {
                misses[i]++;
            }
        }
        hits[numCaches]++;
        if (blk != head){
            moveToHead(blk);
        }
    } else {
        // If a cache miss
        lat = lookupLatency;
        blk = nullptr;
        for (unsigned i = 0; i <= numCaches; ++i) {
            misses[i]++;
        }
    }
    if (inCache) {
        *inCache = tmp_in_cache;
    }

    //assert(check());
    return blk;
}


CacheBlk*
FALRU::findBlock(Addr addr, bool is_secure) const
{
    Addr blkAddr = blkAlign(addr);
    FALRUBlk* blk = hashLookup(blkAddr);

    if (blk && blk->isValid()) {
        assert(blk->tag == blkAddr);
    } else {
        blk = nullptr;
    }
    return blk;
}

CacheBlk*
FALRU::findBlockBySetAndWay(int set, int way) const
{
    assert(set == 0);
    return &blks[way];
}

CacheBlk*
FALRU::findVictim(Addr addr)
{
    return tail;
}

void
FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
{
    FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk);

    // Make sure block is not present in the cache
    assert(falruBlk->inCache == 0);

    // Do common block insertion functionality
    BaseTags::insertBlock(pkt, blk);

    // New block is the MRU
    moveToHead(falruBlk);

    // Insert new block in the hash table
    tagHash[falruBlk->tag] = falruBlk;

    //assert(check());
}

void
FALRU::moveToHead(FALRUBlk *blk)
{
    // If block is not already head, do the moving
    if (blk != head) {
        // Get all caches that this block does not reside in
        int updateMask = blk->inCache ^ cacheMask;

        // Update boundaries for all cache sizes
        for (unsigned i = 0; i < numCaches; i++){
            // If block has been moved to a place before this boundary,
            // all blocks in it will be pushed towards the LRU position,
            // making one leave the boundary
            if ((1U<<i) & updateMask) {
                cacheBoundaries[i]->inCache &= ~(1U<<i);
                cacheBoundaries[i] = cacheBoundaries[i]->prev;
            // If the block resides exactly at this boundary, the previous
            // block is pushed to its position
            } else if (cacheBoundaries[i] == blk) {
                cacheBoundaries[i] = blk->prev;
            }
        }

        // Make block reside in all caches
        blk->inCache = cacheMask;

        // If block is tail, set previous block as new tail
        if (blk == tail){
            assert(blk->next == nullptr);
            tail = blk->prev;
            tail->next = nullptr;
        // Inform block's surrounding blocks that it has been moved
        } else {
            blk->prev->next = blk->next;
            blk->next->prev = blk->prev;
        }

        // Swap pointers
        blk->next = head;
        blk->prev = nullptr;
        head->prev = blk;
        head = blk;
    }
}

void
FALRU::moveToTail(FALRUBlk *blk)
{
    // If block is not already tail, do the moving
    if (blk != tail) {
        // Update boundaries for all cache sizes
        for (unsigned i = 0; i < numCaches; i++){
            // If block has been moved to a place after this boundary,
            // all blocks in it will be pushed towards the MRU position,
            // making one enter the boundary
            if ((1U<<i) & blk->inCache) {
                // If the first block after the boundary is the block,
                // get its successor
                if (cacheBoundaries[i]->next == blk){
                    cacheBoundaries[i] = cacheBoundaries[i]->next->next;
                } else {
                    cacheBoundaries[i] = cacheBoundaries[i]->next;
                }
                cacheBoundaries[i]->inCache |= (1U<<i);
            }
        }

        // Make block reside in the last cache only
        blk->inCache = 0;

        // If block is head, set next block as new head
        if (blk == head){
            assert(blk->prev == nullptr);
            head = blk->next;
            head->prev = nullptr;
        // Inform block's surrounding blocks that it has been moved
        } else {
            blk->prev->next = blk->next;
            blk->next->prev = blk->prev;
        }

        // Swap pointers
        blk->prev = tail;
        blk->next = nullptr;
        tail->next = blk;
        tail = blk;
    }
}

bool
FALRU::check()
{
    FALRUBlk* blk = head;
    int tot_size = 0;
    int boundary = 1<<17;
    int j = 0;
    int flags = cacheMask;
    while (blk) {
        tot_size += blkSize;
        if (blk->inCache != flags) {
            return false;
        }
        if (tot_size == boundary && blk != tail) {
            if (cacheBoundaries[j] != blk) {
                return false;
            }
            flags &=~(1 << j);
            boundary = boundary<<1;
            ++j;
        }
        blk = blk->next;
    }
    return true;
}

FALRU *
FALRUParams::create()
{
    return new FALRU(this);
}