eventq.cc (5501:b1beee9351a4) eventq.cc (5502:f0f8a3ee5aad)
1/*
2 * Copyright (c) 2000-2005 The Regents of The University of Michigan
1/*
2 * Copyright (c) 2000-2005 The Regents of The University of Michigan
3 * Copyright (c) 2008 The Hewlett-Packard Development Company
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the

--- 19 unchanged lines hidden (view full) ---

30 * Steve Raasch
31 */
32
33#include <cassert>
34#include <iostream>
35#include <string>
36#include <vector>
37
4 * All rights reserved.
5 *
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

--- 19 unchanged lines hidden (view full) ---

31 * Steve Raasch
32 */
33
34#include <cassert>
35#include <iostream>
36#include <string>
37#include <vector>
38
39#include "base/hashmap.hh"
38#include "base/misc.hh"
39#include "base/trace.hh"
40#include "cpu/smt.hh"
41#include "sim/core.hh"
42#include "sim/eventq.hh"
43
44using namespace std;
45

--- 4 unchanged lines hidden (view full) ---

50// cycle, before the pipeline simulation is performed.
51//
52EventQueue mainEventQueue("MainEventQueue");
53
54#ifndef NDEBUG
55Counter Event::instanceCounter = 0;
56#endif
57
40#include "base/misc.hh"
41#include "base/trace.hh"
42#include "cpu/smt.hh"
43#include "sim/core.hh"
44#include "sim/eventq.hh"
45
46using namespace std;
47

--- 4 unchanged lines hidden (view full) ---

