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 "sim/core.hh"
44 #include "sim/eventq.hh"
51 // Events on this queue are processed at the *beginning* of each
52 // cycle, before the pipeline simulation is performed.
54 EventQueue
mainEventQueue("Main Event Queue");
57 Counter
Event::instanceCounter
= 0;
70 return csprintf("Event_%d", instance
);
72 return csprintf("Event_%x", (uintptr_t)this);
78 Event::insertBefore(Event
*event
, Event
*curr
)
80 // Either way, event will be the top element in the 'in bin' list
81 // which is the pointer we need in order to look into the list, so
82 // we need to insert that into the bin list.
83 if (!curr
|| *event
< *curr
) {
84 // Insert the event before the current list since it is in the future.
85 event
->nextBin
= curr
;
86 event
->nextInBin
= NULL
;
88 // Since we're on the correct list, we need to point to the next list
89 event
->nextBin
= curr
->nextBin
; // curr->nextBin can now become stale
91 // Insert event at the top of the stack
92 event
->nextInBin
= curr
;
99 EventQueue::insert(Event
*event
)
101 // Deal with the head case
102 if (!head
|| *event
<= *head
) {
103 head
= Event::insertBefore(event
, head
);
107 // Figure out either which 'in bin' list we are on, or where a new list
108 // needs to be inserted
110 Event
*curr
= head
->nextBin
;
111 while (curr
&& *curr
< *event
) {
113 curr
= curr
->nextBin
;
116 // Note: this operation may render all nextBin pointers on the
117 // prev 'in bin' list stale (except for the top one)
118 prev
->nextBin
= Event::insertBefore(event
, curr
);
122 Event::removeItem(Event
*event
, Event
*top
)
125 Event
*next
= top
->nextInBin
;
127 // if we removed the top item, we need to handle things specially
128 // and just remove the top item, fixing up the next bin pointer of
133 next
->nextBin
= top
->nextBin
;
137 // Since we already checked the current element, we're going to
138 // keep checking event against the next element.
139 while (event
!= next
) {
141 panic("event not found!");
144 next
= next
->nextInBin
;
147 // remove next from the 'in bin' list since it's what we're looking for
148 curr
->nextInBin
= next
->nextInBin
;
153 EventQueue::remove(Event
*event
)
156 panic("event not found!");
158 // deal with an event on the head's 'in bin' list (event has the same
160 if (*head
== *event
) {
161 head
= Event::removeItem(event
, head
);
165 // Find the 'in bin' list that this event belongs on
167 Event
*curr
= head
->nextBin
;
168 while (curr
&& *curr
< *event
) {
170 curr
= curr
->nextBin
;
173 if (!curr
|| *curr
!= *event
)
174 panic("event not found!");
176 // curr points to the top item of the the correct 'in bin' list, when
177 // we remove an item, it returns the new top item (which may be
179 prev
->nextBin
= Event::removeItem(event
, curr
);
183 EventQueue::serviceOne()
186 Event
*next
= head
->nextInBin
;
187 event
->flags
.clear(Event::Scheduled
);
190 // update the next bin pointer since it could be stale
191 next
->nextBin
= head
->nextBin
;
196 // this was the only element on the 'in bin' list, so get rid of
197 // the 'in bin' list and point to the next bin list
198 head
= head
->nextBin
;
202 if (!event
->squashed()) {
204 if (event
->isExitEvent()) {
205 assert(!event
->flags
.isSet(Event::AutoDelete
)); // would be silly
209 event
->flags
.clear(Event::Squashed
);
212 if (event
->flags
.isSet(Event::AutoDelete
) && !event
->scheduled())
219 Event::serialize(std::ostream
&os
)
221 SERIALIZE_SCALAR(_when
);
222 SERIALIZE_SCALAR(_priority
);
223 short _flags
= flags
;
224 SERIALIZE_SCALAR(_flags
);
228 Event::unserialize(Checkpoint
*cp
, const string
§ion
)
231 mainEventQueue
.deschedule(this);
233 UNSERIALIZE_SCALAR(_when
);
234 UNSERIALIZE_SCALAR(_priority
);
237 UNSERIALIZE_SCALAR(_flags
);
239 // Old checkpoints had no concept of the Initialized flag
240 // so restoring from old checkpoints always fail.
241 // Events are initialized on construction but original code
242 // "flags = _flags" would just overwrite the initialization.
243 // So, read in the checkpoint flags, but then set the Initialized
244 // flag on top of it in order to avoid failures.
245 assert(initialized());
247 flags
.set(Initialized
);
249 // need to see if original event was in a scheduled, unsquashed
250 // state, but don't want to restore those flags in the current
251 // object itself (since they aren't immediately true)
252 bool wasScheduled
= flags
.isSet(Scheduled
) && !flags
.isSet(Squashed
);
253 flags
.clear(Squashed
| Scheduled
);
256 DPRINTF(Config
, "rescheduling at %d\n", _when
);
257 mainEventQueue
.schedule(this, _when
);
262 EventQueue::serialize(ostream
&os
)
264 std::list
<Event
*> eventPtrs
;
267 Event
*nextBin
= head
;
269 Event
*nextInBin
= nextBin
;
272 if (nextInBin
->flags
.isSet(Event::AutoSerialize
)) {
273 eventPtrs
.push_back(nextInBin
);
274 paramOut(os
, csprintf("event%d", numEvents
++),
277 nextInBin
= nextInBin
->nextInBin
;
280 nextBin
= nextBin
->nextBin
;
283 SERIALIZE_SCALAR(numEvents
);
285 for (std::list
<Event
*>::iterator it
= eventPtrs
.begin();
286 it
!= eventPtrs
.end(); ++it
) {
288 (*it
)->serialize(os
);
293 EventQueue::unserialize(Checkpoint
*cp
, const std::string
§ion
)
296 UNSERIALIZE_SCALAR(numEvents
);
298 std::string eventName
;
299 for (int i
= 0; i
< numEvents
; i
++) {
300 // get the pointer value associated with the event
301 paramIn(cp
, section
, csprintf("event%d", i
), eventName
);
303 // create the event based on its pointer value
304 Serializable::create(cp
, eventName
);
309 EventQueue::dump() const
311 cprintf("============================================================\n");
312 cprintf("EventQueue Dump (cycle %d)\n", curTick
);
313 cprintf("------------------------------------------------------------\n");
316 cprintf("<No Events>\n");
318 Event
*nextBin
= head
;
320 Event
*nextInBin
= nextBin
;
323 nextInBin
= nextInBin
->nextInBin
;
326 nextBin
= nextBin
->nextBin
;
330 cprintf("============================================================\n");
334 EventQueue::debugVerify() const
336 m5::hash_map
<long, bool> map
;
341 Event
*nextBin
= head
;
343 Event
*nextInBin
= nextBin
;
345 if (nextInBin
->when() < time
) {
346 cprintf("time goes backwards!");
349 } else if (nextInBin
->when() == time
&&
350 nextInBin
->priority() < priority
) {
351 cprintf("priority inverted!");
356 if (map
[reinterpret_cast<long>(nextInBin
)]) {
357 cprintf("Node already seen");
361 map
[reinterpret_cast<long>(nextInBin
)] = true;
363 time
= nextInBin
->when();
364 priority
= nextInBin
->priority();
366 nextInBin
= nextInBin
->nextInBin
;
369 nextBin
= nextBin
->nextBin
;
378 mainEventQueue
.dump();
383 Event::description() const
389 Event::trace(const char *action
)
391 // This DPRINTF is unconditional because calls to this function
392 // are protected by an 'if (DTRACE(Event))' in the inlined Event
395 // This is just a default implementation for derived classes where
396 // it's not worth doing anything special. If you want to put a
397 // more informative message in the trace, override this method on
398 // the particular subclass where you have the information that
399 // needs to be printed.
400 DPRINTFN("%s event %s @ %d\n", description(), action
, when());
406 cprintf("Event %s (%s)\n", name(), description());
407 cprintf("Flags: %#x\n", flags
);
409 cprintf("Created: %d\n", whenCreated
);
413 cprintf("Scheduled at %d\n", whenScheduled
);
415 cprintf("Scheduled for %d, priority %d\n", when(), _priority
);
417 cprintf("Not Scheduled\n");
421 EventQueue::EventQueue(const string
&n
)
422 : objName(n
), head(NULL
)