eventq.hh revision 9554:406fbcf60223
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/flags.hh"
46#include "base/misc.hh"
47#include "base/types.hh"
48#include "debug/Event.hh"
49#include "sim/serialize.hh"
50
51class EventQueue;       // forward declaration
52
53extern EventQueue mainEventQueue;
54
55/*
56 * An item on an event queue.  The action caused by a given
57 * event is specified by deriving a subclass and overriding the
58 * process() member function.
59 *
60 * Caution, the order of members is chosen to maximize data packing.
61 */
62class Event : public Serializable
63{
64    friend class EventQueue;
65
66  protected:
67    typedef unsigned short FlagsType;
68    typedef ::Flags<FlagsType> Flags;
69
70    static const FlagsType PublicRead    = 0x003f; // public readable flags
71    static const FlagsType PublicWrite   = 0x001d; // public writable flags
72    static const FlagsType Squashed      = 0x0001; // has been squashed
73    static const FlagsType Scheduled     = 0x0002; // has been scheduled
74    static const FlagsType AutoDelete    = 0x0004; // delete after dispatch
75    static const FlagsType AutoSerialize = 0x0008; // must be serialized
76    static const FlagsType IsExitEvent   = 0x0010; // special exit event
77    static const FlagsType IsMainQueue   = 0x0020; // on main event queue
78    static const FlagsType Initialized   = 0x7a40; // somewhat random bits
79    static const FlagsType InitMask      = 0xffc0; // mask for init bits
80
81    bool
82    initialized() const
83    {
84        return this && (flags & InitMask) == Initialized;
85    }
86
87  public:
88    typedef int8_t Priority;
89
90  private:
91    // The event queue is now a linked list of linked lists.  The
92    // 'nextBin' pointer is to find the bin, where a bin is defined as
93    // when+priority.  All events in the same bin will be stored in a
94    // second linked list (a stack) maintained by the 'nextInBin'
95    // pointer.  The list will be accessed in LIFO order.  The end
96    // result is that the insert/removal in 'nextBin' is
97    // linear/constant, and the lookup/removal in 'nextInBin' is
98    // constant/constant.  Hopefully this is a significant improvement
99    // over the current fully linear insertion.
100    Event *nextBin;
101    Event *nextInBin;
102
103    static Event *insertBefore(Event *event, Event *curr);
104    static Event *removeItem(Event *event, Event *last);
105
106    Tick _when;         //!< timestamp when event should be processed
107    Priority _priority; //!< event priority
108    Flags flags;
109
110#ifndef NDEBUG
111    /// Global counter to generate unique IDs for Event instances
112    static Counter instanceCounter;
113
114    /// This event's unique ID.  We can also use pointer values for
115    /// this but they're not consistent across runs making debugging
116    /// more difficult.  Thus we use a global counter value when
117    /// debugging.
118    Counter instance;
119
120    /// queue to which this event belongs (though it may or may not be
121    /// scheduled on this queue yet)
122    EventQueue *queue;
123#endif
124
125#ifdef EVENTQ_DEBUG
126    Tick whenCreated;   //!< time created
127    Tick whenScheduled; //!< time scheduled
128#endif
129
130    void
131    setWhen(Tick when, EventQueue *q)
132    {
133        _when = when;
134#ifndef NDEBUG
135        queue = q;
136#endif
137#ifdef EVENTQ_DEBUG
138        whenScheduled = curTick();
139#endif
140    }
141
142  protected:
143    /// Accessor for flags.
144    Flags
145    getFlags() const
146    {
147        return flags & PublicRead;
148    }
149
150    bool
151    isFlagSet(Flags _flags) const
152    {
153        assert(_flags.noneSet(~PublicRead));
154        return flags.isSet(_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
187    /// Minimum priority
188    static const Priority Minimum_Pri =          SCHAR_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    static const Priority 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    static const Priority 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    static const Priority 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    static const Priority Delayed_Writeback_Pri =       -1;
210
211    /// Default is zero for historical reasons.
212    static const Priority 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    static const Priority Serialize_Pri =               32;
218
219    /// CPU ticks must come after other associated CPU events
220    /// (such as writebacks).
221    static const Priority CPU_Tick_Pri =                50;
222
223    /// Statistics events (dump, reset, etc.) come after
224    /// everything else, but before exit.
225    static const Priority Stat_Event_Pri =              90;
226
227    /// Progress events come at the end.
228    static const Priority Progress_Event_Pri =          95;
229
230    /// If we want to exit on this cycle, it's the very last thing
231    /// we do.
232    static const Priority Sim_Exit_Pri =               100;
233
234    /// Maximum priority
235    static const Priority Maximum_Pri =          SCHAR_MAX;
236
237    /*
238     * Event constructor
239     * @param queue that the event gets scheduled on
240     */
241    Event(Priority p = Default_Pri, Flags f = 0)
242        : nextBin(NULL), nextInBin(NULL), _priority(p),
243          flags(Initialized | f)
244    {
245        assert(f.noneSet(~PublicWrite));
246#ifndef NDEBUG
247        instance = ++instanceCounter;
248        queue = NULL;
249#endif
250#ifdef EVENTQ_DEBUG
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    Priority priority() const { return _priority; }
297
298#ifndef SWIG
299    virtual void serialize(std::ostream &os);
300    virtual void unserialize(Checkpoint *cp, const std::string &section);
301#endif
302};
303
304#ifndef SWIG
305inline bool
306operator<(const Event &l, const Event &r)
307{
308    return l.when() < r.when() ||
309        (l.when() == r.when() && l.priority() < r.priority());
310}
311
312inline bool
313operator>(const Event &l, const Event &r)
314{
315    return l.when() > r.when() ||
316        (l.when() == r.when() && l.priority() > r.priority());
317}
318
319inline bool
320operator<=(const Event &l, const Event &r)
321{
322    return l.when() < r.when() ||
323        (l.when() == r.when() && l.priority() <= r.priority());
324}
325inline bool
326operator>=(const Event &l, const Event &r)
327{
328    return l.when() > r.when() ||
329        (l.when() == r.when() && l.priority() >= r.priority());
330}
331
332inline bool
333operator==(const Event &l, const Event &r)
334{
335    return l.when() == r.when() && l.priority() == r.priority();
336}
337
338inline bool
339operator!=(const Event &l, const Event &r)
340{
341    return l.when() != r.when() || l.priority() != r.priority();
342}
343#endif
344
345/*
346 * Queue of events sorted in time order
347 */
348class EventQueue : public Serializable
349{
350  private:
351    std::string objName;
352    Event *head;
353    Tick _curTick;
354
355    void insert(Event *event);
356    void remove(Event *event);
357
358    EventQueue(const EventQueue &);
359    const EventQueue &operator=(const EventQueue &);
360
361  public:
362    EventQueue(const std::string &n);
363
364    virtual const std::string name() const { return objName; }
365
366    // schedule the given event on this queue
367    void schedule(Event *event, Tick when);
368    void deschedule(Event *event);
369    void reschedule(Event *event, Tick when, bool always = false);
370
371    Tick nextTick() const { return head->when(); }
372    void setCurTick(Tick newVal) { _curTick = newVal; }
373    Tick getCurTick() { return _curTick; }
374
375    Event *serviceOne();
376
377    // process all events up to the given timestamp.  we inline a
378    // quick test to see if there are any events to process; if so,
379    // call the internal out-of-line version to process them all.
380    void
381    serviceEvents(Tick when)
382    {
383        while (!empty()) {
384            if (nextTick() > when)
385                break;
386
387            /**
388             * @todo this assert is a good bug catcher.  I need to
389             * make it true again.
390             */
391            //assert(head->when() >= when && "event scheduled in the past");
392            serviceOne();
393        }
394
395        setCurTick(when);
396    }
397
398    // return true if no events are queued
399    bool empty() const { return head == NULL; }
400
401    void dump() const;
402
403    bool debugVerify() const;
404
405    /**
406     *  function for replacing the head of the event queue, so that a
407     *  different set of events can run without disturbing events that have
408     *  already been scheduled. Already scheduled events can be processed
409     *  by replacing the original head back.
410     *  USING THIS FUNCTION CAN BE DANGEROUS TO THE HEALTH OF THE SIMULATOR.
411     *  NOT RECOMMENDED FOR USE.
412     */
413    Event* replaceHead(Event* s);
414
415#ifndef SWIG
416    virtual void serialize(std::ostream &os);
417    virtual void unserialize(Checkpoint *cp, const std::string &section);
418#endif
419};
420
421void dumpMainQueue();
422
423#ifndef SWIG
424class EventManager
425{
426  protected:
427    /** A pointer to this object's event queue */
428    EventQueue *eventq;
429
430  public:
431    EventManager(EventManager &em) : eventq(em.eventq) {}
432    EventManager(EventManager *em) : eventq(em->eventq) {}
433    EventManager(EventQueue *eq) : eventq(eq) {}
434
435    EventQueue *
436    eventQueue() const
437    {
438        return eventq;
439    }
440
441    void
442    schedule(Event &event, Tick when)
443    {
444        eventq->schedule(&event, when);
445    }
446
447    void
448    deschedule(Event &event)
449    {
450        eventq->deschedule(&event);
451    }
452
453    void
454    reschedule(Event &event, Tick when, bool always = false)
455    {
456        eventq->reschedule(&event, when, always);
457    }
458
459    void
460    schedule(Event *event, Tick when)
461    {
462        eventq->schedule(event, when);
463    }
464
465    void
466    deschedule(Event *event)
467    {
468        eventq->deschedule(event);
469    }
470
471    void
472    reschedule(Event *event, Tick when, bool always = false)
473    {
474        eventq->reschedule(event, when, always);
475    }
476
477    void setCurTick(Tick newVal) { eventq->setCurTick(newVal); }
478};
479
480template <class T, void (T::* F)()>
481void
482DelayFunction(EventQueue *eventq, Tick when, T *object)
483{
484    class DelayEvent : public Event
485    {
486      private:
487        T *object;
488
489      public:
490        DelayEvent(T *o)
491            : Event(Default_Pri, AutoDelete), object(o)
492        { }
493        void process() { (object->*F)(); }
494        const char *description() const { return "delay"; }
495    };
496
497    eventq->schedule(new DelayEvent(object), when);
498}
499
500template <class T, void (T::* F)()>
501class EventWrapper : public Event
502{
503  private:
504    T *object;
505
506  public:
507    EventWrapper(T *obj, bool del = false, Priority p = Default_Pri)
508        : Event(p), object(obj)
509    {
510        if (del)
511            setFlags(AutoDelete);
512    }
513
514    EventWrapper(T &obj, bool del = false, Priority p = Default_Pri)
515        : Event(p), object(&obj)
516    {
517        if (del)
518            setFlags(AutoDelete);
519    }
520
521    void process() { (object->*F)(); }
522
523    const std::string
524    name() const
525    {
526        return object->name() + ".wrapped_event";
527    }
528
529    const char *description() const { return "EventWrapped"; }
530};
531#endif
532
533#endif // __SIM_EVENTQ_HH__
534