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}