2 * Copyright (c) 2000-2005 The Regents of The University of Michigan
3 * Copyright (c) 2008 The Hewlett-Packard Development Company
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * Authors: Steve Reinhardt
39 #include "base/hashmap.hh"
40 #include "base/misc.hh"
41 #include "base/trace.hh"
43 #include "debug/Config.hh"
44 #include "sim/core.hh"
45 #include "sim/eventq.hh"
52 // Events on this queue are processed at the *beginning* of each
53 // cycle, before the pipeline simulation is performed.
55 EventQueue
mainEventQueue("Main Event Queue");
58 Counter
Event::instanceCounter
= 0;
71 return csprintf("Event_%d", instance
);
73 return csprintf("Event_%x", (uintptr_t)this);
79 Event::insertBefore(Event
*event
, Event
*curr
)
81 // Either way, event will be the top element in the 'in bin' list
82 // which is the pointer we need in order to look into the list, so
83 // we need to insert that into the bin list.
84 if (!curr
|| *event
< *curr
) {
85 // Insert the event before the current list since it is in the future.
86 event
->nextBin
= curr
;
87 event
->nextInBin
= NULL
;
89 // Since we're on the correct list, we need to point to the next list
90 event
->nextBin
= curr
->nextBin
; // curr->nextBin can now become stale
92 // Insert event at the top of the stack
93 event
->nextInBin
= curr
;
100 EventQueue::insert(Event
*event
)
102 // Deal with the head case
103 if (!head
|| *event
<= *head
) {
104 head
= Event::insertBefore(event
, head
);
108 // Figure out either which 'in bin' list we are on, or where a new list
109 // needs to be inserted
111 Event
*curr
= head
->nextBin
;
112 while (curr
&& *curr
< *event
) {
114 curr
= curr
->nextBin
;
117 // Note: this operation may render all nextBin pointers on the
118 // prev 'in bin' list stale (except for the top one)
119 prev
->nextBin
= Event::insertBefore(event
, curr
);
123 Event::removeItem(Event
*event
, Event
*top
)
126 Event
*next
= top
->nextInBin
;
128 // if we removed the top item, we need to handle things specially
129 // and just remove the top item, fixing up the next bin pointer of
134 next
->nextBin
= top
->nextBin
;
138 // Since we already checked the current element, we're going to
139 // keep checking event against the next element.
140 while (event
!= next
) {
142 panic("event not found!");
145 next
= next
->nextInBin
;
148 // remove next from the 'in bin' list since it's what we're looking for
149 curr
->nextInBin
= next
->nextInBin
;
154 EventQueue::remove(Event
*event
)
157 panic("event not found!");
159 // deal with an event on the head's 'in bin' list (event has the same
161 if (*head
== *event
) {
162 head
= Event::removeItem(event
, head
);
166 // Find the 'in bin' list that this event belongs on
168 Event
*curr
= head
->nextBin
;
169 while (curr
&& *curr
< *event
) {
171 curr
= curr
->nextBin
;
174 if (!curr
|| *curr
!= *event
)
175 panic("event not found!");
177 // curr points to the top item of the the correct 'in bin' list, when
178 // we remove an item, it returns the new top item (which may be
180 prev
->nextBin
= Event::removeItem(event
, curr
);
184 EventQueue::serviceOne()
187 Event
*next
= head
->nextInBin
;
188 event
->flags
.clear(Event::Scheduled
);
191 // update the next bin pointer since it could be stale
192 next
->nextBin
= head
->nextBin
;
197 // this was the only element on the 'in bin' list, so get rid of
198 // the 'in bin' list and point to the next bin list
199 head
= head
->nextBin
;
203 if (!event
->squashed()) {
205 if (event
->isExitEvent()) {
206 assert(!event
->flags
.isSet(Event::AutoDelete
)); // would be silly
210 event
->flags
.clear(Event::Squashed
);
213 if (event
->flags
.isSet(Event::AutoDelete
) && !event
->scheduled())
220 Event::serialize(std::ostream
&os
)
222 SERIALIZE_SCALAR(_when
);
223 SERIALIZE_SCALAR(_priority
);
224 short _flags
= flags
;
225 SERIALIZE_SCALAR(_flags
);
229 Event::unserialize(Checkpoint
*cp
, const string
§ion
)
232 mainEventQueue
.deschedule(this);
234 UNSERIALIZE_SCALAR(_when
);
235 UNSERIALIZE_SCALAR(_priority
);
238 UNSERIALIZE_SCALAR(_flags
);
240 // Old checkpoints had no concept of the Initialized flag
241 // so restoring from old checkpoints always fail.
242 // Events are initialized on construction but original code
243 // "flags = _flags" would just overwrite the initialization.
244 // So, read in the checkpoint flags, but then set the Initialized
245 // flag on top of it in order to avoid failures.
246 assert(initialized());
248 flags
.set(Initialized
);
250 // need to see if original event was in a scheduled, unsquashed
251 // state, but don't want to restore those flags in the current
252 // object itself (since they aren't immediately true)
253 bool wasScheduled
= flags
.isSet(Scheduled
) && !flags
.isSet(Squashed
);
254 flags
.clear(Squashed
| Scheduled
);
257 DPRINTF(Config
, "rescheduling at %d\n", _when
);
258 mainEventQueue
.schedule(this, _when
);
263 EventQueue::serialize(ostream
&os
)
265 std::list
<Event
*> eventPtrs
;
268 Event
*nextBin
= head
;
270 Event
*nextInBin
= nextBin
;
273 if (nextInBin
->flags
.isSet(Event::AutoSerialize
)) {
274 eventPtrs
.push_back(nextInBin
);
275 paramOut(os
, csprintf("event%d", numEvents
++),
278 nextInBin
= nextInBin
->nextInBin
;
281 nextBin
= nextBin
->nextBin
;
284 SERIALIZE_SCALAR(numEvents
);
286 for (std::list
<Event
*>::iterator it
= eventPtrs
.begin();
287 it
!= eventPtrs
.end(); ++it
) {
289 (*it
)->serialize(os
);
294 EventQueue::unserialize(Checkpoint
*cp
, const std::string
§ion
)
297 UNSERIALIZE_SCALAR(numEvents
);
299 std::string eventName
;
300 for (int i
= 0; i
< numEvents
; i
++) {
301 // get the pointer value associated with the event
302 paramIn(cp
, section
, csprintf("event%d", i
), eventName
);
304 // create the event based on its pointer value
305 Serializable::create(cp
, eventName
);
310 EventQueue::dump() const
312 cprintf("============================================================\n");
313 cprintf("EventQueue Dump (cycle %d)\n", curTick());
314 cprintf("------------------------------------------------------------\n");
317 cprintf("<No Events>\n");
319 Event
*nextBin
= head
;
321 Event
*nextInBin
= nextBin
;
324 nextInBin
= nextInBin
->nextInBin
;
327 nextBin
= nextBin
->nextBin
;
331 cprintf("============================================================\n");
335 EventQueue::debugVerify() const
337 m5::hash_map
<long, bool> map
;
342 Event
*nextBin
= head
;
344 Event
*nextInBin
= nextBin
;
346 if (nextInBin
->when() < time
) {
347 cprintf("time goes backwards!");
350 } else if (nextInBin
->when() == time
&&
351 nextInBin
->priority() < priority
) {
352 cprintf("priority inverted!");
357 if (map
[reinterpret_cast<long>(nextInBin
)]) {
358 cprintf("Node already seen");
362 map
[reinterpret_cast<long>(nextInBin
)] = true;
364 time
= nextInBin
->when();
365 priority
= nextInBin
->priority();
367 nextInBin
= nextInBin
->nextInBin
;
370 nextBin
= nextBin
->nextBin
;
379 mainEventQueue
.dump();
384 Event::description() const
390 Event::trace(const char *action
)
392 // This DPRINTF is unconditional because calls to this function
393 // are protected by an 'if (DTRACE(Event))' in the inlined Event
396 // This is just a default implementation for derived classes where
397 // it's not worth doing anything special. If you want to put a
398 // more informative message in the trace, override this method on
399 // the particular subclass where you have the information that
400 // needs to be printed.
401 DPRINTFN("%s event %s @ %d\n", description(), action
, when());
407 cprintf("Event %s (%s)\n", name(), description());
408 cprintf("Flags: %#x\n", flags
);
410 cprintf("Created: %d\n", whenCreated
);
414 cprintf("Scheduled at %d\n", whenScheduled
);
416 cprintf("Scheduled for %d, priority %d\n", when(), _priority
);
418 cprintf("Not Scheduled\n");
422 EventQueue::EventQueue(const string
&n
)
423 : objName(n
), head(NULL
)