eventq.hh revision 8648
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 <iosfwd>
43#include <string>
44
45#include "base/fast_alloc.hh"
46#include "base/flags.hh"
47#include "base/misc.hh"
48#include "base/trace.hh"
49#include "base/types.hh"
50#include "debug/Event.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; // public readable flags
73    static const FlagsType PublicWrite   = 0x001d; // public writable flags
74    static const FlagsType Squashed      = 0x0001; // has been squashed
75    static const FlagsType Scheduled     = 0x0002; // has been scheduled
76    static const FlagsType AutoDelete    = 0x0004; // delete after dispatch
77    static const FlagsType AutoSerialize = 0x0008; // must be serialized
78    static const FlagsType IsExitEvent   = 0x0010; // special exit event
79    static const FlagsType IsMainQueue   = 0x0020; // on main event queue
80    static const FlagsType Initialized   = 0x7a40; // somewhat random bits
81    static const FlagsType InitMask      = 0xffc0; // mask for init bits
82
83    bool
84    initialized() const
85    {
86        return this && (flags & InitMask) == Initialized;
87    }
88
89  public:
90    typedef int8_t Priority;
91
92  private:
93    // The event queue is now a linked list of linked lists.  The
94    // 'nextBin' pointer is to find the bin, where a bin is defined as
95    // when+priority.  All events in the same bin will be stored in a
96    // second linked list (a stack) maintained by the 'nextInBin'
97    // pointer.  The list will be accessed in LIFO order.  The end
98    // result is that the insert/removal in 'nextBin' is
99    // linear/constant, and the lookup/removal in 'nextInBin' is
100    // constant/constant.  Hopefully this is a significant improvement
101    // over the current fully linear insertion.
102    Event *nextBin;
103    Event *nextInBin;
104
105    static Event *insertBefore(Event *event, Event *curr);
106    static Event *removeItem(Event *event, Event *last);
107
108    Tick _when;         //!< timestamp when event should be processed
109    Priority _priority; //!< event priority
110    Flags flags;
111
112#ifndef NDEBUG
113    /// Global counter to generate unique IDs for Event instances
114    static Counter instanceCounter;
115
116    /// This event's unique ID.  We can also use pointer values for
117    /// this but they're not consistent across runs making debugging
118    /// more difficult.  Thus we use a global counter value when
119    /// debugging.
120    Counter instance;
121
122    /// queue to which this event belongs (though it may or may not be
123    /// scheduled on this queue yet)
124    EventQueue *queue;
125#endif
126
127#ifdef EVENTQ_DEBUG
128    Tick whenCreated;   //!< time created
129    Tick whenScheduled; //!< time scheduled
130#endif
131
132    void
133    setWhen(Tick when, EventQueue *q)
134    {
135        _when = when;
136#ifndef NDEBUG
137        queue = q;
138#endif
139#ifdef EVENTQ_DEBUG
140        whenScheduled = curTick();
141#endif
142    }
143
144  protected:
145    /// Accessor for flags.
146    Flags
147    getFlags() const
148    {
149        return flags & PublicRead;
150    }
151
152    bool
153    isFlagSet(Flags _flags) const
154    {
155        assert(_flags.noneSet(~PublicRead));
156        return flags.isSet(_flags);
157    }
158
159    /// Accessor for flags.
160    void
161    setFlags(Flags _flags)
162    {
163        assert(_flags.noneSet(~PublicWrite));
164        flags.set(_flags);
165    }
166
167    void
168    clearFlags(Flags _flags)
169    {
170        assert(_flags.noneSet(~PublicWrite));
171        flags.clear(_flags);
172    }
173
174    void
175    clearFlags()
176    {
177        flags.clear(PublicWrite);
178    }
179
180    // This function isn't really useful if TRACING_ON is not defined
181    virtual void trace(const char *action);     //!< trace event activity
182
183  public:
184    /// Event priorities, to provide tie-breakers for events scheduled
185    /// at the same cycle.  Most events are scheduled at the default
186    /// priority; these values are used to control events that need to
187    /// be ordered within a cycle.
188
189    /// Minimum priority
190    static const Priority Minimum_Pri =          SCHAR_MIN;
191
192    /// If we enable tracing on a particular cycle, do that as the
193    /// very first thing so we don't miss any of the events on
194    /// that cycle (even if we enter the debugger).
195    static const Priority Trace_Enable_Pri =          -101;
196
197    /// Breakpoints should happen before anything else (except
198    /// enabling trace output), so we don't miss any action when
199    /// debugging.
200    static const Priority Debug_Break_Pri =           -100;
201
202    /// CPU switches schedule the new CPU's tick event for the
203    /// same cycle (after unscheduling the old CPU's tick event).
204    /// The switch needs to come before any tick events to make
205    /// sure we don't tick both CPUs in the same cycle.
206    static const Priority CPU_Switch_Pri =             -31;
207
208    /// For some reason "delayed" inter-cluster writebacks are
209    /// scheduled before regular writebacks (which have default
210    /// priority).  Steve?
211    static const Priority Delayed_Writeback_Pri =       -1;
212
213    /// Default is zero for historical reasons.
214    static const Priority Default_Pri =                  0;
215
216    /// Serailization needs to occur before tick events also, so
217    /// that a serialize/unserialize is identical to an on-line
218    /// CPU switch.
219    static const Priority Serialize_Pri =               32;
220
221    /// CPU ticks must come after other associated CPU events
222    /// (such as writebacks).
223    static const Priority CPU_Tick_Pri =                50;
224
225    /// Statistics events (dump, reset, etc.) come after
226    /// everything else, but before exit.
227    static const Priority Stat_Event_Pri =              90;
228
229    /// Progress events come at the end.
230    static const Priority Progress_Event_Pri =          95;
231
232    /// If we want to exit on this cycle, it's the very last thing
233    /// we do.
234    static const Priority Sim_Exit_Pri =               100;
235
236    /// Maximum priority
237    static const Priority Maximum_Pri =          SCHAR_MAX;
238
239    /*
240     * Event constructor
241     * @param queue that the event gets scheduled on
242     */
243    Event(Priority p = Default_Pri, Flags f = 0)
244        : nextBin(NULL), nextInBin(NULL), _priority(p),
245          flags(Initialized | f)
246    {
247        assert(f.noneSet(~PublicWrite));
248#ifndef NDEBUG
249        instance = ++instanceCounter;
250        queue = NULL;
251#endif
252#ifdef EVENTQ_DEBUG
253        whenCreated = curTick();
254        whenScheduled = 0;
255#endif
256    }
257
258    virtual ~Event();
259    virtual const std::string name() const;
260
261    /// Return a C string describing the event.  This string should
262    /// *not* be dynamically allocated; just a const char array
263    /// describing the event class.
264    virtual const char *description() const;
265
266    /// Dump the current event data
267    void dump() const;
268
269  public:
270    /*
271     * This member function is invoked when the event is processed
272     * (occurs).  There is no default implementation; each subclass
273     * must provide its own implementation.  The event is not
274     * automatically deleted after it is processed (to allow for
275     * statically allocated event objects).
276     *
277     * If the AutoDestroy flag is set, the object is deleted once it
278     * is processed.
279     */
280    virtual void process() = 0;
281
282    /// Determine if the current event is scheduled
283    bool scheduled() const { return flags.isSet(Scheduled); }
284
285    /// Squash the current event
286    void squash() { flags.set(Squashed); }
287
288    /// Check whether the event is squashed
289    bool squashed() const { return flags.isSet(Squashed); }
290
291    /// See if this is a SimExitEvent (without resorting to RTTI)
292    bool isExitEvent() const { return flags.isSet(IsExitEvent); }
293
294    /// Get the time that the event is scheduled
295    Tick when() const { return _when; }
296
297    /// Get the event priority
298    Priority priority() const { return _priority; }
299
300#ifndef SWIG
301    struct priority_compare
302        : public std::binary_function<Event *, Event *, bool>
303    {
304        bool
305        operator()(const Event *l, const Event *r) const
306        {
307            return l->when() >= r->when() || l->priority() >= r->priority();
308        }
309    };
310
311    virtual void serialize(std::ostream &os);
312    virtual void unserialize(Checkpoint *cp, const std::string &section);
313#endif
314};
315
316#ifndef SWIG
317inline bool
318operator<(const Event &l, const Event &r)
319{
320    return l.when() < r.when() ||
321        (l.when() == r.when() && l.priority() < r.priority());
322}
323
324inline bool
325operator>(const Event &l, const Event &r)
326{
327    return l.when() > r.when() ||
328        (l.when() == r.when() && l.priority() > r.priority());
329}
330
331inline bool
332operator<=(const Event &l, const Event &r)
333{
334    return l.when() < r.when() ||
335        (l.when() == r.when() && l.priority() <= r.priority());
336}
337inline bool
338operator>=(const Event &l, const Event &r)
339{
340    return l.when() > r.when() ||
341        (l.when() == r.when() && l.priority() >= r.priority());
342}
343
344inline bool
345operator==(const Event &l, const Event &r)
346{
347    return l.when() == r.when() && l.priority() == r.priority();
348}
349
350inline bool
351operator!=(const Event &l, const Event &r)
352{
353    return l.when() != r.when() || l.priority() != r.priority();
354}
355#endif
356
357/*
358 * Queue of events sorted in time order
359 */
360class EventQueue : public Serializable
361{
362  private:
363    std::string objName;
364    Event *head;
365
366    void insert(Event *event);
367    void remove(Event *event);
368
369    EventQueue(const EventQueue &);
370    const EventQueue &operator=(const EventQueue &);
371
372  public:
373    EventQueue(const std::string &n);
374
375    virtual const std::string name() const { return objName; }
376
377    // schedule the given event on this queue
378    void schedule(Event *event, Tick when);
379    void deschedule(Event *event);
380    void reschedule(Event *event, Tick when, bool always = false);
381
382    Tick nextTick() const { return head->when(); }
383    Event *serviceOne();
384
385    // process all events up to the given timestamp.  we inline a
386    // quick test to see if there are any events to process; if so,
387    // call the internal out-of-line version to process them all.
388    void
389    serviceEvents(Tick when)
390    {
391        while (!empty()) {
392            if (nextTick() > when)
393                break;
394
395            /**
396             * @todo this assert is a good bug catcher.  I need to
397             * make it true again.
398             */
399            //assert(head->when() >= when && "event scheduled in the past");
400            serviceOne();
401        }
402    }
403
404    // return true if no events are queued
405    bool empty() const { return head == NULL; }
406
407    void dump() const;
408
409    bool debugVerify() const;
410
411    /**
412     *  function for replacing the head of the event queue, so that a
413     *  different set of events can run without disturbing events that have
414     *  already been scheduled. Already scheduled events can be processed
415     *  by replacing the original head back.
416     *  USING THIS FUNCTION CAN BE DANGEROUS TO THE HEALTH OF THE SIMULATOR.
417     *  NOT RECOMMENDED FOR USE.
418     */
419    Event* replaceHead(Event* s);
420
421#ifndef SWIG
422    virtual void serialize(std::ostream &os);
423    virtual void unserialize(Checkpoint *cp, const std::string &section);
424#endif
425};
426
427#ifndef SWIG
428class EventManager
429{
430  protected:
431    /** A pointer to this object's event queue */
432    EventQueue *eventq;
433
434  public:
435    EventManager(EventManager &em) : eventq(em.queue()) {}
436    EventManager(EventManager *em) : eventq(em ? em->queue() : NULL) {}
437    EventManager(EventQueue *eq) : eventq(eq) {}
438
439    EventQueue *
440    queue() const
441    {
442        return eventq;
443    }
444
445    operator EventQueue *() const
446    {
447        return eventq;
448    }
449
450    void
451    schedule(Event &event, Tick when)
452    {
453        eventq->schedule(&event, when);
454    }
455
456    void
457    deschedule(Event &event)
458    {
459        eventq->deschedule(&event);
460    }
461
462    void
463    reschedule(Event &event, Tick when, bool always = false)
464    {
465        eventq->reschedule(&event, when, always);
466    }
467
468    void
469    schedule(Event *event, Tick when)
470    {
471        eventq->schedule(event, when);
472    }
473
474    void
475    deschedule(Event *event)
476    {
477        eventq->deschedule(event);
478    }
479
480    void
481    reschedule(Event *event, Tick when, bool always = false)
482    {
483        eventq->reschedule(event, when, always);
484    }
485};
486
487inline void
488EventQueue::schedule(Event *event, Tick when)
489{
490    // Typecasting Tick->Utick here since gcc
491    // complains about signed overflow
492    assert((UTick)when >= (UTick)curTick());
493    assert(!event->scheduled());
494    assert(event->initialized());
495
496    event->setWhen(when, this);
497    insert(event);
498    event->flags.set(Event::Scheduled);
499    if (this == &mainEventQueue)
500        event->flags.set(Event::IsMainQueue);
501    else
502        event->flags.clear(Event::IsMainQueue);
503
504    if (DTRACE(Event))
505        event->trace("scheduled");
506}
507
508inline void
509EventQueue::deschedule(Event *event)
510{
511    assert(event->scheduled());
512    assert(event->initialized());
513
514    remove(event);
515
516    event->flags.clear(Event::Squashed);
517    event->flags.clear(Event::Scheduled);
518
519    if (event->flags.isSet(Event::AutoDelete))
520        delete event;
521
522    if (DTRACE(Event))
523        event->trace("descheduled");
524}
525
526inline void
527EventQueue::reschedule(Event *event, Tick when, bool always)
528{
529    // Typecasting Tick->Utick here since gcc
530    // complains about signed overflow
531    assert((UTick)when >= (UTick)curTick());
532    assert(always || event->scheduled());
533    assert(event->initialized());
534
535    if (event->scheduled())
536        remove(event);
537
538    event->setWhen(when, this);
539    insert(event);
540    event->flags.clear(Event::Squashed);
541    event->flags.set(Event::Scheduled);
542    if (this == &mainEventQueue)
543        event->flags.set(Event::IsMainQueue);
544    else
545        event->flags.clear(Event::IsMainQueue);
546
547    if (DTRACE(Event))
548        event->trace("rescheduled");
549}
550
551template <class T, void (T::* F)()>
552void
553DelayFunction(EventQueue *eventq, Tick when, T *object)
554{
555    class DelayEvent : public Event
556    {
557      private:
558        T *object;
559
560      public:
561        DelayEvent(T *o)
562            : Event(Default_Pri, AutoDelete), object(o)
563        { }
564        void process() { (object->*F)(); }
565        const char *description() const { return "delay"; }
566    };
567
568    eventq->schedule(new DelayEvent(object), when);
569}
570
571template <class T, void (T::* F)()>
572class EventWrapper : public Event
573{
574  private:
575    T *object;
576
577  public:
578    EventWrapper(T *obj, bool del = false, Priority p = Default_Pri)
579        : Event(p), object(obj)
580    {
581        if (del)
582            setFlags(AutoDelete);
583    }
584
585    EventWrapper(T &obj, bool del = false, Priority p = Default_Pri)
586        : Event(p), object(&obj)
587    {
588        if (del)
589            setFlags(AutoDelete);
590    }
591
592    void process() { (object->*F)(); }
593
594    const std::string
595    name() const
596    {
597        return object->name() + ".wrapped_event";
598    }
599
600    const char *description() const { return "EventWrapped"; }
601};
602#endif
603
604#endif // __SIM_EVENTQ_HH__
605