/*
* Copyright (c) 2012-2013, 2015-2016 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
* Andreas Sandberg
* Andreas Hansson
*/
/** @file
* Declaration of a high-level queue structure
*/
#ifndef __MEM_CACHE_QUEUE_HH__
#define __MEM_CACHE_QUEUE_HH__
#include <cassert>
#include "base/trace.hh"
#include "debug/Drain.hh"
#include "mem/cache/queue_entry.hh"
#include "sim/drain.hh"
/**
* A high-level queue interface, to be used by both the MSHR queue and
* the write buffer.
*/
template<class Entry>
class Queue : public Drainable
{
protected:
/** Local label (for functional print requests) */
const std::string label;
/**
* The total number of entries in this queue. This number is set
* as the number of entries requested plus any reserve. This
* allows for the same number of effective entries while still
* maintaining an overflow reserve.
*/
const int numEntries;
/**
* The number of entries to hold as a temporary overflow
* space. This is used to allow temporary overflow of the number
* of entries as we only check the full condition under certain
* conditions.
*/
const int numReserve;
/** Actual storage. */
std::vector<Entry> entries;
/** Holds pointers to all allocated entries. */
typename Entry::List allocatedList;
/** Holds pointers to entries that haven't been sent downstream. */
typename Entry::List readyList;
/** Holds non allocated entries. */
typename Entry::List freeList;
typename Entry::Iterator addToReadyList(Entry* entry)
{
if (readyList.empty() ||
readyList.back()->readyTime <= entry->readyTime) {
return readyList.insert(readyList.end(), entry);
}
for (auto i = readyList.begin(); i != readyList.end(); ++i) {
if ((*i)->readyTime > entry->readyTime) {
return readyList.insert(i, entry);
}
}
assert(false);
return readyList.end(); // keep stupid compilers happy
}
/** The number of entries that are in service. */
int _numInService;
/** The number of currently allocated entries. */
int allocated;
public:
/**
* Create a queue with a given number of entries.
*
* @param num_entries The number of entries in this queue.
* @param reserve The extra overflow entries needed.
*/
Queue(const std::string &_label, int num_entries, int reserve) :
label(_label), numEntries(num_entries + reserve),
numReserve(reserve), entries(numEntries), _numInService(0),
allocated(0)
{
for (int i = 0; i < numEntries; ++i) {
freeList.push_back(&entries[i]);
}
}
bool isEmpty() const
{
return allocated == 0;
}
bool isFull() const
{
return (allocated >= numEntries - numReserve);
}
int numInService() const
{
return _numInService;
}
/**
* Find the first WriteQueueEntry that matches the provided address.
* @param blk_addr The block address to find.
* @param is_secure True if the target memory space is secure.
* @return Pointer to the matching WriteQueueEntry, null if not found.
*/
Entry* findMatch(Addr blk_addr, bool is_secure) const
{
for (const auto& entry : allocatedList) {
// we ignore any entries allocated for uncacheable
// accesses and simply ignore them when matching, in the
// cache we never check for matches when adding new
// uncacheable entries, and we do not want normal
// cacheable accesses being added to an WriteQueueEntry
// serving an uncacheable access
if (!entry->isUncacheable() && entry->blkAddr == blk_addr &&
entry->isSecure == is_secure) {
return entry;
}
}
return nullptr;
}
bool checkFunctional(PacketPtr pkt, Addr blk_addr)
{
pkt->pushLabel(label);
for (const auto& entry : allocatedList) {
if (entry->blkAddr == blk_addr && entry->checkFunctional(pkt)) {
pkt->popLabel();
return true;
}
}
pkt->popLabel();
return false;
}
/**
* Find any pending requests that overlap the given request.
* @param blk_addr Block address.
* @param is_secure True if the target memory space is secure.
* @return A pointer to the earliest matching WriteQueueEntry.
*/
Entry* findPending(Addr blk_addr, bool is_secure) const
{
for (const auto& entry : readyList) {
if (entry->blkAddr == blk_addr && entry->isSecure == is_secure) {
return entry;
}
}
return nullptr;
}
/**
* Returns the WriteQueueEntry at the head of the readyList.
* @return The next request to service.
*/
Entry* getNext() const
{
if (readyList.empty() || readyList.front()->readyTime > curTick()) {
return nullptr;
}
return readyList.front();
}
Tick nextReadyTime() const
{
return readyList.empty() ? MaxTick : readyList.front()->readyTime;
}
/**
* Removes the given entry from the queue. This places the entry
* on the free list.
*
* @param entry
*/
void deallocate(Entry *entry)
{
allocatedList.erase(entry->allocIter);
freeList.push_front(entry);
allocated--;
if (entry->inService) {
_numInService--;
} else {
readyList.erase(entry->readyIter);
}
entry->deallocate();
if (drainState() == DrainState::Draining && allocated == 0) {
// Notify the drain manager that we have completed
// draining if there are no other outstanding requests in
// this queue.
DPRINTF(Drain, "Queue now empty, signalling drained\n");
signalDrainDone();
}
}
DrainState drain() override
{
return allocated == 0 ? DrainState::Drained : DrainState::Draining;
}
};
#endif //__MEM_CACHE_QUEUE_HH__