mshr_queue.cc revision 5314 
1/*
2 * Copyright (c) 2003-2005 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Erik Hallnor
29 */
30
31/** @file
32 * Definition of MSHRQueue class functions.
33 */
34
35#include "mem/cache/miss/mshr_queue.hh"
36
37using namespace std;
38
39MSHRQueue::MSHRQueue(const std::string &_label,
40                     int num_entries, int reserve, int _index)
41    : label(_label),
42      numEntries(num_entries + reserve - 1), numReserve(reserve),
43      index(_index)
44{
45    allocated = 0;
46    inServiceEntries = 0;
47    registers = new MSHR[numEntries];
48    for (int i = 0; i < numEntries; ++i) {
49        registers[i].queue = this;
50        freeList.push_back(&registers[i]);
51    }
52}
53
54MSHRQueue::~MSHRQueue()
55{
56    delete [] registers;
57}
58
59MSHR *
60MSHRQueue::findMatch(Addr addr) const
61{
62    MSHR::ConstIterator i = allocatedList.begin();
63    MSHR::ConstIterator end = allocatedList.end();
64    for (; i != end; ++i) {
65        MSHR *mshr = *i;
66        if (mshr->addr == addr) {
67            return mshr;
68        }
69    }
70    return NULL;
71}
72
73bool
74MSHRQueue::findMatches(Addr addr, vector<MSHR*>& matches) const
75{
76    // Need an empty vector
77    assert(matches.empty());
78    bool retval = false;
79    MSHR::ConstIterator i = allocatedList.begin();
80    MSHR::ConstIterator end = allocatedList.end();
81    for (; i != end; ++i) {
82        MSHR *mshr = *i;
83        if (mshr->addr == addr) {
84            retval = true;
85            matches.push_back(mshr);
86        }
87    }
88    return retval;
89}
90
91
92bool
93MSHRQueue::checkFunctional(PacketPtr pkt, Addr blk_addr)
94{
95    pkt->pushLabel(label);
96    MSHR::ConstIterator i = allocatedList.begin();
97    MSHR::ConstIterator end = allocatedList.end();
98    for (; i != end; ++i) {
99        MSHR *mshr = *i;
100        if (mshr->addr == blk_addr && mshr->checkFunctional(pkt)) {
101            pkt->popLabel();
102            return true;
103        }
104    }
105    pkt->popLabel();
106    return false;
107}
108
109
110MSHR *
111MSHRQueue::findPending(Addr addr, int size) const
112{
113    MSHR::ConstIterator i = readyList.begin();
114    MSHR::ConstIterator end = readyList.end();
115    for (; i != end; ++i) {
116        MSHR *mshr = *i;
117        if (mshr->addr < addr) {
118            if (mshr->addr + mshr->size > addr) {
119                return mshr;
120            }
121        } else {
122            if (addr + size > mshr->addr) {
123                return mshr;
124            }
125        }
126    }
127    return NULL;
128}
129
130
131MSHR::Iterator
132MSHRQueue::addToReadyList(MSHR *mshr)
133{
134    if (readyList.empty() || readyList.back()->readyTime <= mshr->readyTime) {
135        return readyList.insert(readyList.end(), mshr);
136    }
137
138    MSHR::Iterator i = readyList.begin();
139    MSHR::Iterator end = readyList.end();
140    for (; i != end; ++i) {
141        if ((*i)->readyTime > mshr->readyTime) {
142            return readyList.insert(i, mshr);
143        }
144    }
145    assert(false);
146    return end;  // keep stupid compilers happy
147}
148
149
150MSHR *
151MSHRQueue::allocate(Addr addr, int size, PacketPtr &pkt,
152                    Tick when, Counter order)
153{
154    assert(!freeList.empty());
155    MSHR *mshr = freeList.front();
156    assert(mshr->getNumTargets() == 0);
157    freeList.pop_front();
158
159    mshr->allocate(addr, size, pkt, when, order);
160    mshr->allocIter = allocatedList.insert(allocatedList.end(), mshr);
161    mshr->readyIter = addToReadyList(mshr);
162
163    allocated += 1;
164    return mshr;
165}
166
167
168void
169MSHRQueue::deallocate(MSHR *mshr)
170{
171    deallocateOne(mshr);
172}
173
174MSHR::Iterator
175MSHRQueue::deallocateOne(MSHR *mshr)
176{
177    MSHR::Iterator retval = allocatedList.erase(mshr->allocIter);
178    freeList.push_front(mshr);
179    allocated--;
180    if (mshr->inService) {
181        inServiceEntries--;
182    } else {
183        readyList.erase(mshr->readyIter);
184    }
185    mshr->deallocate();
186    return retval;
187}
188
189void
190MSHRQueue::moveToFront(MSHR *mshr)
191{
192    if (!mshr->inService) {
193        assert(mshr == *(mshr->readyIter));
194        readyList.erase(mshr->readyIter);
195        mshr->readyIter = readyList.insert(readyList.begin(), mshr);
196    }
197}
198
199void
200MSHRQueue::markInService(MSHR *mshr)
201{
202    if (mshr->markInService()) {
203        deallocate(mshr);
204    } else {
205        readyList.erase(mshr->readyIter);
206        inServiceEntries += 1;
207    }
208}
209
210void
211MSHRQueue::markPending(MSHR *mshr)
212{
213    assert(mshr->inService);
214    mshr->inService = false;
215    --inServiceEntries;
216    /**
217     * @ todo might want to add rerequests to front of pending list for
218     * performance.
219     */
220    mshr->readyIter = addToReadyList(mshr);
221}
222
223void
224MSHRQueue::squash(int threadNum)
225{
226    MSHR::Iterator i = allocatedList.begin();
227    MSHR::Iterator end = allocatedList.end();
228    for (; i != end;) {
229        MSHR *mshr = *i;
230        if (mshr->threadNum == threadNum) {
231            while (mshr->hasTargets()) {
232                mshr->popTarget();
233                assert(0/*target->req->getThreadNum()*/ == threadNum);
234            }
235            assert(!mshr->hasTargets());
236            assert(mshr->ntargets==0);
237            if (!mshr->inService) {
238                i = deallocateOne(mshr);
239            } else {
240                //mshr->pkt->flags &= ~CACHE_LINE_FILL;
241                ++i;
242            }
243        } else {
244            ++i;
245        }
246    }
247}
248