eventq.hh

Go to the documentation of this file.

/*
 * Copyright (c) 2000-2005 The Regents of The University of Michigan
 * Copyright (c) 2013 Advanced Micro Devices, Inc.
 * Copyright (c) 2013 Mark D. Hill and David A. Wood
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/* @file
 * EventQueue interfaces
 */

#ifndef __SIM_EVENTQ_HH__
#define __SIM_EVENTQ_HH__

#include <algorithm>
#include <cassert>
#include <climits>
#include <functional>
#include <iosfwd>
#include <memory>
#include <mutex>
#include <string>

#include "base/debug.hh"
#include "base/flags.hh"
#include "base/types.hh"
#include "debug/Event.hh"
#include "sim/serialize.hh"

class EventQueue;       // forward declaration
class BaseGlobalEvent;

extern Tick simQuantum;

extern uint32_t numMainEventQueues;

extern std::vector<EventQueue *> mainEventQueue;


extern __thread EventQueue *_curEventQueue;

extern bool inParallelMode;

EventQueue *getEventQueue(uint32_t index);

inline EventQueue *curEventQueue() { return _curEventQueue; }
inline void curEventQueue(EventQueue *q) { _curEventQueue = q; }

class EventBase
{
  protected:
    typedef unsigned short FlagsType;
    typedef ::Flags<FlagsType> Flags;

    static const FlagsType PublicRead    = 0x003f; // public readable flags
    static const FlagsType PublicWrite   = 0x001d; // public writable flags
    static const FlagsType Squashed      = 0x0001; // has been squashed
    static const FlagsType Scheduled     = 0x0002; // has been scheduled
    static const FlagsType Managed       = 0x0004; // Use life cycle manager
    static const FlagsType AutoDelete    = Managed; // delete after dispatch
    static const FlagsType Reserved0     = 0x0008;
    static const FlagsType IsExitEvent   = 0x0010; // special exit event
    static const FlagsType IsMainQueue   = 0x0020; // on main event queue
    static const FlagsType Initialized   = 0x7a40; // somewhat random bits
    static const FlagsType InitMask      = 0xffc0; // mask for init bits

  public:
    typedef int8_t Priority;


    static const Priority Minimum_Pri =          SCHAR_MIN;

    static const Priority Debug_Enable_Pri =          -101;

    static const Priority Debug_Break_Pri =           -100;

    static const Priority CPU_Switch_Pri =             -31;

    static const Priority Delayed_Writeback_Pri =       -1;

    static const Priority Default_Pri =                  0;

    static const Priority DVFS_Update_Pri =             31;

    static const Priority Serialize_Pri =               32;

    static const Priority CPU_Tick_Pri =                50;

    static const Priority CPU_Exit_Pri =                64;

    static const Priority Stat_Event_Pri =              90;

    static const Priority Progress_Event_Pri =          95;

    static const Priority Sim_Exit_Pri =               100;

    static const Priority Maximum_Pri =          SCHAR_MAX;
};

/*
 * An item on an event queue.  The action caused by a given
 * event is specified by deriving a subclass and overriding the
 * process() member function.
 *
 * Caution, the order of members is chosen to maximize data packing.
 */
class Event : public EventBase, public Serializable
{
    friend class EventQueue;

  private:
    // 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 linked list (a stack) maintained by the 'nextInBin'
    // pointer.  The list will be accessed in LIFO 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;

    static Event *insertBefore(Event *event, Event *curr);
    static Event *removeItem(Event *event, Event *last);

    Tick _when;         
    Priority _priority; 
    Flags flags;

#ifndef NDEBUG
    static Counter instanceCounter;

    Counter instance;

    EventQueue *queue;
#endif

#ifdef EVENTQ_DEBUG
    Tick whenCreated;   
    Tick whenScheduled; 
#endif

    void
    setWhen(Tick when, EventQueue *q)
    {
        _when = when;
#ifndef NDEBUG
        queue = q;
#endif
#ifdef EVENTQ_DEBUG
        whenScheduled = curTick();
#endif
    }

    bool
    initialized() const
    {
        return (flags & InitMask) == Initialized;
    }

  protected:
    Flags
    getFlags() const
    {
        return flags & PublicRead;
    }

    bool
    isFlagSet(Flags _flags) const
    {
        assert(_flags.noneSet(~PublicRead));
        return flags.isSet(_flags);
    }

    void
    setFlags(Flags _flags)
    {
        assert(_flags.noneSet(~PublicWrite));
        flags.set(_flags);
    }

