summaryrefslogtreecommitdiff
path: root/src/sim/eventq.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/sim/eventq.cc')
-rw-r--r--src/sim/eventq.cc222
1 files changed, 180 insertions, 42 deletions
diff --git a/src/sim/eventq.cc b/src/sim/eventq.cc
index ab0ba9385..2b61df26e 100644
--- a/src/sim/eventq.cc
+++ b/src/sim/eventq.cc
@@ -1,5 +1,6 @@
/*
* Copyright (c) 2000-2005 The Regents of The University of Michigan
+ * Copyright (c) 2008 The Hewlett-Packard Development Company
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -35,6 +36,7 @@
#include <string>
#include <vector>
+#include "base/hashmap.hh"
#include "base/misc.hh"
#include "base/trace.hh"
#include "cpu/smt.hh"
@@ -55,61 +57,140 @@ EventQueue mainEventQueue("MainEventQueue");
Counter Event::instanceCounter = 0;
#endif
+inline void
+insertBefore(Event *event, Event *curr)
+{
+ // Either way, event will be the last 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;
+ } 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
+ }
+}
+
void
EventQueue::insert(Event *event)
{
- if (head == NULL || event->when() < head->when() ||
- (event->when() == head->when() &&
- event->priority() <= head->priority())) {
- event->next = head;
+ // Deal with the head case
+ if (!head || *event <= *head) {
+ insertBefore(event, head);
head = event;
- } else {
- Event *prev = head;
- Event *curr = head->next;
+ return;
+ }
- while (curr) {
- if (event->when() <= curr->when() &&
- (event->when() < curr->when() ||
- event->priority() <= curr->priority()))
- break;
+ // 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;
+ }
- prev = curr;
- curr = curr->next;
- }
+ insertBefore(event, next);
+ curr->nextBin = event; // all nextBin pointers on the curr
+ // 'in bin' list are now stale
+}
+
+inline Event *
+removeItem(Event *event, Event *last)
+{
+ Event *prev = last;
+ Event *curr = last->nextInBin;
+
+ while (event != curr) {
+ if (curr == last)
+ panic("event not found!");
- event->next = curr;
- prev->next = event;
+ prev = curr;
+ curr = curr->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;
}
void
EventQueue::remove(Event *event)
{
if (head == NULL)
- return;
-
- if (head == event){
- head = event->next;
+ panic("event not found!");
+
+ // deal with an event on the head's 'in bin' list (event has the same
+ // time as the head)
+ if (*head == *event) {
+ head = removeItem(event, head);
+ if (!head)
+ head = event->nextBin;
return;
}
+ // Find the 'in bin' list that this event belongs on
Event *prev = head;
- Event *curr = head->next;
- while (curr && curr != event) {
+ Event *curr = head->nextBin;
+ while (curr && *curr < *event) {
prev = curr;
- curr = curr->next;
+ curr = curr->nextBin;
}
- if (curr == event)
- prev->next = curr->next;
+ 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
+ // 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;
+ }
}
Event *
EventQueue::serviceOne()
{
- Event *event = head;
+ // grab the first element
+ Event *event = head->nextInBin;
event->clearFlags(Event::Scheduled);
- head = event->next;
+
+ if (head == event) {
+ // 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;
+ }
// handle action
if (!event->squashed()) {
@@ -128,7 +209,6 @@ EventQueue::serviceOne()
return NULL;
}
-
void
Event::serialize(std::ostream &os)
{
@@ -137,7 +217,6 @@ Event::serialize(std::ostream &os)
SERIALIZE_ENUM(_flags);
}
-
void
Event::unserialize(Checkpoint *cp, const string &section)
{
@@ -166,18 +245,25 @@ EventQueue::serialize(ostream &os)
std::list<Event *> eventPtrs;
int numEvents = 0;
- Event *event = head;
- while (event) {
- if (event->getFlags(Event::AutoSerialize)) {
- eventPtrs.push_back(event);
- paramOut(os, csprintf("event%d", numEvents++), event->name());
- }
- event = event->next;
+ Event *nextBin = head;
+ while (nextBin) {
+ Event *nextInBin = nextBin->nextInBin;
+
+ do {
+ 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;
}
SERIALIZE_SCALAR(numEvents);
- for (std::list<Event *>::iterator it=eventPtrs.begin();
+ for (std::list<Event *>::iterator it = eventPtrs.begin();
it != eventPtrs.end(); ++it) {
(*it)->nameOut(os);
(*it)->serialize(os);
@@ -207,19 +293,71 @@ 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 *event = head;
- while (event) {
- event->dump();
- event = event->next;
+ 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;
+ nextInBin->dump();
+ } while (nextInBin != nextBin);
+
+ nextBin = nextBin->nextBin;
}
}
cprintf("============================================================\n");
}
+bool
+EventQueue::debugVerify() const
+{
+ m5::hash_map<long, bool> map;
+
+ Tick time = 0;
+ short priority = 0;
+
+ Event *nextBin = head;
+ while (nextBin) {
+ Event *nextInBin = nextBin->nextInBin;
+ do {
+ if (nextInBin->when() < time) {
+ cprintf("time goes backwards!");
+ nextInBin->dump();
+ return false;
+ } else if (nextInBin->when() == time &&
+ nextInBin->priority() < priority) {
+ cprintf("priority inverted!");
+ nextInBin->dump();
+ return false;
+ }
+
+ if (map[reinterpret_cast<long>(nextInBin)]) {
+ cprintf("Node already seen");
+ nextInBin->dump();
+ return false;
+ }
+ map[reinterpret_cast<long>(nextInBin)] = true;
+
+ time = nextInBin->when();
+ priority = nextInBin->priority();
+
+ nextInBin = nextInBin->nextInBin;
+ } while (nextInBin != nextBin);
+
+ nextBin = nextBin->nextBin;
+ }
+
+ return true;
+}
+
void
dumpMainQueue()
{
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-31 18:42:37 +0000