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