2 * Copyright (c) 2019,2020 ARM Limited
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.
14 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
15 * All rights reserved.
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.
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.
41 #include "mem/ruby/network/MessageBuffer.hh"
45 #include "base/cprintf.hh"
46 #include "base/logging.hh"
47 #include "base/random.hh"
48 #include "base/stl_helpers.hh"
49 #include "debug/RubyQueue.hh"
50 #include "mem/ruby/system/RubySystem.hh"
53 using m5::stl_helpers::operator<<;
55 MessageBuffer::MessageBuffer(const Params
&p
)
56 : SimObject(p
), m_stall_map_size(0),
57 m_max_size(p
.buffer_size
), m_time_last_time_size_checked(0),
58 m_time_last_time_enqueue(0), m_time_last_time_pop(0),
59 m_last_arrival_time(0), m_strict_fifo(p
.ordered
),
60 m_randomization(p
.randomization
),
61 m_allow_zero_latency(p
.allow_zero_latency
)
65 m_size_last_time_size_checked
= 0;
66 m_size_at_cycle_start
= 0;
67 m_stalled_at_cycle_start
= 0;
68 m_msgs_this_cycle
= 0;
71 m_stall_msg_map
.clear();
78 m_dequeue_callback
= nullptr;
82 MessageBuffer::getSize(Tick curTime
)
84 if (m_time_last_time_size_checked
!= curTime
) {
85 m_time_last_time_size_checked
= curTime
;
86 m_size_last_time_size_checked
= m_prio_heap
.size();
89 return m_size_last_time_size_checked
;
93 MessageBuffer::areNSlotsAvailable(unsigned int n
, Tick current_time
)
96 // fast path when message buffers have infinite size
97 if (m_max_size
== 0) {
101 // determine the correct size for the current cycle
102 // pop operations shouldn't effect the network's visible size
103 // until schd cycle, but enqueue operations effect the visible
105 unsigned int current_size
= 0;
106 unsigned int current_stall_size
= 0;
108 if (m_time_last_time_pop
< current_time
) {
109 // no pops this cycle - heap and stall queue size is correct
110 current_size
= m_prio_heap
.size();
111 current_stall_size
= m_stall_map_size
;
113 if (m_time_last_time_enqueue
< current_time
) {
114 // no enqueues this cycle - m_size_at_cycle_start is correct
115 current_size
= m_size_at_cycle_start
;
117 // both pops and enqueues occured this cycle - add new
118 // enqueued msgs to m_size_at_cycle_start
119 current_size
= m_size_at_cycle_start
+ m_msgs_this_cycle
;
122 // Stall queue size at start is considered
123 current_stall_size
= m_stalled_at_cycle_start
;
126 // now compare the new size with our max size
127 if (current_size
+ current_stall_size
+ n
<= m_max_size
) {
130 DPRINTF(RubyQueue
, "n: %d, current_size: %d, heap size: %d, "
132 n
, current_size
+ current_stall_size
,
133 m_prio_heap
.size(), m_max_size
);
140 MessageBuffer::peek() const
142 DPRINTF(RubyQueue
, "Peeking at head of queue.\n");
143 const Message
* msg_ptr
= m_prio_heap
.front().get();
146 DPRINTF(RubyQueue
, "Message: %s\n", (*msg_ptr
));
150 // FIXME - move me somewhere else
155 time
+= random_mt
.random(0, 3); // [0...3]
156 if (random_mt
.random(0, 7) == 0) { // 1 in 8 chance
157 time
+= 100 + random_mt
.random(1, 15); // 100 + [1...15]
163 MessageBuffer::enqueue(MsgPtr message
, Tick current_time
, Tick delta
)
165 // record current time incase we have a pop that also adjusts my size
166 if (m_time_last_time_enqueue
< current_time
) {
167 m_msgs_this_cycle
= 0; // first msg this cycle
168 m_time_last_time_enqueue
= current_time
;
174 // Calculate the arrival time of the message, that is, the first
175 // cycle the message can be dequeued.
176 assert((delta
> 0) || m_allow_zero_latency
);
177 Tick arrival_time
= 0;
179 // random delays are inserted if the RubySystem level randomization flag
180 // is turned on and this buffer allows it
181 if ((m_randomization
== MessageRandomization::disabled
) ||
182 ((m_randomization
== MessageRandomization::ruby_system
) &&
183 !RubySystem::getRandomization())) {
185 arrival_time
= current_time
+ delta
;
187 // Randomization - ignore delta
189 if (m_last_arrival_time
< current_time
) {
190 m_last_arrival_time
= current_time
;
192 arrival_time
= m_last_arrival_time
+ random_time();
194 arrival_time
= current_time
+ random_time();
198 // Check the arrival time
199 assert(arrival_time
>= current_time
);
201 if (arrival_time
< m_last_arrival_time
) {
202 panic("FIFO ordering violated: %s name: %s current time: %d "
203 "delta: %d arrival_time: %d last arrival_time: %d\n",
204 *this, name(), current_time
, delta
, arrival_time
,
205 m_last_arrival_time
);
209 // If running a cache trace, don't worry about the last arrival checks
210 if (!RubySystem::getWarmupEnabled()) {
211 m_last_arrival_time
= arrival_time
;
214 // compute the delay cycles and set enqueue time
215 Message
* msg_ptr
= message
.get();
216 assert(msg_ptr
!= NULL
);
218 assert(current_time
>= msg_ptr
->getLastEnqueueTime() &&
219 "ensure we aren't dequeued early");
221 msg_ptr
->updateDelayedTicks(current_time
);
222 msg_ptr
->setLastEnqueueTime(arrival_time
);
223 msg_ptr
->setMsgCounter(m_msg_counter
);
225 // Insert the message into the priority heap
226 m_prio_heap
.push_back(message
);
227 push_heap(m_prio_heap
.begin(), m_prio_heap
.end(), greater
<MsgPtr
>());
228 // Increment the number of messages statistic
231 assert((m_max_size
== 0) ||
232 ((m_prio_heap
.size() + m_stall_map_size
) <= m_max_size
));
234 DPRINTF(RubyQueue
, "Enqueue arrival_time: %lld, Message: %s\n",
235 arrival_time
, *(message
.get()));
237 // Schedule the wakeup
238 assert(m_consumer
!= NULL
);
239 m_consumer
->scheduleEventAbsolute(arrival_time
);
240 m_consumer
->storeEventInfo(m_vnet_id
);
244 MessageBuffer::dequeue(Tick current_time
, bool decrement_messages
)
246 DPRINTF(RubyQueue
, "Popping\n");
247 assert(isReady(current_time
));
249 // get MsgPtr of the message about to be dequeued
250 MsgPtr message
= m_prio_heap
.front();
252 // get the delay cycles
253 message
->updateDelayedTicks(current_time
);
254 Tick delay
= message
->getDelayedTicks();
256 m_stall_time
= curTick() - message
->getTime();
258 // record previous size and time so the current buffer size isn't
259 // adjusted until schd cycle
260 if (m_time_last_time_pop
< current_time
) {
261 m_size_at_cycle_start
= m_prio_heap
.size();
262 m_stalled_at_cycle_start
= m_stall_map_size
;
263 m_time_last_time_pop
= current_time
;
266 pop_heap(m_prio_heap
.begin(), m_prio_heap
.end(), greater
<MsgPtr
>());
267 m_prio_heap
.pop_back();
268 if (decrement_messages
) {
269 // If the message will be removed from the queue, decrement the
270 // number of message in the queue.
274 // if a dequeue callback was requested, call it now
275 if (m_dequeue_callback
) {
276 m_dequeue_callback();
283 MessageBuffer::registerDequeueCallback(std::function
<void()> callback
)
285 m_dequeue_callback
= callback
;
289 MessageBuffer::unregisterDequeueCallback()
291 m_dequeue_callback
= nullptr;
295 MessageBuffer::clear()
300 m_time_last_time_enqueue
= 0;
301 m_time_last_time_pop
= 0;
302 m_size_at_cycle_start
= 0;
303 m_stalled_at_cycle_start
= 0;
304 m_msgs_this_cycle
= 0;
308 MessageBuffer::recycle(Tick current_time
, Tick recycle_latency
)
310 DPRINTF(RubyQueue
, "Recycling.\n");
311 assert(isReady(current_time
));
312 MsgPtr node
= m_prio_heap
.front();
313 pop_heap(m_prio_heap
.begin(), m_prio_heap
.end(), greater
<MsgPtr
>());
315 Tick future_time
= current_time
+ recycle_latency
;
316 node
->setLastEnqueueTime(future_time
);
318 m_prio_heap
.back() = node
;
319 push_heap(m_prio_heap
.begin(), m_prio_heap
.end(), greater
<MsgPtr
>());
320 m_consumer
->scheduleEventAbsolute(future_time
);
324 MessageBuffer::reanalyzeList(list
<MsgPtr
> <
, Tick schdTick
)
326 while (!lt
.empty()) {
327 MsgPtr m
= lt
.front();
328 assert(m
->getLastEnqueueTime() <= schdTick
);
330 m_prio_heap
.push_back(m
);
331 push_heap(m_prio_heap
.begin(), m_prio_heap
.end(),
334 m_consumer
->scheduleEventAbsolute(schdTick
);
336 DPRINTF(RubyQueue
, "Requeue arrival_time: %lld, Message: %s\n",
337 schdTick
, *(m
.get()));
344 MessageBuffer::reanalyzeMessages(Addr addr
, Tick current_time
)
346 DPRINTF(RubyQueue
, "ReanalyzeMessages %#x\n", addr
);
347 assert(m_stall_msg_map
.count(addr
) > 0);
350 // Put all stalled messages associated with this address back on the
351 // prio heap. The reanalyzeList call will make sure the consumer is
352 // scheduled for the current cycle so that the previously stalled messages
353 // will be observed before any younger messages that may arrive this cycle
355 m_stall_map_size
-= m_stall_msg_map
[addr
].size();
356 assert(m_stall_map_size
>= 0);
357 reanalyzeList(m_stall_msg_map
[addr
], current_time
);
358 m_stall_msg_map
.erase(addr
);
362 MessageBuffer::reanalyzeAllMessages(Tick current_time
)
364 DPRINTF(RubyQueue
, "ReanalyzeAllMessages\n");
367 // Put all stalled messages associated with this address back on the
368 // prio heap. The reanalyzeList call will make sure the consumer is
369 // scheduled for the current cycle so that the previously stalled messages
370 // will be observed before any younger messages that may arrive this cycle.
372 for (StallMsgMapType::iterator map_iter
= m_stall_msg_map
.begin();
373 map_iter
!= m_stall_msg_map
.end(); ++map_iter
) {
374 m_stall_map_size
-= map_iter
->second
.size();
375 assert(m_stall_map_size
>= 0);
376 reanalyzeList(map_iter
->second
, current_time
);
378 m_stall_msg_map
.clear();
382 MessageBuffer::stallMessage(Addr addr
, Tick current_time
)
384 DPRINTF(RubyQueue
, "Stalling due to %#x\n", addr
);
385 assert(isReady(current_time
));
386 assert(getOffset(addr
) == 0);
387 MsgPtr message
= m_prio_heap
.front();
389 // Since the message will just be moved to stall map, indicate that the
390 // buffer should not decrement the m_buf_msgs statistic
391 dequeue(current_time
, false);
394 // Note: no event is scheduled to analyze the map at a later time.
395 // Instead the controller is responsible to call reanalyzeMessages when
396 // these addresses change state.
398 (m_stall_msg_map
[addr
]).push_back(message
);
404 MessageBuffer::hasStalledMsg(Addr addr
) const
406 return (m_stall_msg_map
.count(addr
) != 0);
410 MessageBuffer::deferEnqueueingMessage(Addr addr
, MsgPtr message
)
412 DPRINTF(RubyQueue
, "Deferring enqueueing message: %s, Address %#x\n",
413 *(message
.get()), addr
);
414 (m_deferred_msg_map
[addr
]).push_back(message
);
418 MessageBuffer::enqueueDeferredMessages(Addr addr
, Tick curTime
, Tick delay
)
420 assert(!isDeferredMsgMapEmpty(addr
));
421 std::vector
<MsgPtr
>& msg_vec
= m_deferred_msg_map
[addr
];
422 assert(msg_vec
.size() > 0);
424 // enqueue all deferred messages associated with this address
425 for (MsgPtr m
: msg_vec
) {
426 enqueue(m
, curTime
, delay
);
430 m_deferred_msg_map
.erase(addr
);
434 MessageBuffer::isDeferredMsgMapEmpty(Addr addr
) const
436 return m_deferred_msg_map
.count(addr
) == 0;
440 MessageBuffer::print(ostream
& out
) const
442 ccprintf(out
, "[MessageBuffer: ");
443 if (m_consumer
!= NULL
) {
444 ccprintf(out
, " consumer-yes ");
447 vector
<MsgPtr
> copy(m_prio_heap
);
448 sort_heap(copy
.begin(), copy
.end(), greater
<MsgPtr
>());
449 ccprintf(out
, "%s] %s", copy
, name());
453 MessageBuffer::isReady(Tick current_time
) const
455 return ((m_prio_heap
.size() > 0) &&
456 (m_prio_heap
.front()->getLastEnqueueTime() <= current_time
));
460 MessageBuffer::regStats()
463 .name(name() + ".not_avail_count")
464 .desc("Number of times this buffer did not have N slots available")
465 .flags(Stats::nozero
);
468 .name(name() + ".avg_buf_msgs")
469 .desc("Average number of messages in buffer")
470 .flags(Stats::nozero
);
473 .name(name() + ".num_msg_stalls")
474 .desc("Number of times messages were stalled")
475 .flags(Stats::nozero
);
478 .name(name() + ".avg_buf_occ")
479 .desc("Average occupancy of buffer capacity")
480 .flags(Stats::nozero
);
483 .name(name() + ".avg_stall_time")
484 .desc("Average number of cycles messages are stalled in this MB")
485 .flags(Stats::nozero
);
487 if (m_max_size
> 0) {
488 m_occupancy
= m_buf_msgs
/ m_max_size
;
495 MessageBuffer::functionalAccess(Packet
*pkt
, bool is_read
)
497 DPRINTF(RubyQueue
, "functional %s for %#x\n",
498 is_read
? "read" : "write", pkt
->getAddr());
500 uint32_t num_functional_accesses
= 0;
502 // Check the priority heap and write any messages that may
503 // correspond to the address in the packet.
504 for (unsigned int i
= 0; i
< m_prio_heap
.size(); ++i
) {
505 Message
*msg
= m_prio_heap
[i
].get();
506 if (is_read
&& msg
->functionalRead(pkt
))
508 else if (!is_read
&& msg
->functionalWrite(pkt
))
509 num_functional_accesses
++;
512 // Check the stall queue and write any messages that may
513 // correspond to the address in the packet.
514 for (StallMsgMapType::iterator map_iter
= m_stall_msg_map
.begin();
515 map_iter
!= m_stall_msg_map
.end();
518 for (std::list
<MsgPtr
>::iterator it
= (map_iter
->second
).begin();
519 it
!= (map_iter
->second
).end(); ++it
) {
521 Message
*msg
= (*it
).get();
522 if (is_read
&& msg
->functionalRead(pkt
))
524 else if (!is_read
&& msg
->functionalWrite(pkt
))
525 num_functional_accesses
++;
529 return num_functional_accesses
;
533 MessageBufferParams::create() const
535 return new MessageBuffer(*this);