diff options
Diffstat (limited to 'src/sim')
| -rw-r--r-- | src/sim/eventq.cc | 222 | ||||
| -rw-r--r-- | src/sim/eventq.hh | 132 |
2 files changed, 277 insertions, 77 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 §ion) { @@ -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() { diff --git a/src/sim/eventq.hh b/src/sim/eventq.hh index ea950e625..10c0048a8 100644 --- a/src/sim/eventq.hh +++ b/src/sim/eventq.hh @@ -74,7 +74,20 @@ class Event : public Serializable, public FastAlloc friend class EventQueue; private: - Event *next; + // 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 + // 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 + // over the current fully linear insertion. + Event *nextBin; + Event *nextInBin; + + friend void 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 /// scheduled on this queue yet) @@ -99,6 +112,17 @@ class Event : public Serializable, public FastAlloc Tick whenCreated; //!< time created Tick whenScheduled; //!< time scheduled #endif + + protected: + void + setWhen(Tick when) + { + _when = when; +#ifdef DEBUG_EVENTQ + whenScheduled = curTick; +#endif + } + protected: enum Flags { None = 0x0, @@ -181,7 +205,7 @@ class Event : public Serializable, public FastAlloc * @param queue that the event gets scheduled on */ Event(EventQueue *q, Priority p = Default_Pri) - : next(NULL), _queue(q), _priority(p), _flags(None) + : nextBin(NULL), nextInBin(NULL), _queue(q), _priority(p), _flags(None) { #ifndef NDEBUG instance = ++instanceCounter; @@ -343,9 +367,9 @@ class EventQueue : public Serializable virtual const std::string name() const { return objName; } // schedule the given event on this queue - void schedule(Event *ev); + void schedule(Event *ev, Tick when); void deschedule(Event *ev); - void reschedule(Event *ev); + void reschedule(Event *ev, Tick when); Tick nextTick() const { return head->when(); } Event *serviceOne(); @@ -379,6 +403,8 @@ class EventQueue : public Serializable Tick nextEventTime() { return empty() ? curTick : head->when(); } + bool debugVerify() const; + virtual void serialize(std::ostream &os); virtual void unserialize(Checkpoint *cp, const std::string §ion); }; @@ -396,53 +422,77 @@ class EventQueue : public Serializable // schedule at specified time (place on event queue specified via // constructor) inline void -Event::schedule(Tick t) +Event::schedule(Tick when) { - assert(!scheduled()); - assert(t >= curTick); - - setFlags(Scheduled); -#ifdef DEBUG_EVENTQ - whenScheduled = curTick; -#endif - _when = t; - _queue->schedule(this); + _queue->schedule(this, when); } inline void Event::deschedule() { - assert(scheduled()); - - clearFlags(Squashed); - clearFlags(Scheduled); _queue->deschedule(this); } inline void -Event::reschedule(Tick t, bool always) +Event::reschedule(Tick when, bool always) { - assert(scheduled() || always); - assert(t >= curTick); - -#ifdef DEBUG_EVENTQ - whenScheduled = curTick; -#endif - _when = t; - if (scheduled()) { - clearFlags(Squashed); - _queue->reschedule(this); + _queue->reschedule(this, when); } else { - setFlags(Scheduled); - _queue->schedule(this); + assert(always); + _queue->schedule(this, when); } } +inline bool +operator<(const Event &l, const Event &r) +{ + return l.when() < r.when() || + (l.when() == r.when() && l.priority() < r.priority()); +} + +inline bool +operator>(const Event &l, const Event &r) +{ + return l.when() > r.when() || + (l.when() == r.when() && l.priority() > r.priority()); +} + +inline bool +operator<=(const Event &l, const Event &r) +{ + return l.when() < r.when() || + (l.when() == r.when() && l.priority() <= r.priority()); +} +inline bool +operator>=(const Event &l, const Event &r) +{ + return l.when() > r.when() || + (l.when() == r.when() && l.priority() >= r.priority()); +} + +inline bool +operator==(const Event &l, const Event &r) +{ + return l.when() == r.when() && l.priority() == r.priority(); +} + +inline bool +operator!=(const Event &l, const Event &r) +{ + return l.when() != r.when() || l.priority() != r.priority(); +} + inline void -EventQueue::schedule(Event *event) +EventQueue::schedule(Event *event, Tick when) { + assert(when >= curTick); + assert(!event->scheduled()); + + event->setWhen(when); insert(event); + event->setFlags(Event::Scheduled); + if (DTRACE(Event)) event->trace("scheduled"); } @@ -450,19 +500,31 @@ EventQueue::schedule(Event *event) inline void EventQueue::deschedule(Event *event) { + assert(event->scheduled()); + remove(event); - if (DTRACE(Event)) - event->trace("descheduled"); + + event->clearFlags(Event::Squashed); + event->clearFlags(Event::Scheduled); if (event->getFlags(Event::AutoDelete)) delete event; + + if (DTRACE(Event)) + event->trace("descheduled"); } inline void -EventQueue::reschedule(Event *event) +EventQueue::reschedule(Event *event, Tick when) { + assert(when >= curTick); + assert(event->scheduled()); + remove(event); + event->setWhen(when); insert(event); + event->clearFlags(Event::Squashed); + if (DTRACE(Event)) event->trace("rescheduled"); } |