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
);
236 // need to see if original event was in a scheduled, unsquashed
237 // state, but don't want to restore those flags in the current
238 // object itself (since they aren't immediately true)
240 UNSERIALIZE_SCALAR(_flags
);
243 bool wasScheduled
= flags
.isSet(Scheduled
) && !flags
.isSet(Squashed
);
244 flags
.clear(Squashed
| Scheduled
);
247 DPRINTF(Config
, "rescheduling at %d\n", _when
);
248 mainEventQueue
.schedule(this, _when
);
253 EventQueue::serialize(ostream
&os
)
255 std::list
<Event
*> eventPtrs
;
258 Event
*nextBin
= head
;
260 Event
*nextInBin
= nextBin
;
263 if (nextInBin
->flags
.isSet(Event::AutoSerialize
)) {
264 eventPtrs
.push_back(nextInBin
);
265 paramOut(os
, csprintf("event%d", numEvents
++),
268 nextInBin
= nextInBin
->nextInBin
;
271 nextBin
= nextBin
->nextBin
;
274 SERIALIZE_SCALAR(numEvents
);
276 for (std::list
<Event
*>::iterator it
= eventPtrs
.begin();
277 it
!= eventPtrs
.end(); ++it
) {
279 (*it
)->serialize(os
);
284 EventQueue::unserialize(Checkpoint
*cp
, const std::string
§ion
)
287 UNSERIALIZE_SCALAR(numEvents
);
289 std::string eventName
;
290 for (int i
= 0; i
< numEvents
; i
++) {
291 // get the pointer value associated with the event
292 paramIn(cp
, section
, csprintf("event%d", i
), eventName
);
294 // create the event based on its pointer value
295 Serializable::create(cp
, eventName
);
300 EventQueue::dump() const
302 cprintf("============================================================\n");
303 cprintf("EventQueue Dump (cycle %d)\n", curTick
);
304 cprintf("------------------------------------------------------------\n");
307 cprintf("<No Events>\n");
309 Event
*nextBin
= head
;
311 Event
*nextInBin
= nextBin
;
314 nextInBin
= nextInBin
->nextInBin
;
317 nextBin
= nextBin
->nextBin
;
321 cprintf("============================================================\n");
325 EventQueue::debugVerify() const
327 m5::hash_map
<long, bool> map
;
332 Event
*nextBin
= head
;
334 Event
*nextInBin
= nextBin
;
336 if (nextInBin
->when() < time
) {
337 cprintf("time goes backwards!");
340 } else if (nextInBin
->when() == time
&&
341 nextInBin
->priority() < priority
) {
342 cprintf("priority inverted!");
347 if (map
[reinterpret_cast<long>(nextInBin
)]) {
348 cprintf("Node already seen");
352 map
[reinterpret_cast<long>(nextInBin
)] = true;
354 time
= nextInBin
->when();
355 priority
= nextInBin
->priority();
357 nextInBin
= nextInBin
->nextInBin
;
360 nextBin
= nextBin
->nextBin
;
369 mainEventQueue
.dump();
374 Event::description() const
380 Event::trace(const char *action
)
382 // This DPRINTF is unconditional because calls to this function
383 // are protected by an 'if (DTRACE(Event))' in the inlined Event
386 // This is just a default implementation for derived classes where
387 // it's not worth doing anything special. If you want to put a
388 // more informative message in the trace, override this method on
389 // the particular subclass where you have the information that
390 // needs to be printed.
391 DPRINTFN("%s event %s @ %d\n", description(), action
, when());
397 cprintf("Event %s (%s)\n", name(), description());
398 cprintf("Flags: %#x\n", flags
);
400 cprintf("Created: %d\n", whenCreated
);
404 cprintf("Scheduled at %d\n", whenScheduled
);
406 cprintf("Scheduled for %d, priority %d\n", when(), _priority
);
408 cprintf("Not Scheduled\n");
412 EventQueue::EventQueue(const string
&n
)
413 : objName(n
), head(NULL
)