summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNathan Binkert <nate@binkert.org>2008-07-11 08:48:50 -0700
committerNathan Binkert <nate@binkert.org>2008-07-11 08:48:50 -0700
commitf90b08a5ccd83800e0263e6e13af7d8c87b3cdf4 (patch)
tree3d62aa636507c46ee894865202ec8d0779ac63d1
parent10df68dd727d37876f3d9526739b1c49d195e222 (diff)
downloadgem5-f90b08a5ccd83800e0263e6e13af7d8c87b3cdf4.tar.xz
eventq: change the event datastructure back to LIFO.
The status quo is preferred since it is less likely that people will rely on LIFO than FIFO, and when we move to a parallelized M5, no ordering between events of the same time/priority will be guaranteed.
-rw-r--r--src/sim/eventq.cc136
-rw-r--r--src/sim/eventq.hh6
2 files changed, 63 insertions, 79 deletions
diff --git a/src/sim/eventq.cc b/src/sim/eventq.cc
index 2b61df26e..4f0b51e08 100644
--- a/src/sim/eventq.cc
+++ b/src/sim/eventq.cc
@@ -57,29 +57,25 @@ EventQueue mainEventQueue("MainEventQueue");
Counter Event::instanceCounter = 0;
#endif
-inline void
+inline Event *
insertBefore(Event *event, Event *curr)
{
- // Either way, event will be the last element in the 'in bin' list
+ // Either way, event will be the top element in the 'in bin' list
// which is the pointer we need in order to look into the list, so
// we need to insert that into the bin list.
if (!curr || *event < *curr) {
// Insert the event before the current list since it is in the future.
event->nextBin = curr;
-
- // We need to create a new 'in bin' list
- event->nextInBin = event;
+ event->nextInBin = NULL;
} else {
// Since we're on the correct list, we need to point to the next list
event->nextBin = curr->nextBin; // curr->nextBin can now become stale
- // Insert event at the end of the 'nextInBin' curr is the last
- // element on the 'in bin' list and curr->nextInBin is the first
-
- event->nextInBin = curr->nextInBin; // event->nextInBin needs to
- // point to the first
- curr->nextInBin = event; // curr->nextInBin is now second to last
+ // Insert event at the top of the stack
+ event->nextInBin = curr;
}
+
+ return event;
}
void
@@ -87,54 +83,53 @@ EventQueue::insert(Event *event)
{
// Deal with the head case
if (!head || *event <= *head) {
- insertBefore(event, head);
- head = event;
+ head = insertBefore(event, head);
return;
}
// Figure out either which 'in bin' list we are on, or where a new list
// needs to be inserted
- Event *curr = head;
- Event *next = head->nextBin;
- while (next && *next < *event) {
- curr = next;
- next = next->nextBin;
+ Event *prev = head;
+ Event *curr = head->nextBin;
+ while (curr && *curr < *event) {
+ prev = curr;
+ curr = curr->nextBin;
}
- insertBefore(event, next);
- curr->nextBin = event; // all nextBin pointers on the curr
- // 'in bin' list are now stale
+ // Note: this operation may render all nextBin pointers on the
+ // prev 'in bin' list stale (except for the top one)
+ prev->nextBin = insertBefore(event, curr);
}
inline Event *
-removeItem(Event *event, Event *last)
+removeItem(Event *event, Event *top)
{
- Event *prev = last;
- Event *curr = last->nextInBin;
+ Event *curr = top;
+ Event *next = top->nextInBin;
+
+ // if we removed the top item, we need to handle things specially
+ // and just remove the top item, fixing up the next bin pointer of
+ // the new top item
+ if (event == top) {
+ if (!next)
+ return top->nextBin;
+ next->nextBin = top->nextBin;
+ return next;
+ }
- while (event != curr) {
- if (curr == last)
+ // Since we already checked the current element, we're going to
+ // keep checking event against the next element.
+ while (event != next) {
+ if (!next)
panic("event not found!");
- prev = curr;
- curr = curr->nextInBin;
+ curr = next;
+ next = next->nextInBin;
}
- // If this was the only item in this list, we're done.
- if (prev == curr)
- return NULL;
-
- // remove curr from the 'in bin' list since it's what we're looking for
- prev->nextInBin = curr->nextInBin;
-
- // If we didn't remove the last item, we're done
- if (curr != last)
- return last;
-
- // if we removed the last item, the new last item is prev
- // fix it up since it might be stale and return it
- prev->nextBin = last->nextBin;
- return prev;
+ // remove next from the 'in bin' list since it's what we're looking for
+ curr->nextInBin = next->nextInBin;
+ return top;
}
void
@@ -147,8 +142,6 @@ EventQueue::remove(Event *event)
// time as the head)
if (*head == *event) {
head = removeItem(event, head);
- if (!head)
- head = event->nextBin;
return;
}
@@ -163,33 +156,29 @@ EventQueue::remove(Event *event)
if (!curr || *curr != *event)
panic("event not found!");
- // curr points to the last item of the the correct 'in bin' list, when
- // we remove an item, it returns the new last item (which may be
+ // curr points to the top item of the the correct 'in bin' list, when
+ // we remove an item, it returns the new top item (which may be
// unchanged)
- Event *last = removeItem(event, curr);
- if (!last) {
- // The current item was removed, so we need to fix the bin list
- prev->nextBin = curr->nextBin;
- } else if (last != curr) {
- // We have a new last item, so we need to update the bin list
- prev->nextBin = last;
- }
+ prev->nextBin = removeItem(event, curr);
}
Event *
EventQueue::serviceOne()
{
- // grab the first element
- Event *event = head->nextInBin;
+ Event *event = head;
+ Event *next = head->nextInBin;
event->clearFlags(Event::Scheduled);
- if (head == event) {
+ if (next) {
+ // update the next bin pointer since it could be stale
+ next->nextBin = head->nextBin;
+
+ // pop the stack
+ head = next;
+ } else {
// this was the only element on the 'in bin' list, so get rid of
// the 'in bin' list and point to the next bin list
- head = event->nextBin;
- } else {
- // maintain head->nextInBin as the first element
- head->nextInBin = event->nextInBin;
+ head = head->nextBin;
}
// handle action
@@ -247,16 +236,16 @@ EventQueue::serialize(ostream &os)
int numEvents = 0;
Event *nextBin = head;
while (nextBin) {
- Event *nextInBin = nextBin->nextInBin;
+ Event *nextInBin = nextBin;
- do {
+ while (nextInBin) {
if (nextInBin->getFlags(Event::AutoSerialize)) {
eventPtrs.push_back(nextInBin);
paramOut(os, csprintf("event%d", numEvents++),
nextInBin->name());
}
nextInBin = nextInBin->nextInBin;
- } while (nextInBin != nextBin);
+ }
nextBin = nextBin->nextBin;
}
@@ -293,21 +282,16 @@ EventQueue::dump() const
cprintf("EventQueue Dump (cycle %d)\n", curTick);
cprintf("------------------------------------------------------------\n");
- m5::hash_map<long, bool> map;
-
if (empty())
cprintf("<No Events>\n");
else {
Event *nextBin = head;
while (nextBin) {
Event *nextInBin = nextBin;
- if (map[reinterpret_cast<long>(nextInBin)])
- break;
- map[reinterpret_cast<long>(nextInBin)] = true;
- do {
- nextInBin = nextInBin->nextInBin;
+ while (nextInBin) {
nextInBin->dump();
- } while (nextInBin != nextBin);
+ nextInBin = nextInBin->nextInBin;
+ }
nextBin = nextBin->nextBin;
}
@@ -326,8 +310,8 @@ EventQueue::debugVerify() const
Event *nextBin = head;
while (nextBin) {
- Event *nextInBin = nextBin->nextInBin;
- do {
+ Event *nextInBin = nextBin;
+ while (nextInBin) {
if (nextInBin->when() < time) {
cprintf("time goes backwards!");
nextInBin->dump();
@@ -350,7 +334,7 @@ EventQueue::debugVerify() const
priority = nextInBin->priority();
nextInBin = nextInBin->nextInBin;
- } while (nextInBin != nextBin);
+ }
nextBin = nextBin->nextBin;
}
diff --git a/src/sim/eventq.hh b/src/sim/eventq.hh
index 10c0048a8..bc9b2353f 100644
--- a/src/sim/eventq.hh
+++ b/src/sim/eventq.hh
@@ -77,8 +77,8 @@ class Event : public Serializable, public FastAlloc
// The event queue is now a linked list of linked lists. The
// 'nextBin' pointer is to find the bin, where a bin is defined as
// when+priority. All events in the same bin will be stored in a
- // second circularly linked list maintained by the 'nextInBin'
- // pointer. The list will be accessed in FIFO order. The end
+ // second linked list (a stack) maintained by the 'nextInBin'
+ // pointer. The list will be accessed in LIFO order. The end
// result is that the insert/removal in 'nextBin' is
// linear/constant, and the lookup/removal in 'nextInBin' is
// constant/constant. Hopefully this is a significant improvement
@@ -86,7 +86,7 @@ class Event : public Serializable, public FastAlloc
Event *nextBin;
Event *nextInBin;
- friend void insertBefore(Event *event, Event *curr);
+ friend Event *insertBefore(Event *event, Event *curr);
friend Event *removeItem(Event *event, Event *last);
/// queue to which this event belongs (though it may or may not be