eventq.cc (5502:f0f8a3ee5aad) eventq.cc (5503:cf464d02bc57)
1/*
2 * Copyright (c) 2000-2005 The Regents of The University of Michigan
3 * Copyright (c) 2008 The Hewlett-Packard Development Company
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

--- 43 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
1/*
2 * Copyright (c) 2000-2005 The Regents of The University of Michigan
3 * Copyright (c) 2008 The Hewlett-Packard Development Company
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

--- 43 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
60inline Event *
61insertBefore(Event *event, Event *curr)
62{
61insertBefore(Event *event, Event *curr)
62{
63 // Either way, event will be the last element in the 'in bin' list
63 // Either way, event will be the top 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;
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;
69 event->nextInBin = NULL;
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
70 } else {
71 // Since we're on the correct list, we need to point to the next list
72 event->nextBin = curr->nextBin; // curr->nextBin can now become stale
73
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
74 // Insert event at the top of the stack
75 event->nextInBin = curr;
82 }
76 }
77
78 return event;
83}
84
85void
86EventQueue::insert(Event *event)
87{
88 // Deal with the head case
89 if (!head || *event <= *head) {
79}
80
81void
82EventQueue::insert(Event *event)
83{
84 // Deal with the head case
85 if (!head || *event <= *head) {
90 insertBefore(event, head);
91 head = event;
86 head = insertBefore(event, head);
92 return;
93 }
94
95 // Figure out either which 'in bin' list we are on, or where a new list
96 // needs to be inserted
87 return;
88 }
89
90 // Figure out either which 'in bin' list we are on, or where a new list
91 // 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;
92 Event *prev = head;
93 Event *curr = head->nextBin;
94 while (curr && *curr < *event) {
95 prev = curr;
96 curr = curr->nextBin;
102 }
103
97 }
98
104 insertBefore(event, next);
105 curr->nextBin = event; // all nextBin pointers on the curr
106 // 'in bin' list are now stale
99 // Note: this operation may render all nextBin pointers on the
100 // prev 'in bin' list stale (except for the top one)
101 prev->nextBin = insertBefore(event, curr);
107}
108
109inline Event *
102}
103
104inline Event *
110removeItem(Event *event, Event *last)
105removeItem(Event *event, Event *top)
111{
106{
112 Event *prev = last;
113 Event *curr = last->nextInBin;
107 Event *curr = top;
108 Event *next = top->nextInBin;
114
109
115 while (event != curr) {
116 if (curr == last)
110 // if we removed the top item, we need to handle things specially
111 // and just remove the top item, fixing up the next bin pointer of
112 // the new top item
113 if (event == top) {
114 if (!next)
115 return top->nextBin;
116 next->nextBin = top->nextBin;
117 return next;
118 }
119
120 // Since we already checked the current element, we're going to
121 // keep checking event against the next element.
122 while (event != next) {
123 if (!next)
117 panic("event not found!");
118
124 panic("event not found!");
125
119 prev = curr;
120 curr = curr->nextInBin;
126 curr = next;
127 next = next->nextInBin;
121 }
122
128 }
129
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;
130 // remove next from the 'in bin' list since it's what we're looking for
131 curr->nextInBin = next->nextInBin;
132 return top;
138}
139
140void
141EventQueue::remove(Event *event)
142{
143 if (head == NULL)
144 panic("event not found!");
145
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);
133}
134
135void
136EventQueue::remove(Event *event)
137{
138 if (head == NULL)
139 panic("event not found!");
140
141 // deal with an event on the head's 'in bin' list (event has the same
142 // time as the head)
143 if (*head == *event) {
144 head = removeItem(event, head);
150 if (!head)
151 head = event->nextBin;
152 return;
153 }
154
155 // Find the 'in bin' list that this event belongs on
156 Event *prev = head;
157 Event *curr = head->nextBin;
158 while (curr && *curr < *event) {
159 prev = curr;
160 curr = curr->nextBin;
161 }
162
163 if (!curr || *curr != *event)
164 panic("event not found!");
165
145 return;
146 }
147
148 // Find the 'in bin' list that this event belongs on
149 Event *prev = head;
150 Event *curr = head->nextBin;
151 while (curr && *curr < *event) {
152 prev = curr;
153 curr = curr->nextBin;
154 }
155
156 if (!curr || *curr != *event)
157 panic("event not found!");
158
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
159 // curr points to the top item of the the correct 'in bin' list, when
160 // we remove an item, it returns the new top item (which may be
168 // unchanged)
161 // 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 }
162 prev->nextBin = removeItem(event, curr);
177}
178
179Event *
180EventQueue::serviceOne()
181{
163}
164
165Event *
166EventQueue::serviceOne()
167{
182 // grab the first element
183 Event *event = head->nextInBin;
168 Event *event = head;
169 Event *next = head->nextInBin;
184 event->clearFlags(Event::Scheduled);
185
170 event->clearFlags(Event::Scheduled);
171
186 if (head == event) {
172 if (next) {
173 // update the next bin pointer since it could be stale
174 next->nextBin = head->nextBin;
175
176 // pop the stack
177 head = next;
178 } else {
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
179 // this was the only element on the 'in bin' list, so get rid of
180 // 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;
181 head = head->nextBin;
193 }
194
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;

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

242void
243EventQueue::serialize(ostream &os)
244{
245 std::list<Event *> eventPtrs;
246
247 int numEvents = 0;
248 Event *nextBin = head;
249 while (nextBin) {
182 }
183
184 // handle action
185 if (!event->squashed()) {
186 event->process();
187 if (event->isExitEvent()) {
188 assert(!event->getFlags(Event::AutoDelete)); // would be silly
189 return event;

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

231void
232EventQueue::serialize(ostream &os)
233{
234 std::list<Event *> eventPtrs;
235
236 int numEvents = 0;
237 Event *nextBin = head;
238 while (nextBin) {
250 Event *nextInBin = nextBin->nextInBin;
239 Event *nextInBin = nextBin;
251
240
252 do {
241 while (nextInBin) {
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;
242 if (nextInBin->getFlags(Event::AutoSerialize)) {
243 eventPtrs.push_back(nextInBin);
244 paramOut(os, csprintf("event%d", numEvents++),
245 nextInBin->name());
246 }
247 nextInBin = nextInBin->nextInBin;
259 } while (nextInBin != nextBin);
248 }
260
261 nextBin = nextBin->nextBin;
262 }
263
264 SERIALIZE_SCALAR(numEvents);
265
266 for (std::list<Event *>::iterator it = eventPtrs.begin();
267 it != eventPtrs.end(); ++it) {

--- 20 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
249
250 nextBin = nextBin->nextBin;
251 }
252
253 SERIALIZE_SCALAR(numEvents);
254
255 for (std::list<Event *>::iterator it = eventPtrs.begin();
256 it != eventPtrs.end(); ++it) {

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

277
278void
279EventQueue::dump() const
280{
281 cprintf("============================================================\n");
282 cprintf("EventQueue Dump (cycle %d)\n", curTick);
283 cprintf("------------------------------------------------------------\n");
284
296 m5::hash_map<long, bool> map;
297
298 if (empty())
299 cprintf("<No Events>\n");
300 else {
301 Event *nextBin = head;
302 while (nextBin) {
303 Event *nextInBin = nextBin;
285 if (empty())
286 cprintf("<No Events>\n");
287 else {
288 Event *nextBin = head;
289 while (nextBin) {
290 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;
291 while (nextInBin) {
309 nextInBin->dump();
292 nextInBin->dump();
310 } while (nextInBin != nextBin);
293 nextInBin = nextInBin->nextInBin;
294 }
311
312 nextBin = nextBin->nextBin;
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) {
295
296 nextBin = nextBin->nextBin;
297 }
298 }
299
300 cprintf("============================================================\n");
301}
302
303bool
304EventQueue::debugVerify() const
305{
306 m5::hash_map<long, bool> map;
307
308 Tick time = 0;
309 short priority = 0;
310
311 Event *nextBin = head;
312 while (nextBin) {
329 Event *nextInBin = nextBin->nextInBin;
330 do {
313 Event *nextInBin = nextBin;
314 while (nextInBin) {
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();

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

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;
315 if (nextInBin->when() < time) {
316 cprintf("time goes backwards!");
317 nextInBin->dump();
318 return false;
319 } else if (nextInBin->when() == time &&
320 nextInBin->priority() < priority) {
321 cprintf("priority inverted!");
322 nextInBin->dump();

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

329 return false;
330 }
331 map[reinterpret_cast<long>(nextInBin)] = true;
332
333 time = nextInBin->when();
334 priority = nextInBin->priority();
335
336 nextInBin = nextInBin->nextInBin;
353 } while (nextInBin != nextBin);
337 }
354
355 nextBin = nextBin->nextBin;
356 }
357
358 return true;
359}
360
361void

--- 44 unchanged lines hidden --- 		338
339 nextBin = nextBin->nextBin;
340 }
341
342 return true;
343}
344
345void

--- 44 unchanged lines hidden ---