    void
    clearFlags(Flags _flags)
    {
        assert(_flags.noneSet(~PublicWrite));
        flags.clear(_flags);
    }

    void
    clearFlags()
    {
        flags.clear(PublicWrite);
    }

    virtual void trace(const char *action);     

    const std::string instanceString() const;

  protected: /* Memory management */
    void acquire()
    {
        if (flags.isSet(Event::Managed))
            acquireImpl();
    }

    void release() {
        if (flags.isSet(Event::Managed))
            releaseImpl();
    }

    virtual void acquireImpl() {}

    virtual void releaseImpl() {
        if (!scheduled())
            delete this;
    }

  public:

    /*
     * Event constructor
     * @param queue that the event gets scheduled on
     *
     * @ingroup api_eventq
     */
    Event(Priority p = Default_Pri, Flags f = 0)
        : nextBin(nullptr), nextInBin(nullptr), _when(0), _priority(p),
          flags(Initialized | f)
    {
        assert(f.noneSet(~PublicWrite));
#ifndef NDEBUG
        instance = ++instanceCounter;
        queue = NULL;
#endif
#ifdef EVENTQ_DEBUG
        whenCreated = curTick();
        whenScheduled = 0;
#endif
    }

    virtual ~Event();
    virtual const std::string name() const;

    virtual const char *description() const;

    void dump() const; //end of api group

  public:
    /*
     * This member function is invoked when the event is processed
     * (occurs).  There is no default implementation; each subclass
     * must provide its own implementation.  The event is not
     * automatically deleted after it is processed (to allow for
     * statically allocated event objects).
     *
     * If the AutoDestroy flag is set, the object is deleted once it
     * is processed.
     *
     * @ingroup api_eventq
     */
    virtual void process() = 0;

    bool scheduled() const { return flags.isSet(Scheduled); }

    void squash() { flags.set(Squashed); }

    bool squashed() const { return flags.isSet(Squashed); }

    bool isExitEvent() const { return flags.isSet(IsExitEvent); }

    bool isManaged() const { return flags.isSet(Managed); }

    bool isAutoDelete() const { return isManaged(); }

    Tick when() const { return _when; }

    Priority priority() const { return _priority; }

    virtual BaseGlobalEvent *globalEvent() { return NULL; }

    void serialize(CheckpointOut &cp) const override;
    void unserialize(CheckpointIn &cp) override;
};

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();
}

class EventQueue
{
  private:
    std::string objName;
    Event *head;
    Tick _curTick;

    std::mutex async_queue_mutex;

    std::list<Event*> async_queue;

    std::mutex service_mutex;

    void insert(Event *event);
    void remove(Event *event);

    void asyncInsert(Event *event);

    EventQueue(const EventQueue &);

  public:
    class ScopedMigration
    {
      public:
        ScopedMigration(EventQueue *_new_eq, bool _doMigrate = true)
            :new_eq(*_new_eq), old_eq(*curEventQueue()),
             doMigrate((&new_eq != &old_eq)&&_doMigrate)
        {
            if (doMigrate){
                old_eq.unlock();
                new_eq.lock();
                curEventQueue(&new_eq);
            }
        }

        ~ScopedMigration()
        {
            if (doMigrate){
                new_eq.unlock();
                old_eq.lock();
                curEventQueue(&old_eq);
            }
        }

      private:
        EventQueue &new_eq;
        EventQueue &old_eq;
        bool doMigrate;
    };

    class ScopedRelease
    {
      public:
        ScopedRelease(EventQueue *_eq)
            :  eq(*_eq)
        {
            eq.unlock();
        }

        ~ScopedRelease()
        {
            eq.lock();
        }

      private:
        EventQueue &eq;
    };

    EventQueue(const std::string &n);

    virtual const std::string name() const { return objName; }
    void name(const std::string &st) { objName = st; } //end of api_eventq group

    void
    schedule(Event *event, Tick when, bool global=false)
    {
        assert(when >= getCurTick());
        assert(!event->scheduled());
        assert(event->initialized());

        event->setWhen(when, this);

        // The check below is to make sure of two things
        // a. A thread schedules local events on other queues through the
        //    asyncq.
        // b. A thread schedules global events on the asyncq, whether or not
        //    this event belongs to this eventq. This is required to maintain
        //    a total order amongst the global events. See global_event.{cc,hh}
        //    for more explanation.
        if (inParallelMode && (this != curEventQueue() || global)) {
            asyncInsert(event);
        } else {
            insert(event);
        }
        event->flags.set(Event::Scheduled);
        event->acquire();

        if (DTRACE(Event))
            event->trace("scheduled");
    }

