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;
69 return csprintf("Event_%d", instance
);
71 return csprintf("Event_%x", (uintptr_t)this);
77 Event::insertBefore(Event
*event
, Event
*curr
)
79 // Either way, event will be the top element in the 'in bin' list
80 // which is the pointer we need in order to look into the list, so
81 // we need to insert that into the bin list.
82 if (!curr
|| *event
< *curr
) {
83 // Insert the event before the current list since it is in the future.
84 event
->nextBin
= curr
;
85 event
->nextInBin
= NULL
;
87 // Since we're on the correct list, we need to point to the next list
88 event
->nextBin
= curr
->nextBin
; // curr->nextBin can now become stale
90 // Insert event at the top of the stack
91 event
->nextInBin
= curr
;
98 EventQueue::insert(Event
*event
)
100 // Deal with the head case
101 if (!head
|| *event
<= *head
) {
102 head
= Event::insertBefore(event
, head
);
106 // Figure out either which 'in bin' list we are on, or where a new list
107 // needs to be inserted
109 Event
*curr
= head
->nextBin
;
110 while (curr
&& *curr
< *event
) {
112 curr
= curr
->nextBin
;
115 // Note: this operation may render all nextBin pointers on the
116 // prev 'in bin' list stale (except for the top one)
117 prev
->nextBin
= Event::insertBefore(event
, curr
);
121 Event::removeItem(Event
*event
, Event
*top
)
124 Event
*next
= top
->nextInBin
;
126 // if we removed the top item, we need to handle things specially
127 // and just remove the top item, fixing up the next bin pointer of
132 next
->nextBin
= top
->nextBin
;
136 // Since we already checked the current element, we're going to
137 // keep checking event against the next element.
138 while (event
!= next
) {
140 panic("event not found!");
143 next
= next
->nextInBin
;
146 // remove next from the 'in bin' list since it's what we're looking for
147 curr
->nextInBin
= next
->nextInBin
;
152 EventQueue::remove(Event
*event
)
155 panic("event not found!");
157 // deal with an event on the head's 'in bin' list (event has the same
159 if (*head
== *event
) {
160 head
= Event::removeItem(event
, head
);
164 // Find the 'in bin' list that this event belongs on
166 Event
*curr
= head
->nextBin
;
167 while (curr
&& *curr
< *event
) {
169 curr
= curr
->nextBin
;
172 if (!curr
|| *curr
!= *event
)
173 panic("event not found!");
175 // curr points to the top item of the the correct 'in bin' list, when
176 // we remove an item, it returns the new top item (which may be
178 prev
->nextBin
= Event::removeItem(event
, curr
);
182 EventQueue::serviceOne()
185 Event
*next
= head
->nextInBin
;
186 event
->flags
.clear(Event::Scheduled
);
189 // update the next bin pointer since it could be stale
190 next
->nextBin
= head
->nextBin
;
195 // this was the only element on the 'in bin' list, so get rid of
196 // the 'in bin' list and point to the next bin list
197 head
= head
->nextBin
;
201 if (!event
->squashed()) {
203 if (event
->isExitEvent()) {
204 assert(!event
->flags
.isSet(Event::AutoDelete
)); // would be silly
208 event
->flags
.clear(Event::Squashed
);
211 if (event
->flags
.isSet(Event::AutoDelete
) && !event
->scheduled())
218 Event::serialize(std::ostream
&os
)
220 SERIALIZE_SCALAR(_when
);
221 SERIALIZE_SCALAR(_priority
);
222 short _flags
= flags
;
223 SERIALIZE_SCALAR(_flags
);
227 Event::unserialize(Checkpoint
*cp
, const string
§ion
)
230 mainEventQueue
.deschedule(this);
232 UNSERIALIZE_SCALAR(_when
);
233 UNSERIALIZE_SCALAR(_priority
);
235 // need to see if original event was in a scheduled, unsquashed
236 // state, but don't want to restore those flags in the current
237 // object itself (since they aren't immediately true)
239 UNSERIALIZE_SCALAR(_flags
);
242 bool wasScheduled
= flags
.isSet(Scheduled
) && !flags
.isSet(Squashed
);
243 flags
.clear(Squashed
| Scheduled
);
246 DPRINTF(Config
, "rescheduling at %d\n", _when
);
247 mainEventQueue
.schedule(this, _when
);
252 EventQueue::serialize(ostream
&os
)
254 std::list
<Event
*> eventPtrs
;
257 Event
*nextBin
= head
;
259 Event
*nextInBin
= nextBin
;
262 if (nextInBin
->flags
.isSet(Event::AutoSerialize
)) {
263 eventPtrs
.push_back(nextInBin
);
264 paramOut(os
, csprintf("event%d", numEvents
++),
267 nextInBin
= nextInBin
->nextInBin
;
270 nextBin
= nextBin
->nextBin
;
273 SERIALIZE_SCALAR(numEvents
);
275 for (std::list
<Event
*>::iterator it
= eventPtrs
.begin();
276 it
!= eventPtrs
.end(); ++it
) {
278 (*it
)->serialize(os
);
283 EventQueue::unserialize(Checkpoint
*cp
, const std::string
§ion
)
286 UNSERIALIZE_SCALAR(numEvents
);
288 std::string eventName
;
289 for (int i
= 0; i
< numEvents
; i
++) {
290 // get the pointer value associated with the event
291 paramIn(cp
, section
, csprintf("event%d", i
), eventName
);
293 // create the event based on its pointer value
294 Serializable::create(cp
, eventName
);
299 EventQueue::dump() const
301 cprintf("============================================================\n");
302 cprintf("EventQueue Dump (cycle %d)\n", curTick
);
303 cprintf("------------------------------------------------------------\n");
306 cprintf("<No Events>\n");
308 Event
*nextBin
= head
;
310 Event
*nextInBin
= nextBin
;
313 nextInBin
= nextInBin
->nextInBin
;
316 nextBin
= nextBin
->nextBin
;
320 cprintf("============================================================\n");
324 EventQueue::debugVerify() const
326 m5::hash_map
<long, bool> map
;
331 Event
*nextBin
= head
;
333 Event
*nextInBin
= nextBin
;
335 if (nextInBin
->when() < time
) {
336 cprintf("time goes backwards!");
339 } else if (nextInBin
->when() == time
&&
340 nextInBin
->priority() < priority
) {
341 cprintf("priority inverted!");
346 if (map
[reinterpret_cast<long>(nextInBin
)]) {
347 cprintf("Node already seen");
351 map
[reinterpret_cast<long>(nextInBin
)] = true;
353 time
= nextInBin
->when();
354 priority
= nextInBin
->priority();
356 nextInBin
= nextInBin
->nextInBin
;
359 nextBin
= nextBin
->nextBin
;
368 mainEventQueue
.dump();
373 Event::description() const
379 Event::trace(const char *action
)
381 // This DPRINTF is unconditional because calls to this function
382 // are protected by an 'if (DTRACE(Event))' in the inlined Event
385 // This is just a default implementation for derived classes where
386 // it's not worth doing anything special. If you want to put a
387 // more informative message in the trace, override this method on
388 // the particular subclass where you have the information that
389 // needs to be printed.
390 DPRINTFN("%s event %s @ %d\n", description(), action
, when());
396 cprintf("Event %s (%s)\n", name(), description());
397 cprintf("Flags: %#x\n", flags
);
399 cprintf("Created: %d\n", whenCreated
);
403 cprintf("Scheduled at %d\n", whenScheduled
);
405 cprintf("Scheduled for %d, priority %d\n", when(), _priority
);
407 cprintf("Not Scheduled\n");