52// cycle, before the pipeline simulation is performed.
53//
54EventQueue mainEventQueue("MainEventQueue");
55
56#ifndef NDEBUG
57Counter Event::instanceCounter = 0;
58#endif
59
60inline void
61insertBefore(Event *event, Event *curr)
62{
63 // Either way, event will be the last element in the 'in bin' list
64 // which is the pointer we need in order to look into the list, so
65 // we need to insert that into the bin list.
66 if (!curr || *event < *curr) {
67 // Insert the event before the current list since it is in the future.
68 event->nextBin = curr;
69
70 // We need to create a new 'in bin' list
71 event->nextInBin = event;
72 } else {
73 // Since we're on the correct list, we need to point to the next list
74 event->nextBin = curr->nextBin; // curr->nextBin can now become stale
75
76 // Insert event at the end of the 'nextInBin' curr is the last
77 // element on the 'in bin' list and curr->nextInBin is the first
78
79 event->nextInBin = curr->nextInBin; // event->nextInBin needs to
80 // point to the first
81 curr->nextInBin = event; // curr->nextInBin is now second to last
82 }
83}
84
58void
59EventQueue::insert(Event *event)
60{
85void
86EventQueue::insert(Event *event)
87{
61 if (head == NULL || event->when() < head->when() ||
62 (event->when() == head->when() &&
63 event->priority() <= head->priority())) {
64 event->next = head;
88 // Deal with the head case
89 if (!head || *event <= *head) {
90 insertBefore(event, head);
65 head = event;
91 head = event;
66 } else {
67 Event *prev = head;
68 Event *curr = head->next;
92 return;
93 }
69
94
70 while (curr) {
71 if (event->when() <= curr->when() &&
72 (event->when() < curr->when() ||
73 event->priority() <= curr->priority()))
74 break;
95 // Figure out either which 'in bin' list we are on, or where a new list
96 // needs to be inserted
97 Event *curr = head;
98 Event *next = head->nextBin;
99 while (next && *next < *event) {
100 curr = next;
101 next = next->nextBin;
102 }
75
103
76 prev = curr;
77 curr = curr->next;
78 }
104 insertBefore(event, next);
105 curr->nextBin = event; // all nextBin pointers on the curr
106 // 'in bin' list are now stale
107}
79
108
80 event->next = curr;
81 prev->next = event;
109inline Event *
110removeItem(Event *event, Event *last)
111{
112 Event *prev = last;
113 Event *curr = last->nextInBin;
114
115 while (event != curr) {
116 if (curr == last)
117 panic("event not found!");
118
119 prev = curr;
120 curr = curr->nextInBin;
82 }
121 }
122
123 // If this was the only item in this list, we're done.
124 if (prev == curr)
125 return NULL;
126
127 // remove curr from the 'in bin' list since it's what we're looking for
128 prev->nextInBin = curr->nextInBin;
129
130 // If we didn't remove the last item, we're done
131 if (curr != last)
132 return last;
133
134 // if we removed the last item, the new last item is prev
135 // fix it up since it might be stale and return it
136 prev->nextBin = last->nextBin;
137 return prev;
83}
84
85void
86EventQueue::remove(Event *event)
87{
88 if (head == NULL)
138}
139
140void
141EventQueue::remove(Event *event)
142{
143 if (head == NULL)
89 return;
144 panic("event not found!");
90
145
91 if (head == event){
92 head = event->next;
146 // deal with an event on the head's 'in bin' list (event has the same
147 // time as the head)
148 if (*head == *event) {
149 head = removeItem(event, head);
150 if (!head)
151 head = event->nextBin;
93 return;
94 }
95
152 return;
153 }
154
155 // Find the 'in bin' list that this event belongs on
96 Event *prev = head;
156 Event *prev = head;
97 Event *curr = head->next;
98 while (curr && curr != event) {
157 Event *curr = head->nextBin;
158 while (curr && *curr < *event) {
99 prev = curr;
159 prev = curr;
100 curr = curr->next;
160 curr = curr->nextBin;
101 }
102
161 }
162
103 if (curr == event)
104 prev->next = curr->next;
163 if (!curr || *curr != *event)
164 panic("event not found!");
165
166 // curr points to the last item of the the correct 'in bin' list, when
167 // we remove an item, it returns the new last item (which may be
168 // unchanged)
169 Event *last = removeItem(event, curr);
170 if (!last) {
171 // The current item was removed, so we need to fix the bin list
172 prev->nextBin = curr->nextBin;
173 } else if (last != curr) {
174 // We have a new last item, so we need to update the bin list
175 prev->nextBin = last;
176 }
105}
106
107Event *
108EventQueue::serviceOne()
109{
177}
178
179Event *
180EventQueue::serviceOne()
181{
110 Event *event = head;
182 // grab the first element
183 Event *event = head->nextInBin;
111 event->clearFlags(Event::Scheduled);
184 event->clearFlags(Event::Scheduled);
112 head = event->next;
113
185
186 if (head == event) {
187 // this was the only element on the 'in bin' list, so get rid of
188 // the 'in bin' list and point to the next bin list
189 head = event->nextBin;
190 } else {
191 // maintain head->nextInBin as the first element
192 head->nextInBin = event->nextInBin;
193 }
194
114 // handle action
115 if (!event->squashed()) {
116 event->process();
117 if (event->isExitEvent()) {
118 assert(!event->getFlags(Event::AutoDelete)); // would be silly
119 return event;
120 }
121 } else {
122 event->clearFlags(Event::Squashed);
123 }
124
125 if (event->getFlags(Event::AutoDelete) && !event->scheduled())
126 delete event;
127
128 return NULL;
129}
130
195 // handle action
196 if (!event->squashed()) {
197 event->process();
198 if (event->isExitEvent()) {
199 assert(!event->getFlags(Event::AutoDelete)); // would be silly
200 return event;
201 }
202 } else {
203 event->clearFlags(Event::Squashed);
204 }
205
206 if (event->getFlags(Event::AutoDelete) && !event->scheduled())
207 delete event;
208
209 return NULL;
210}
211
131
132void
133Event::serialize(std::ostream &os)
134{
135 SERIALIZE_SCALAR(_when);
136 SERIALIZE_SCALAR(_priority);
137 SERIALIZE_ENUM(_flags);
138}
139
212void
213Event::serialize(std::ostream &os)
214{
215 SERIALIZE_SCALAR(_when);
216 SERIALIZE_SCALAR(_priority);
217 SERIALIZE_ENUM(_flags);
218}
219
140
141void
142Event::unserialize(Checkpoint *cp, const string &section)
143{
144 if (scheduled())
145 deschedule();
146
147 UNSERIALIZE_SCALAR(_when);
148 UNSERIALIZE_SCALAR(_priority);

--- 12 unchanged lines hidden (view full) ---

161}
162
163void
164EventQueue::serialize(ostream &os)
165{
166 std::list<Event *> eventPtrs;
167
168 int numEvents = 0;
220void
221Event::unserialize(Checkpoint *cp, const string &section)
222{
223 if (scheduled())
224 deschedule();
225
226 UNSERIALIZE_SCALAR(_when);
227 UNSERIALIZE_SCALAR(_priority);

--- 12 unchanged lines hidden (view full) ---

240}
241
242void
243EventQueue::serialize(ostream &os)
244{
245 std::list<Event *> eventPtrs;
246
247 int numEvents = 0;
169 Event *event = head;
170 while (event) {
171 if (event->getFlags(Event::AutoSerialize)) {
172 eventPtrs.push_back(event);
173 paramOut(os, csprintf("event%d", numEvents++), event->name());
174 }
175 event = event->next;
248 Event *nextBin = head;
249 while (nextBin) {
250 Event *nextInBin = nextBin->nextInBin;
251
252 do {
253 if (nextInBin->getFlags(Event::AutoSerialize)) {
254 eventPtrs.push_back(nextInBin);
255 paramOut(os, csprintf("event%d", numEvents++),
256 nextInBin->name());
257 }
258 nextInBin = nextInBin->nextInBin;
259 } while (nextInBin != nextBin);
260
261 nextBin = nextBin->nextBin;
176 }
177
178 SERIALIZE_SCALAR(numEvents);
179
262 }
263
264 SERIALIZE_SCALAR(numEvents);
265
180 for (std::list<Event *>::iterator it=eventPtrs.begin();
266 for (std::list<Event *>::iterator it = eventPtrs.begin();
181 it != eventPtrs.end(); ++it) {
182 (*it)->nameOut(os);
183 (*it)->serialize(os);
184 }
185}
186
187void
188EventQueue::unserialize(Checkpoint *cp, const std::string &section)

--- 13 unchanged lines hidden (view full) ---

202
203void
204EventQueue::dump() const
205{
206 cprintf("============================================================\n");
207 cprintf("EventQueue Dump (cycle %d)\n", curTick);
208 cprintf("------------------------------------------------------------\n");
209
267 it != eventPtrs.end(); ++it) {
268 (*it)->nameOut(os);
269 (*it)->serialize(os);
270 }
271}
272
273void
274EventQueue::unserialize(Checkpoint *cp, const std::string &section)

--- 13 unchanged lines hidden (view full) ---

288
289void
290EventQueue::dump() const
291{
292 cprintf("============================================================\n");
293 cprintf("EventQueue Dump (cycle %d)\n", curTick);
294 cprintf("------------------------------------------------------------\n");
295
296 m5::hash_map<long, bool> map;
297
210 if (empty())
211 cprintf("<No Events>\n");
212 else {
298 if (empty())
299 cprintf("<No Events>\n");
300 else {
213 Event *event = head;
214 while (event) {
215 event->dump();
216 event = event->next;
301 Event *nextBin = head;
302 while (nextBin) {
303 Event *nextInBin = nextBin;
304 if (map[reinterpret_cast<long>(nextInBin)])
305 break;
306 map[reinterpret_cast<long>(nextInBin)] = true;
307 do {
308 nextInBin = nextInBin->nextInBin;
309 nextInBin->dump();
310 } while (nextInBin != nextBin);
311
312 nextBin = nextBin->nextBin;
217 }
218 }
219
220 cprintf("============================================================\n");
221}
222
313 }
314 }
315
316 cprintf("============================================================\n");
317}
318
319bool
320EventQueue::debugVerify() const
321{
322 m5::hash_map<long, bool> map;
323
324 Tick time = 0;
325 short priority = 0;
326
327 Event *nextBin = head;
328 while (nextBin) {
329 Event *nextInBin = nextBin->nextInBin;
330 do {
331 if (nextInBin->when() < time) {
332 cprintf("time goes backwards!");
333 nextInBin->dump();
334 return false;
335 } else if (nextInBin->when() == time &&
336 nextInBin->priority() < priority) {
337 cprintf("priority inverted!");
338 nextInBin->dump();
339 return false;
340 }
341
342 if (map[reinterpret_cast<long>(nextInBin)]) {
343 cprintf("Node already seen");
344 nextInBin->dump();
345 return false;
346 }
347 map[reinterpret_cast<long>(nextInBin)] = true;
348
349 time = nextInBin->when();
350 priority = nextInBin->priority();
351
352 nextInBin = nextInBin->nextInBin;
353 } while (nextInBin != nextBin);
354
355 nextBin = nextBin->nextBin;
356 }
357
358 return true;
359}
360
223void
224dumpMainQueue()
225{
226 mainEventQueue.dump();
227}
228
229
230const char *

--- 37 unchanged lines hidden --- 		361void
362dumpMainQueue()
363{
364 mainEventQueue.dump();
365}
366
367
368const char *

--- 37 unchanged lines hidden ---