2 * Copyright (c) 2000-2005 The Regents of The University of Michigan
3 * Copyright (c) 2008 The Hewlett-Packard Development Company
4 * Copyright (c) 2013 Advanced Micro Devices, Inc.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met: redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer;
11 * redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution;
14 * neither the name of the copyright holders nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #include "sim/eventq.hh"
37 #include <unordered_map>
40 #include "base/logging.hh"
41 #include "base/trace.hh"
43 #include "debug/Checkpoint.hh"
44 #include "sim/core.hh"
51 // Events on these queues are processed at the *beginning* of each
52 // cycle, before the pipeline simulation is performed.
54 uint32_t numMainEventQueues
= 0;
55 std::vector
<EventQueue
*> mainEventQueue
;
56 __thread EventQueue
*_curEventQueue
= NULL
;
57 bool inParallelMode
= false;
60 getEventQueue(uint32_t index
)
62 while (numMainEventQueues
<= index
) {
64 mainEventQueue
.push_back(
65 new EventQueue(csprintf("MainEventQueue-%d", index
)));
68 return mainEventQueue
[index
];
72 Counter
Event::instanceCounter
= 0;
84 return csprintf("Event_%s", instanceString());
89 Event::insertBefore(Event
*event
, Event
*curr
)
91 // Either way, event will be the top element in the 'in bin' list
92 // which is the pointer we need in order to look into the list, so
93 // we need to insert that into the bin list.
94 if (!curr
|| *event
< *curr
) {
95 // Insert the event before the current list since it is in the future.
96 event
->nextBin
= curr
;
97 event
->nextInBin
= NULL
;
99 // Since we're on the correct list, we need to point to the next list
100 event
->nextBin
= curr
->nextBin
; // curr->nextBin can now become stale
102 // Insert event at the top of the stack
103 event
->nextInBin
= curr
;
110 EventQueue::insert(Event
*event
)
112 // Deal with the head case
113 if (!head
|| *event
<= *head
) {
114 head
= Event::insertBefore(event
, head
);
118 // Figure out either which 'in bin' list we are on, or where a new list
119 // needs to be inserted
121 Event
*curr
= head
->nextBin
;
122 while (curr
&& *curr
< *event
) {
124 curr
= curr
->nextBin
;
127 // Note: this operation may render all nextBin pointers on the
128 // prev 'in bin' list stale (except for the top one)
129 prev
->nextBin
= Event::insertBefore(event
, curr
);
133 Event::removeItem(Event
*event
, Event
*top
)
136 Event
*next
= top
->nextInBin
;
138 // if we removed the top item, we need to handle things specially
139 // and just remove the top item, fixing up the next bin pointer of
144 next
->nextBin
= top
->nextBin
;
148 // Since we already checked the current element, we're going to
149 // keep checking event against the next element.
150 while (event
!= next
) {
152 panic("event not found!");
155 next
= next
->nextInBin
;
158 // remove next from the 'in bin' list since it's what we're looking for
159 curr
->nextInBin
= next
->nextInBin
;
164 EventQueue::remove(Event
*event
)
167 panic("event not found!");
169 assert(event
->queue
== this);
171 // deal with an event on the head's 'in bin' list (event has the same
173 if (*head
== *event
) {
174 head
= Event::removeItem(event
, head
);
178 // Find the 'in bin' list that this event belongs on
180 Event
*curr
= head
->nextBin
;
181 while (curr
&& *curr
< *event
) {
183 curr
= curr
->nextBin
;
186 if (!curr
|| *curr
!= *event
)
187 panic("event not found!");
189 // curr points to the top item of the the correct 'in bin' list, when
190 // we remove an item, it returns the new top item (which may be
192 prev
->nextBin
= Event::removeItem(event
, curr
);
196 EventQueue::serviceOne()
198 std::lock_guard
<EventQueue
> lock(*this);
200 Event
*next
= head
->nextInBin
;
201 event
->flags
.clear(Event::Scheduled
);
204 // update the next bin pointer since it could be stale
205 next
->nextBin
= head
->nextBin
;
210 // this was the only element on the 'in bin' list, so get rid of
211 // the 'in bin' list and point to the next bin list
212 head
= head
->nextBin
;
216 if (!event
->squashed()) {
217 // forward current cycle to the time when this event occurs.
218 setCurTick(event
->when());
220 event
->trace("executed");
222 if (event
->isExitEvent()) {
223 assert(!event
->flags
.isSet(Event::Managed
) ||
224 !event
->flags
.isSet(Event::IsMainQueue
)); // would be silly
228 event
->flags
.clear(Event::Squashed
);
237 Event::serialize(CheckpointOut
&cp
) const
239 SERIALIZE_SCALAR(_when
);
240 SERIALIZE_SCALAR(_priority
);
241 short _flags
= flags
;
242 SERIALIZE_SCALAR(_flags
);
246 Event::unserialize(CheckpointIn
&cp
)
248 assert(!scheduled());
250 UNSERIALIZE_SCALAR(_when
);
251 UNSERIALIZE_SCALAR(_priority
);
254 UNSERIALIZE_SCALAR(_flags
);
256 // Old checkpoints had no concept of the Initialized flag
257 // so restoring from old checkpoints always fail.
258 // Events are initialized on construction but original code
259 // "flags = _flags" would just overwrite the initialization.
260 // So, read in the checkpoint flags, but then set the Initialized
261 // flag on top of it in order to avoid failures.
262 assert(initialized());
264 flags
.set(Initialized
);
266 // need to see if original event was in a scheduled, unsquashed
267 // state, but don't want to restore those flags in the current
268 // object itself (since they aren't immediately true)
269 if (flags
.isSet(Scheduled
) && !flags
.isSet(Squashed
)) {
270 flags
.clear(Squashed
| Scheduled
);
272 DPRINTF(Checkpoint
, "Event '%s' need to be scheduled @%d\n",
278 EventQueue::checkpointReschedule(Event
*event
)
280 // It's safe to call insert() directly here since this method
281 // should only be called when restoring from a checkpoint (which
282 // happens before thread creation).
283 if (event
->flags
.isSet(Event::Scheduled
))
287 EventQueue::dump() const
289 cprintf("============================================================\n");
290 cprintf("EventQueue Dump (cycle %d)\n", curTick());
291 cprintf("------------------------------------------------------------\n");
294 cprintf("<No Events>\n");
296 Event
*nextBin
= head
;
298 Event
*nextInBin
= nextBin
;
301 nextInBin
= nextInBin
->nextInBin
;
304 nextBin
= nextBin
->nextBin
;
308 cprintf("============================================================\n");
312 EventQueue::debugVerify() const
314 std::unordered_map
<long, bool> map
;
319 Event
*nextBin
= head
;
321 Event
*nextInBin
= nextBin
;
323 if (nextInBin
->when() < time
) {
324 cprintf("time goes backwards!");
327 } else if (nextInBin
->when() == time
&&
328 nextInBin
->priority() < priority
) {
329 cprintf("priority inverted!");
334 if (map
[reinterpret_cast<long>(nextInBin
)]) {
335 cprintf("Node already seen");
339 map
[reinterpret_cast<long>(nextInBin
)] = true;
341 time
= nextInBin
->when();
342 priority
= nextInBin
->priority();
344 nextInBin
= nextInBin
->nextInBin
;
347 nextBin
= nextBin
->nextBin
;
354 EventQueue::replaceHead(Event
* s
)
364 for (uint32_t i
= 0; i
< numMainEventQueues
; ++i
) {
365 mainEventQueue
[i
]->dump();
371 Event::description() const
377 Event::trace(const char *action
)
379 // This DPRINTF is unconditional because calls to this function
380 // are protected by an 'if (DTRACE(Event))' in the inlined Event
383 // This is just a default implementation for derived classes where
384 // it's not worth doing anything special. If you want to put a
385 // more informative message in the trace, override this method on
386 // the particular subclass where you have the information that
387 // needs to be printed.
388 DPRINTF_UNCONDITIONAL(Event
, "%s %s %s @ %d\n",
389 description(), instanceString(), action
, when());
393 Event::instanceString() const
396 return csprintf("%d", instance
);
398 return csprintf("%#x", (uintptr_t)this);
405 cprintf("Event %s (%s)\n", name(), description());
406 cprintf("Flags: %#x\n", flags
);
408 cprintf("Created: %d\n", whenCreated
);
412 cprintf("Scheduled at %d\n", whenScheduled
);
414 cprintf("Scheduled for %d, priority %d\n", when(), _priority
);
416 cprintf("Not Scheduled\n");
420 EventQueue::EventQueue(const std::string
&n
)
421 : objName(n
), head(NULL
), _curTick(0)
426 EventQueue::asyncInsert(Event
*event
)
428 async_queue_mutex
.lock();
429 async_queue
.push_back(event
);
430 async_queue_mutex
.unlock();
434 EventQueue::handleAsyncInsertions()
436 assert(this == curEventQueue());
437 async_queue_mutex
.lock();
439 while (!async_queue
.empty()) {
440 insert(async_queue
.front());
441 async_queue
.pop_front();
444 async_queue_mutex
.unlock();