2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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.
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.
31 #include "base/cprintf.hh"
32 #include "base/misc.hh"
33 #include "base/stl_helpers.hh"
34 #include "debug/RubyQueue.hh"
35 #include "mem/ruby/buffers/MessageBuffer.hh"
36 #include "mem/ruby/system/System.hh"
39 using m5::stl_helpers::operator<<;
41 MessageBuffer::MessageBuffer(const string
&name
)
42 : m_time_last_time_size_checked(0), m_time_last_time_enqueue(0),
43 m_time_last_time_pop(0), m_last_arrival_time(0)
46 m_consumer_ptr
= NULL
;
48 m_receiver_ptr
= NULL
;
50 m_ordering_set
= false;
54 m_randomization
= true;
55 m_size_last_time_size_checked
= 0;
56 m_size_at_cycle_start
= 0;
57 m_msgs_this_cycle
= 0;
58 m_not_avail_count
= 0;
62 m_stall_msg_map
.clear();
68 MessageBuffer::getSize()
70 if (m_time_last_time_size_checked
== m_receiver_ptr
->curCycle()) {
71 return m_size_last_time_size_checked
;
73 m_time_last_time_size_checked
= m_receiver_ptr
->curCycle();
74 m_size_last_time_size_checked
= m_size
;
80 MessageBuffer::areNSlotsAvailable(int n
)
83 // fast path when message buffers have infinite size
84 if (m_max_size
== -1) {
88 // determine my correct size for the current cycle
89 // pop operations shouldn't effect the network's visible size
90 // until next cycle, but enqueue operations effect the visible
92 int current_size
= max(m_size_at_cycle_start
, m_size
);
93 if (m_time_last_time_pop
< m_receiver_ptr
->curCycle()) {
94 // no pops this cycle - m_size is correct
95 current_size
= m_size
;
97 if (m_time_last_time_enqueue
< m_receiver_ptr
->curCycle()) {
98 // no enqueues this cycle - m_size_at_cycle_start is correct
99 current_size
= m_size_at_cycle_start
;
101 // both pops and enqueues occured this cycle - add new
102 // enqueued msgs to m_size_at_cycle_start
103 current_size
= m_size_at_cycle_start
+m_msgs_this_cycle
;
107 // now compare the new size with our max size
108 if (current_size
+ n
<= m_max_size
) {
111 DPRINTF(RubyQueue
, "n: %d, current_size: %d, m_size: %d, "
113 n
, current_size
, m_size
, m_max_size
);
120 MessageBuffer::getMsgPtrCopy() const
124 return m_prio_heap
.front().m_msgptr
->clone();
128 MessageBuffer::peekAtHeadOfQueue() const
130 DPRINTF(RubyQueue
, "Peeking at head of queue.\n");
133 const Message
* msg_ptr
= m_prio_heap
.front().m_msgptr
.get();
136 DPRINTF(RubyQueue
, "Message: %s\n", (*msg_ptr
));
140 // FIXME - move me somewhere else
145 time
+= Cycles(random() & 0x3); // [0...3]
146 if ((random() & 0x7) == 0) { // 1 in 8 chance
147 time
+= Cycles(100 + (random() % 0xf)); // 100 + [1...15]
153 MessageBuffer::enqueue(MsgPtr message
, Cycles delay
)
158 // record current time incase we have a pop that also adjusts my size
159 if (m_time_last_time_enqueue
< m_receiver_ptr
->curCycle()) {
160 m_msgs_this_cycle
= 0; // first msg this cycle
161 m_time_last_time_enqueue
= m_receiver_ptr
->curCycle();
165 if (!m_ordering_set
) {
166 panic("Ordering property of %s has not been set", m_name
);
169 // Calculate the arrival time of the message, that is, the first
170 // cycle the message can be dequeued.
172 Cycles delta
= m_receiver_ptr
->ticksToCycles(delay
*
173 m_sender_ptr
->clockPeriod());
175 Cycles
current_time(m_receiver_ptr
->curCycle());
176 Cycles
arrival_time(0);
178 if (!RubySystem::getRandomization() || (m_randomization
== false)) {
180 arrival_time
= current_time
+ delta
;
182 // Randomization - ignore delta
184 if (m_last_arrival_time
< current_time
) {
185 m_last_arrival_time
= current_time
;
187 arrival_time
= m_last_arrival_time
+ random_time();
189 arrival_time
= current_time
+ random_time();
193 // Check the arrival time
194 assert(arrival_time
> current_time
);
196 if (arrival_time
< m_last_arrival_time
) {
197 panic("FIFO ordering violated: %s name: %s current time: %d "
198 "delta: %d arrival_time: %d last arrival_time: %d\n",
199 *this, m_name
, current_time
* m_receiver_ptr
->clockPeriod(),
200 delta
* m_receiver_ptr
->clockPeriod(),
201 arrival_time
* m_receiver_ptr
->clockPeriod(),
202 m_last_arrival_time
* m_receiver_ptr
->clockPeriod());
206 // If running a cache trace, don't worry about the last arrival checks
207 if (!g_system_ptr
->m_warmup_enabled
) {
208 m_last_arrival_time
= arrival_time
;
211 // compute the delay cycles and set enqueue time
212 Message
* msg_ptr
= message
.get();
213 assert(msg_ptr
!= NULL
);
215 assert(m_receiver_ptr
->clockEdge() >= msg_ptr
->getLastEnqueueTime() &&
216 "ensure we aren't dequeued early");
218 msg_ptr
->setDelayedTicks(m_receiver_ptr
->clockEdge() -
219 msg_ptr
->getLastEnqueueTime() +
220 msg_ptr
->getDelayedTicks());
221 msg_ptr
->setLastEnqueueTime(arrival_time
* m_receiver_ptr
->clockPeriod());
223 // Insert the message into the priority heap
224 MessageBufferNode
thisNode(arrival_time
, m_msg_counter
, message
);
225 m_prio_heap
.push_back(thisNode
);
226 push_heap(m_prio_heap
.begin(), m_prio_heap
.end(),
227 greater
<MessageBufferNode
>());
229 DPRINTF(RubyQueue
, "Enqueue arrival_time: %lld, Message: %s\n",
230 arrival_time
* m_receiver_ptr
->clockPeriod(), *(message
.get()));
232 // Schedule the wakeup
233 if (m_consumer_ptr
!= NULL
) {
234 m_consumer_ptr
->scheduleEventAbsolute(arrival_time
);
235 m_consumer_ptr
->storeEventInfo(m_vnet_id
);
237 panic("No consumer: %s name: %s\n", *this, m_name
);
242 MessageBuffer::dequeue_getDelayCycles(MsgPtr
& message
)
245 return setAndReturnDelayCycles(message
);
249 MessageBuffer::dequeue(MsgPtr
& message
)
251 DPRINTF(RubyQueue
, "Dequeueing\n");
252 message
= m_prio_heap
.front().m_msgptr
;
255 DPRINTF(RubyQueue
, "Enqueue message is %s\n", (*(message
.get())));
259 MessageBuffer::dequeue_getDelayCycles()
261 // get MsgPtr of the message about to be dequeued
262 MsgPtr message
= m_prio_heap
.front().m_msgptr
;
264 // get the delay cycles
265 Cycles delayCycles
= setAndReturnDelayCycles(message
);
274 DPRINTF(RubyQueue
, "Popping\n");
276 pop_heap(m_prio_heap
.begin(), m_prio_heap
.end(),
277 greater
<MessageBufferNode
>());
278 m_prio_heap
.pop_back();
280 // record previous size and time so the current buffer size isn't
281 // adjusted until next cycle
282 if (m_time_last_time_pop
< m_receiver_ptr
->curCycle()) {
283 m_size_at_cycle_start
= m_size
;
284 m_time_last_time_pop
= m_receiver_ptr
->curCycle();
290 MessageBuffer::clear()
296 m_time_last_time_enqueue
= Cycles(0);
297 m_time_last_time_pop
= Cycles(0);
298 m_size_at_cycle_start
= 0;
299 m_msgs_this_cycle
= 0;
303 MessageBuffer::recycle()
305 DPRINTF(RubyQueue
, "Recycling.\n");
307 MessageBufferNode node
= m_prio_heap
.front();
308 pop_heap(m_prio_heap
.begin(), m_prio_heap
.end(),
309 greater
<MessageBufferNode
>());
311 node
.m_time
= m_receiver_ptr
->curCycle() + m_recycle_latency
;
312 m_prio_heap
.back() = node
;
313 push_heap(m_prio_heap
.begin(), m_prio_heap
.end(),
314 greater
<MessageBufferNode
>());
315 m_consumer_ptr
->scheduleEventAbsolute(m_receiver_ptr
->curCycle() +
320 MessageBuffer::reanalyzeMessages(const Address
& addr
)
322 DPRINTF(RubyQueue
, "ReanalyzeMessages\n");
323 assert(m_stall_msg_map
.count(addr
) > 0);
324 Cycles nextCycle
= m_receiver_ptr
->curCycle() + Cycles(1);
327 // Put all stalled messages associated with this address back on the
330 while(!m_stall_msg_map
[addr
].empty()) {
332 MessageBufferNode
msgNode(nextCycle
, m_msg_counter
,
333 m_stall_msg_map
[addr
].front());
335 m_prio_heap
.push_back(msgNode
);
336 push_heap(m_prio_heap
.begin(), m_prio_heap
.end(),
337 greater
<MessageBufferNode
>());
339 m_consumer_ptr
->scheduleEventAbsolute(msgNode
.m_time
);
340 m_stall_msg_map
[addr
].pop_front();
342 m_stall_msg_map
.erase(addr
);
346 MessageBuffer::reanalyzeAllMessages()
348 DPRINTF(RubyQueue
, "ReanalyzeAllMessages %s\n");
349 Cycles nextCycle
= m_receiver_ptr
->curCycle() + Cycles(1);
352 // Put all stalled messages associated with this address back on the
355 for (StallMsgMapType::iterator map_iter
= m_stall_msg_map
.begin();
356 map_iter
!= m_stall_msg_map
.end();
359 while(!(map_iter
->second
).empty()) {
361 MessageBufferNode
msgNode(nextCycle
, m_msg_counter
,
362 (map_iter
->second
).front());
364 m_prio_heap
.push_back(msgNode
);
365 push_heap(m_prio_heap
.begin(), m_prio_heap
.end(),
366 greater
<MessageBufferNode
>());
368 m_consumer_ptr
->scheduleEventAbsolute(msgNode
.m_time
);
369 (map_iter
->second
).pop_front();
372 m_stall_msg_map
.clear();
376 MessageBuffer::stallMessage(const Address
& addr
)
378 DPRINTF(RubyQueue
, "Stalling due to %s\n", addr
);
380 assert(addr
.getOffset() == 0);
381 MsgPtr message
= m_prio_heap
.front().m_msgptr
;
386 // Note: no event is scheduled to analyze the map at a later time.
387 // Instead the controller is responsible to call reanalyzeMessages when
388 // these addresses change state.
390 (m_stall_msg_map
[addr
]).push_back(message
);
394 MessageBuffer::setAndReturnDelayCycles(MsgPtr msg_ptr
)
396 // get the delay cycles of the message at the top of the queue
398 // this function should only be called on dequeue
399 // ensure the msg hasn't been enqueued
400 assert(msg_ptr
->getLastEnqueueTime() <= m_receiver_ptr
->clockEdge());
402 msg_ptr
->setDelayedTicks(m_receiver_ptr
->clockEdge() -
403 msg_ptr
->getLastEnqueueTime() +
404 msg_ptr
->getDelayedTicks());
406 return m_receiver_ptr
->ticksToCycles(msg_ptr
->getDelayedTicks());
410 MessageBuffer::print(ostream
& out
) const
412 ccprintf(out
, "[MessageBuffer: ");
413 if (m_consumer_ptr
!= NULL
) {
414 ccprintf(out
, " consumer-yes ");
417 vector
<MessageBufferNode
> copy(m_prio_heap
);
418 sort_heap(copy
.begin(), copy
.end(), greater
<MessageBufferNode
>());
419 ccprintf(out
, "%s] %s", copy
, m_name
);
423 MessageBuffer::printStats(ostream
& out
)
425 out
<< "MessageBuffer: " << m_name
<< " stats - msgs:" << m_msg_counter
426 << " full:" << m_not_avail_count
<< endl
;
430 MessageBuffer::isReady() const
432 return ((m_prio_heap
.size() > 0) &&
433 (m_prio_heap
.front().m_time
<= m_receiver_ptr
->curCycle()));
437 MessageBuffer::functionalRead(Packet
*pkt
)
439 // Check the priority heap and read any messages that may
440 // correspond to the address in the packet.
441 for (unsigned int i
= 0; i
< m_prio_heap
.size(); ++i
) {
442 Message
*msg
= m_prio_heap
[i
].m_msgptr
.get();
443 if (msg
->functionalRead(pkt
)) return true;
446 // Read the messages in the stall queue that correspond
447 // to the address in the packet.
448 for (StallMsgMapType::iterator map_iter
= m_stall_msg_map
.begin();
449 map_iter
!= m_stall_msg_map
.end();
452 for (std::list
<MsgPtr
>::iterator it
= (map_iter
->second
).begin();
453 it
!= (map_iter
->second
).end(); ++it
) {
455 Message
*msg
= (*it
).get();
456 if (msg
->functionalRead(pkt
)) return true;
463 MessageBuffer::functionalWrite(Packet
*pkt
)
465 uint32_t num_functional_writes
= 0;
467 // Check the priority heap and write any messages that may
468 // correspond to the address in the packet.
469 for (unsigned int i
= 0; i
< m_prio_heap
.size(); ++i
) {
470 Message
*msg
= m_prio_heap
[i
].m_msgptr
.get();
471 if (msg
->functionalWrite(pkt
)) {
472 num_functional_writes
++;
476 // Check the stall queue and write any messages that may
477 // correspond to the address in the packet.
478 for (StallMsgMapType::iterator map_iter
= m_stall_msg_map
.begin();
479 map_iter
!= m_stall_msg_map
.end();
482 for (std::list
<MsgPtr
>::iterator it
= (map_iter
->second
).begin();
483 it
!= (map_iter
->second
).end(); ++it
) {
485 Message
*msg
= (*it
).get();
486 if (msg
->functionalWrite(pkt
)) {
487 num_functional_writes
++;
492 return num_functional_writes
;