    void
    deschedule(Event *event)
    {
        assert(event->scheduled());
        assert(event->initialized());
        assert(!inParallelMode || this == curEventQueue());

        remove(event);

        event->flags.clear(Event::Squashed);
        event->flags.clear(Event::Scheduled);

        if (DTRACE(Event))
            event->trace("descheduled");

        event->release();
    }

    void
    reschedule(Event *event, Tick when, bool always=false)
    {
        assert(when >= getCurTick());
        assert(always || event->scheduled());
        assert(event->initialized());
        assert(!inParallelMode || this == curEventQueue());

        if (event->scheduled()) {
            remove(event);
        } else {
            event->acquire();
        }

        event->setWhen(when, this);
        insert(event);
        event->flags.clear(Event::Squashed);
        event->flags.set(Event::Scheduled);

        if (DTRACE(Event))
            event->trace("rescheduled");
    }

    Tick nextTick() const { return head->when(); }
    void setCurTick(Tick newVal) { _curTick = newVal; }

    Tick getCurTick() const { return _curTick; }
    Event *getHead() const { return head; }

    Event *serviceOne();

    void
    serviceEvents(Tick when)
    {
        while (!empty()) {
            if (nextTick() > when)
                break;

            //assert(head->when() >= when && "event scheduled in the past");
            serviceOne();
        }

        setCurTick(when);
    }

    bool empty() const { return head == NULL; }

    void dump() const;

    bool debugVerify() const;

    void handleAsyncInsertions();

    virtual void wakeup(Tick when = (Tick)-1) { }

    Event* replaceHead(Event* s);

    void lock() { service_mutex.lock(); }
    void unlock() { service_mutex.unlock(); }
    void checkpointReschedule(Event *event);

    virtual ~EventQueue()
    {
        while (!empty())
            deschedule(getHead());
    }
};

void dumpMainQueue();

class EventManager
{
  protected:
    EventQueue *eventq;

  public:
    EventManager(EventManager &em) : eventq(em.eventq) {}
    EventManager(EventManager *em) : eventq(em->eventq) {}
    EventManager(EventQueue *eq) : eventq(eq) {} //end of api_eventq group

    EventQueue *
    eventQueue() const
    {
        return eventq;
    }

    void
    schedule(Event &event, Tick when)
    {
        eventq->schedule(&event, when);
    }

    void
    deschedule(Event &event)
    {
        eventq->deschedule(&event);
    }

    void
    reschedule(Event &event, Tick when, bool always = false)
    {
        eventq->reschedule(&event, when, always);
    }

    void
    schedule(Event *event, Tick when)
    {
        eventq->schedule(event, when);
    }

    void
    deschedule(Event *event)
    {
        eventq->deschedule(event);
    }

    void
    reschedule(Event *event, Tick when, bool always = false)
    {
        eventq->reschedule(event, when, always);
    }

    void wakeupEventQueue(Tick when = (Tick)-1)
    {
        eventq->wakeup(when);
    }

    void setCurTick(Tick newVal) { eventq->setCurTick(newVal); }
};

template <class T, void (T::* F)()>
class EventWrapper : public Event
{
  private:
    T *object;

  public:
    EventWrapper(T *obj, bool del = false, Priority p = Default_Pri)
        : Event(p), object(obj)
    {
        if (del)
            setFlags(AutoDelete);
    }

    EventWrapper(T &obj, bool del = false, Priority p = Default_Pri)
        : Event(p), object(&obj)
    {
        if (del)
            setFlags(AutoDelete);
    }

    void process() { (object->*F)(); }

    const std::string
    name() const
    {
        return object->name() + ".wrapped_event";
    }

    const char *description() const { return "EventWrapped"; }
};

class EventFunctionWrapper : public Event
{
  private:
      std::function<void(void)> callback;
      std::string _name;

  public:
    EventFunctionWrapper(const std::function<void(void)> &callback,
                         const std::string &name,
                         bool del = false,
                         Priority p = Default_Pri)
        : Event(p), callback(callback), _name(name)
    {
        if (del)
            setFlags(AutoDelete);
    }

    void process() { callback(); }

    const std::string
    name() const
    {
        return _name + ".wrapped_function_event";
    }

    const char *description() const { return "EventFunctionWrapped"; }
};

#endif // __SIM_EVENTQ_HH__