mshr_queue.cc (9347:b02075171b57) mshr_queue.cc (9725:0d4ee33078bb)
1/*
1/*
2 * Copyright (c) 2012 ARM Limited
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)
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),
55 numEntries(num_entries + reserve - 1), numReserve(reserve),
56 drainManager(NULL), index(_index)
54 : label(_label), numEntries(num_entries + reserve - 1),
55 numReserve(reserve), registers(numEntries),
56 drainManager(NULL), allocated(0), inServiceEntries(0), index(_index)
57{
57{
58 allocated = 0;
59 inServiceEntries = 0;
60 registers = new MSHR[numEntries];
61 for (int i = 0; i < numEntries; ++i) {
62 registers[i].queue = this;
63 freeList.push_back(&registers[i]);
64 }
65}
66
58 for (int i = 0; i < numEntries; ++i) {
59 registers[i].queue = this;
60 freeList.push_back(&registers[i]);
61 }
62}
63
67MSHRQueue::~MSHRQueue()
68{
69 delete [] registers;
70}
71
72MSHR *
73MSHRQueue::findMatch(Addr addr) const
74{
75 MSHR::ConstIterator i = allocatedList.begin();
76 MSHR::ConstIterator end = allocatedList.end();
77 for (; i != end; ++i) {
78 MSHR *mshr = *i;
79 if (mshr->addr == addr) {
80 return mshr;
81 }
82 }
83 return NULL;
84}
85
86bool
87MSHRQueue::findMatches(Addr addr, vector<MSHR*>& matches) const
88{
89 // Need an empty vector
90 assert(matches.empty());
91 bool retval = false;
92 MSHR::ConstIterator i = allocatedList.begin();
93 MSHR::ConstIterator end = allocatedList.end();
94 for (; i != end; ++i) {
95 MSHR *mshr = *i;
96 if (mshr->addr == addr) {
97 retval = true;
98 matches.push_back(mshr);
99 }
100 }
101 return retval;
102}
103
104
105bool
106MSHRQueue::checkFunctional(PacketPtr pkt, Addr blk_addr)
107{
108 pkt->pushLabel(label);
109 MSHR::ConstIterator i = allocatedList.begin();
110 MSHR::ConstIterator end = allocatedList.end();
111 for (; i != end; ++i) {
112 MSHR *mshr = *i;
113 if (mshr->addr == blk_addr && mshr->checkFunctional(pkt)) {
114 pkt->popLabel();
115 return true;
116 }
117 }
118 pkt->popLabel();
119 return false;
120}
121
122
123MSHR *
124MSHRQueue::findPending(Addr addr, int size) const
125{
126 MSHR::ConstIterator i = readyList.begin();
127 MSHR::ConstIterator end = readyList.end();
128 for (; i != end; ++i) {
129 MSHR *mshr = *i;
130 if (mshr->addr < addr) {
131 if (mshr->addr + mshr->size > addr) {
132 return mshr;
133 }
134 } else {
135 if (addr + size > mshr->addr) {
136 return mshr;
137 }
138 }
139 }
140 return NULL;
141}
142
143
144MSHR::Iterator
145MSHRQueue::addToReadyList(MSHR *mshr)
146{
147 if (readyList.empty() || readyList.back()->readyTime <= mshr->readyTime) {
148 return readyList.insert(readyList.end(), mshr);
149 }
150
151 MSHR::Iterator i = readyList.begin();
152 MSHR::Iterator end = readyList.end();
153 for (; i != end; ++i) {
154 if ((*i)->readyTime > mshr->readyTime) {
155 return readyList.insert(i, mshr);
156 }
157 }
158 assert(false);
159 return end; // keep stupid compilers happy
160}
161
162
163MSHR *
164MSHRQueue::allocate(Addr addr, int size, PacketPtr &pkt,
165 Tick when, Counter order)
166{
167 assert(!freeList.empty());
168 MSHR *mshr = freeList.front();
169 assert(mshr->getNumTargets() == 0);
170 freeList.pop_front();
171
172 mshr->allocate(addr, size, pkt, when, order);
173 mshr->allocIter = allocatedList.insert(allocatedList.end(), mshr);
174 mshr->readyIter = addToReadyList(mshr);
175
176 allocated += 1;
177 return mshr;
178}
179
180
181void
182MSHRQueue::deallocate(MSHR *mshr)
183{
184 deallocateOne(mshr);
185}
186
187MSHR::Iterator
188MSHRQueue::deallocateOne(MSHR *mshr)
189{
190 MSHR::Iterator retval = allocatedList.erase(mshr->allocIter);
191 freeList.push_front(mshr);
192 allocated--;
193 if (mshr->inService) {
194 inServiceEntries--;
195 } else {
196 readyList.erase(mshr->readyIter);
197 }
198 mshr->deallocate();
199 if (drainManager && allocated == 0) {
200 // Notify the drain manager that we have completed draining if
201 // there are no other outstanding requests in this MSHR queue.
202 drainManager->signalDrainDone();
203 drainManager = NULL;
204 setDrainState(Drainable::Drained);
205 }
206 return retval;
207}
208
209void
210MSHRQueue::moveToFront(MSHR *mshr)
211{
212 if (!mshr->inService) {
213 assert(mshr == *(mshr->readyIter));
214 readyList.erase(mshr->readyIter);
215 mshr->readyIter = readyList.insert(readyList.begin(), mshr);
216 }
217}
218
219void
220MSHRQueue::markInService(MSHR *mshr, PacketPtr pkt)
221{
222 if (mshr->markInService(pkt)) {
223 deallocate(mshr);
224 } else {
225 readyList.erase(mshr->readyIter);
226 inServiceEntries += 1;
227 }
228}
229
230void
231MSHRQueue::markPending(MSHR *mshr)
232{
233 assert(mshr->inService);
234 mshr->inService = false;
235 --inServiceEntries;
236 /**
237 * @ todo might want to add rerequests to front of pending list for
238 * performance.
239 */
240 mshr->readyIter = addToReadyList(mshr);
241}
242
243void
244MSHRQueue::squash(int threadNum)
245{
246 MSHR::Iterator i = allocatedList.begin();
247 MSHR::Iterator end = allocatedList.end();
248 for (; i != end;) {
249 MSHR *mshr = *i;
250 if (mshr->threadNum == threadNum) {
251 while (mshr->hasTargets()) {
252 mshr->popTarget();
253 assert(0/*target->req->threadId()*/ == threadNum);
254 }
255 assert(!mshr->hasTargets());
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());
256 assert(mshr->ntargets==0);
248 assert(mshr->getNumTargets()==0);
257 if (!mshr->inService) {
258 i = deallocateOne(mshr);
259 } else {
260 //mshr->pkt->flags &= ~CACHE_LINE_FILL;
261 ++i;
262 }
263 } else {
264 ++i;
265 }
266 }
267}
268
269unsigned int
270MSHRQueue::drain(DrainManager *dm)
271{
272 if (allocated == 0) {
273 setDrainState(Drainable::Drained);
274 return 0;
275 } else {
276 drainManager = dm;
277 setDrainState(Drainable::Draining);
278 return 1;
279 }
280}
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}