eventq.hh revision 6982
1/*
2 * Copyright (c) 2000-2005 The Regents of The University of Michigan
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
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Steve Reinhardt
29 *          Nathan Binkert
30 */
31
32/* @file
33 * EventQueue interfaces
34 */
35
36#ifndef __SIM_EVENTQ_HH__
37#define __SIM_EVENTQ_HH__
38
39#include <algorithm>
40#include <cassert>
41#include <climits>
42#include <map>
43#include <string>
44#include <vector>
45
46#include "base/fast_alloc.hh"
47#include "base/flags.hh"
48#include "base/misc.hh"
49#include "base/trace.hh"
50#include "base/types.hh"
51#include "sim/serialize.hh"
52
53class EventQueue;       // forward declaration
54
55extern EventQueue mainEventQueue;
56
57/*
58 * An item on an event queue.  The action caused by a given
59 * event is specified by deriving a subclass and overriding the
60 * process() member function.
61 *
62 * Caution, the order of members is chosen to maximize data packing.
63 */
64class Event : public Serializable, public FastAlloc
65{
66    friend class EventQueue;
67
68  protected:
69    typedef short FlagsType;
70    typedef ::Flags<FlagsType> Flags;
71
72    static const FlagsType PublicRead    = 0x003f;
73    static const FlagsType PublicWrite   = 0x001d;
74    static const FlagsType Squashed      = 0x0001;
75    static const FlagsType Scheduled     = 0x0002;
76    static const FlagsType AutoDelete    = 0x0004;
77    static const FlagsType AutoSerialize = 0x0008;
78    static const FlagsType IsExitEvent   = 0x0010;
79    static const FlagsType IsMainQueue   = 0x0020;
80#ifdef EVENTQ_DEBUG
81    static const FlagsType Initialized   = 0xf000;
82#endif
83
84  private:
85    // The event queue is now a linked list of linked lists.  The
86    // 'nextBin' pointer is to find the bin, where a bin is defined as
87    // when+priority.  All events in the same bin will be stored in a
88    // second linked list (a stack) maintained by the 'nextInBin'
89    // pointer.  The list will be accessed in LIFO order.  The end
90    // result is that the insert/removal in 'nextBin' is
91    // linear/constant, and the lookup/removal in 'nextInBin' is
92    // constant/constant.  Hopefully this is a significant improvement
93    // over the current fully linear insertion.
94    Event *nextBin;
95    Event *nextInBin;
96
97    static Event *insertBefore(Event *event, Event *curr);
98    static Event *removeItem(Event *event, Event *last);
99
100    Tick _when;         //!< timestamp when event should be processed
101    short _priority;    //!< event priority
102    Flags flags;
103
104#ifndef NDEBUG
105    /// Global counter to generate unique IDs for Event instances
106    static Counter instanceCounter;
107
108    /// This event's unique ID.  We can also use pointer values for
109    /// this but they're not consistent across runs making debugging
110    /// more difficult.  Thus we use a global counter value when
111    /// debugging.
112    Counter instance;
113
114    /// queue to which this event belongs (though it may or may not be
115    /// scheduled on this queue yet)
116    EventQueue *queue;
117#endif
118
119#ifdef EVENTQ_DEBUG
120    Tick whenCreated;   //!< time created
121    Tick whenScheduled; //!< time scheduled
122#endif
123
124    void
125    setWhen(Tick when, EventQueue *q)
126    {
127        _when = when;
128#ifndef NDEBUG
129        queue = q;
130#endif
131#ifdef EVENTQ_DEBUG
132        whenScheduled = curTick;
133#endif
134    }
135
136  protected:
137    /// Accessor for flags.
138    Flags
139    getFlags() const
140    {
141        return flags & PublicRead;
142    }
143
144    Flags
145    getFlags(Flags _flags) const
146    {
147        assert(flags.noneSet(~PublicRead));
148        return flags.isSet(_flags);
149    }
150
151    Flags
152    allFlags(Flags _flags) const
153    {
154        assert(_flags.noneSet(~PublicRead));
155        return flags.allSet(_flags);
156    }
157
158    /// Accessor for flags.
159    void
160    setFlags(Flags _flags)
161    {
162        assert(_flags.noneSet(~PublicWrite));
163        flags.set(_flags);
164    }
165
166    void
167    clearFlags(Flags _flags)
168    {
169        assert(_flags.noneSet(~PublicWrite));
170        flags.clear(_flags);
171    }
172
173    void
174    clearFlags()
175    {
176        flags.clear(PublicWrite);
177    }
178
179    // This function isn't really useful if TRACING_ON is not defined
180    virtual void trace(const char *action);     //!< trace event activity
181
182  public:
183    /// Event priorities, to provide tie-breakers for events scheduled
184    /// at the same cycle.  Most events are scheduled at the default
185    /// priority; these values are used to control events that need to
186    /// be ordered within a cycle.
187    enum Priority {
188        /// Minimum priority
189        Minimum_Pri             = SHRT_MIN,
190
191        /// If we enable tracing on a particular cycle, do that as the
192        /// very first thing so we don't miss any of the events on
193        /// that cycle (even if we enter the debugger).
194        Trace_Enable_Pri        = -101,
195
196        /// Breakpoints should happen before anything else (except
197        /// enabling trace output), so we don't miss any action when
198        /// debugging.
199        Debug_Break_Pri         = -100,
200
201        /// CPU switches schedule the new CPU's tick event for the
202        /// same cycle (after unscheduling the old CPU's tick event).
203        /// The switch needs to come before any tick events to make
204        /// sure we don't tick both CPUs in the same cycle.
205        CPU_Switch_Pri          =   -31,
206
207        /// For some reason "delayed" inter-cluster writebacks are
208        /// scheduled before regular writebacks (which have default
209        /// priority).  Steve?
210        Delayed_Writeback_Pri   =   -1,
211
212        /// Default is zero for historical reasons.
213        Default_Pri             =    0,
214
215        /// Serailization needs to occur before tick events also, so
216        /// that a serialize/unserialize is identical to an on-line
217        /// CPU switch.
218        Serialize_Pri           =   32,
219
220        /// CPU ticks must come after other associated CPU events
221        /// (such as writebacks).
222        CPU_Tick_Pri            =   50,
223
224        /// Statistics events (dump, reset, etc.) come after
225        /// everything else, but before exit.
226        Stat_Event_Pri          =   90,
227
228        /// Progress events come at the end.
229        Progress_Event_Pri      =   95,
230
231        /// If we want to exit on this cycle, it's the very last thing
232        /// we do.
233        Sim_Exit_Pri            =  100,
234
235        /// Maximum priority
236        Maximum_Pri             = SHRT_MAX
237    };
238
239    /*
240     * Event constructor
241     * @param queue that the event gets scheduled on
242     */
243    Event(Priority p = Default_Pri)
244        : nextBin(NULL), nextInBin(NULL), _priority(p)
245    {
246#ifndef NDEBUG
247        instance = ++instanceCounter;
248        queue = NULL;
249#endif
250#ifdef EVENTQ_DEBUG
251        flags.set(Initialized);
252        whenCreated = curTick;
253        whenScheduled = 0;
254#endif
255    }
256
257    virtual ~Event();
258    virtual const std::string name() const;
259
260    /// Return a C string describing the event.  This string should
261    /// *not* be dynamically allocated; just a const char array
262    /// describing the event class.
263    virtual const char *description() const;
264
265    /// Dump the current event data
266    void dump() const;
267
268  public:
269    /*
270     * This member function is invoked when the event is processed
271     * (occurs).  There is no default implementation; each subclass
272     * must provide its own implementation.  The event is not
273     * automatically deleted after it is processed (to allow for
274     * statically allocated event objects).
275     *
276     * If the AutoDestroy flag is set, the object is deleted once it
277     * is processed.
278     */
279    virtual void process() = 0;
280
281    /// Determine if the current event is scheduled
282    bool scheduled() const { return flags.isSet(Scheduled); }
283
284    /// Squash the current event
285    void squash() { flags.set(Squashed); }
286
287    /// Check whether the event is squashed
288    bool squashed() const { return flags.isSet(Squashed); }
289
290    /// See if this is a SimExitEvent (without resorting to RTTI)
291    bool isExitEvent() const { return flags.isSet(IsExitEvent); }
292
293    /// Get the time that the event is scheduled
294    Tick when() const { return _when; }
295
296    /// Get the event priority
297    int priority() const { return _priority; }
298
299#ifndef SWIG
300    struct priority_compare
301        : public std::binary_function<Event *, Event *, bool>
302    {
303        bool
304        operator()(const Event *l, const Event *r) const
305        {
306            return l->when() >= r->when() || l->priority() >= r->priority();
307        }
308    };
309
310    virtual void serialize(std::ostream &os);
311    virtual void unserialize(Checkpoint *cp, const std::string &section);
312#endif
313};
314
315/*
316 * Queue of events sorted in time order
317 */
318class EventQueue : public Serializable
319{
320  private:
321    std::string objName;
322    Event *head;
323
324    void insert(Event *event);
325    void remove(Event *event);
326
327  public:
328    EventQueue(const std::string &n)
329        : objName(n), head(NULL)
330    {}
331
332    virtual const std::string name() const { return objName; }
333
334    // schedule the given event on this queue
335    void schedule(Event *event, Tick when);
336    void deschedule(Event *event);
337    void reschedule(Event *event, Tick when, bool always = false);
338
339    Tick nextTick() const { return head->when(); }
340    Event *serviceOne();
341
342    // process all events up to the given timestamp.  we inline a
343    // quick test to see if there are any events to process; if so,
344    // call the internal out-of-line version to process them all.
345    void
346    serviceEvents(Tick when)
347    {
348        while (!empty()) {
349            if (nextTick() > when)
350                break;
351
352            /**
353             * @todo this assert is a good bug catcher.  I need to
354             * make it true again.
355             */
356            //assert(head->when() >= when && "event scheduled in the past");
357            serviceOne();
358        }
359    }
360
361    // default: process all events up to 'now' (curTick)
362    void serviceEvents() { serviceEvents(curTick); }
363
364    // return true if no events are queued
365    bool empty() const { return head == NULL; }
366
367    void dump() const;
368
369    Tick nextEventTime() { return empty() ? curTick : head->when(); }
370
371    bool debugVerify() const;
372
373#ifndef SWIG
374    virtual void serialize(std::ostream &os);
375    virtual void unserialize(Checkpoint *cp, const std::string &section);
376#endif
377};
378
379#ifndef SWIG
380class EventManager
381{
382  protected:
383    /** A pointer to this object's event queue */
384    EventQueue *eventq;
385
386  public:
387    EventManager(EventManager &em) : eventq(em.queue()) {}
388    EventManager(EventManager *em) : eventq(em ? em->queue() : NULL) {}
389    EventManager(EventQueue *eq) : eventq(eq) {}
390
391    EventQueue *
392    queue() const
393    {
394        return eventq;
395    }
396
397    void
398    schedule(Event &event, Tick when)
399    {
400        eventq->schedule(&event, when);
401    }
402
403    void
404    deschedule(Event &event)
405    {
406        eventq->deschedule(&event);
407    }
408
409    void
410    reschedule(Event &event, Tick when, bool always = false)
411    {
412        eventq->reschedule(&event, when, always);
413    }
414
415    void
416    schedule(Event *event, Tick when)
417    {
418        eventq->schedule(event, when);
419    }
420
421    void
422    deschedule(Event *event)
423    {
424        eventq->deschedule(event);
425    }
426
427    void
428    reschedule(Event *event, Tick when, bool always = false)
429    {
430        eventq->reschedule(event, when, always);
431    }
432};
433
434template <class T, void (T::* F)()>
435void
436DelayFunction(EventQueue *eventq, Tick when, T *object)
437{
438    class DelayEvent : public Event
439    {
440      private:
441        T *object;
442
443      public:
444        DelayEvent(T *o)
445            : object(o)
446        { this->setFlags(AutoDelete); }
447        void process() { (object->*F)(); }
448        const char *description() const { return "delay"; }
449    };
450
451    eventq->schedule(new DelayEvent(object), when);
452}
453
454template <class T, void (T::* F)()>
455class EventWrapper : public Event
456{
457  private:
458    T *object;
459
460  public:
461    EventWrapper(T *obj, bool del = false, Priority p = Default_Pri)
462        : Event(p), object(obj)
463    {
464        if (del)
465            setFlags(AutoDelete);
466    }
467
468    void process() { (object->*F)(); }
469
470    const std::string
471    name() const
472    {
473        return object->name() + ".wrapped_event";
474    }
475
476    const char *description() const { return "EventWrapped"; }
477};
478
479inline void
480EventQueue::schedule(Event *event, Tick when)
481{
482    assert((UTick)when >= (UTick)curTick);
483    assert(!event->scheduled());
484#ifdef EVENTQ_DEBUG
485    assert((event->flags & Event::Initialized) == Event::Initialized);
486#endif
487
488    event->setWhen(when, this);
489    insert(event);
490    event->flags.set(Event::Scheduled);
491    if (this == &mainEventQueue)
492        event->flags.set(Event::IsMainQueue);
493    else
494        event->flags.clear(Event::IsMainQueue);
495
496    if (DTRACE(Event))
497        event->trace("scheduled");
498}
499
500inline void
501EventQueue::deschedule(Event *event)
502{
503    assert(event->scheduled());
504#ifdef EVENTQ_DEBUG
505    assert((event->flags & Event::Initialized) == Event::Initialized);
506#endif
507
508    remove(event);
509
510    event->flags.clear(Event::Squashed);
511    event->flags.clear(Event::Scheduled);
512
513    if (event->flags.isSet(Event::AutoDelete))
514        delete event;
515
516    if (DTRACE(Event))
517        event->trace("descheduled");
518}
519
520inline void
521EventQueue::reschedule(Event *event, Tick when, bool always)
522{
523    assert(when >= curTick);
524    assert(always || event->scheduled());
525#ifdef EVENTQ_DEBUG
526    assert((event->flags & Event::Initialized) == Event::Initialized);
527#endif
528
529    if (event->scheduled())
530        remove(event);
531
532    event->setWhen(when, this);
533    insert(event);
534    event->flags.clear(Event::Squashed);
535    event->flags.set(Event::Scheduled);
536    if (this == &mainEventQueue)
537        event->flags.set(Event::IsMainQueue);
538    else
539        event->flags.clear(Event::IsMainQueue);
540
541    if (DTRACE(Event))
542        event->trace("rescheduled");
543}
544
545inline bool
546operator<(const Event &l, const Event &r)
547{
548    return l.when() < r.when() ||
549        (l.when() == r.when() && l.priority() < r.priority());
550}
551
552inline bool
553operator>(const Event &l, const Event &r)
554{
555    return l.when() > r.when() ||
556        (l.when() == r.when() && l.priority() > r.priority());
557}
558
559inline bool
560operator<=(const Event &l, const Event &r)
561{
562    return l.when() < r.when() ||
563        (l.when() == r.when() && l.priority() <= r.priority());
564}
565inline bool
566operator>=(const Event &l, const Event &r)
567{
568    return l.when() > r.when() ||
569        (l.when() == r.when() && l.priority() >= r.priority());
570}
571
572inline bool
573operator==(const Event &l, const Event &r)
574{
575    return l.when() == r.when() && l.priority() == r.priority();
576}
577
578inline bool
579operator!=(const Event &l, const Event &r)
580{
581    return l.when() != r.when() || l.priority() != r.priority();
582}
583#endif
584
585#endif // __SIM_EVENTQ_HH__
586