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