/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

/*

 * Copyright (c) 2008 University of Washington

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License version 2 as

 * published by the Free Software Foundation;

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 */

#include "simulator.h"

#include "realtime-simulator-impl.h"

#include "wall-clock-synchronizer.h"

#include "scheduler.h"

#include "event-impl.h"

#include "synchronizer.h"

#include "ns3/ptr.h"

#include "ns3/pointer.h"

#include "ns3/assert.h"

#include "ns3/fatal-error.h"

#include "ns3/log.h"

#include "ns3/system-mutex.h"

#include "ns3/boolean.h"

#include "ns3/enum.h"

#include <math.h>

NS_LOG_COMPONENT_DEFINE ("RealtimeSimulatorImpl");

namespace ns3 {

NS_OBJECT_ENSURE_REGISTERED (RealtimeSimulatorImpl);

TypeId

RealtimeSimulatorImpl::GetTypeId (void)

{

  static TypeId tid = TypeId ("ns3::RealtimeSimulatorImpl")

    .SetParent<Object> ()

    .AddConstructor<RealtimeSimulatorImpl> ()

    .AddAttribute ("SynchronizationMode", 

                   "What to do if the simulation cannot keep up with real time.",

                   EnumValue (SYNC_BEST_EFFORT),

                   MakeEnumAccessor (&RealtimeSimulatorImpl::SetSynchronizationMode),

                   MakeEnumChecker (SYNC_BEST_EFFORT, "BestEffort",

                                    SYNC_HARD_LIMIT, "HardLimit"))

    .AddAttribute ("HardLimit", 

                   "Maximum acceptable real-time jitter (used in conjunction with SynchronizationMode=HardLimit)",

                   TimeValue (Seconds (0.1)),

                   MakeTimeAccessor (&RealtimeSimulatorImpl::m_hardLimit),

                   MakeTimeChecker ())

    ;

  return tid;

}

RealtimeSimulatorImpl::RealtimeSimulatorImpl ()

{

  NS_LOG_FUNCTION_NOARGS ();

  m_stop = false;

  m_running = false;

  // uids are allocated from 4.

  // uid 0 is "invalid" events

  // uid 1 is "now" events

  // uid 2 is "destroy" events

  m_uid = 4; 

  // before ::Run is entered, the m_currentUid will be zero

  m_currentUid = 0;

  m_currentTs = 0;

  m_unscheduledEvents = 0;

  // Be very careful not to do anything that would cause a change or assignment

  // of the underlying reference counts of m_synchronizer or you will be sorry.

  m_synchronizer = CreateObject<WallClockSynchronizer> ();

}

RealtimeSimulatorImpl::~RealtimeSimulatorImpl ()

{

  NS_LOG_FUNCTION_NOARGS ();

  while (m_events->IsEmpty () == false)

    {

      Scheduler::Event next = m_events->RemoveNext ();

      next.impl->Unref ();

    }

  m_events = 0;

  m_synchronizer = 0;

}

void

RealtimeSimulatorImpl::Destroy ()

{

  NS_LOG_FUNCTION_NOARGS ();

  //

  // This function is only called with the private version "disconnected" from

  // the main simulator functions.  We rely on the user not calling 

  // Simulator::Destroy while there is a chance that a worker thread could be

  // accessing the current instance of the private object.  In practice this

  // means shutting down the workers and doing a Join() before calling the

  // Simulator::Destroy().

  //

  while (m_destroyEvents.empty () == false) 

    {

      Ptr<EventImpl> ev = m_destroyEvents.front ().PeekEventImpl ();

      m_destroyEvents.pop_front ();

      NS_LOG_LOGIC ("handle destroy " << ev);

      if (ev->IsCancelled () == false)

        {

          ev->Invoke ();

        }

    }

}

void

RealtimeSimulatorImpl::SetScheduler (Ptr<Scheduler> scheduler)

{

  NS_LOG_FUNCTION_NOARGS ();

  { 

    CriticalSection cs (m_mutex);

    if (m_events != 0)

      {

        while (m_events->IsEmpty () == false)

          {

            Scheduler::Event next = m_events->RemoveNext ();

            scheduler->Insert (next);

          }

      }

    m_events = scheduler;

  }

}

Ptr<Scheduler>

RealtimeSimulatorImpl::GetScheduler (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_events;

}

void

RealtimeSimulatorImpl::ProcessOneEvent (void)

{

  NS_LOG_FUNCTION_NOARGS ();

  //

  // The idea here is to wait until the next event comes due.  In the case of

  // a realtime simulation, we want real time to be consumed between events.  

  // It is the realtime synchronizer that causes real time to be consumed by

  // doing some kind of a wait.

  //

  // We need to be able to have external events (such as a packet reception event)

  // cause us to re-evaluate our state.  The way this works is that the synchronizer

  // gets interrupted and returs.  So, there is a possibility that things may change

  // out from under us dynamically.  In this case, we need to re-evaluate how long to 

  // wait in a for-loop until we have waited sucessfully (until a timeout) for the 

  // event at the head of the event list.

  //

  // m_synchronizer->Synchronize will return true if the wait was completed without 

  // interruption, otherwise it will return false indicating that something has changed

  // out from under us.  If we sit in the for-loop trying to synchronize until 

  // Synchronize() returns true, we will have successfully synchronized the execution 

  // time of the next event with the wall clock time of the synchronizer.

  //

  for (;;) 

    {

      uint64_t tsDelay = 0;

      uint64_t tsNext = 0;

      //

      // It is important to understand that m_currentTs is interpreted only as the 

      // timestamp  of the last event we executed.  Current time can a bit of a 

      // slippery concept in realtime mode.  What we have here is a discrete event 

      // simulator, so the last event is, by defintion, executed entirely at a single

      //  discrete time.  This is the definition of m_currentTs.  It really has 

      // nothing to do with the current real time, except that we are trying to arrange

      // that at the instant of the beginning of event execution, the current real time

      // and m_currentTs coincide.

      //

      // We use tsNow as the indication of the current real time.

      //

      uint64_t tsNow;

      { 

        CriticalSection cs (m_mutex);

        //

        // Since we are in realtime mode, the time to delay has got to be the 

        // difference between the current realtime and the timestamp of the next 

        // event.  Since m_currentTs is actually the timestamp of the last event we 

        // executed, it's not particularly meaningful for us here since real time has

        // certainly elapsed since it was last updated.

        //

        // It is possible that the current realtime has drifted past the next event

        // time so we need to be careful about that and not delay in that case.

        //

        NS_ASSERT_MSG (m_synchronizer->Realtime (), 

          "RealtimeSimulatorImpl::ProcessOneEvent (): Synchronizer reports not Realtime ()");

        //

        // tsNow is set to the normalized current real time.  When the simulation was

        // started, the current real time was effectively set to zero; so tsNow is

        // the current "real" simulation time.

        //

        // tsNext is the simulation time of the next event we want to execute.

        //

        tsNow = m_synchronizer->GetCurrentRealtime ();

        tsNext = NextTs ();

        //

        // tsDelay is therefore the real time we need to delay in order to bring the

        // real time in sync with the simulation time.  If we wait for this amount of

        // real time, we will accomplish moving the simulation time at the same rate

        // as the real time.  This is typically called "pacing" the simulation time.

        //

        // We do have to be careful if we are falling behind.  If so, tsDelay must be

        // zero.  If we're late, don't dawdle.

        //

        if (tsNext <= tsNow)

          {

            tsDelay = 0;

          }

        else

          {

            tsDelay = tsNext - tsNow;

          }

        //

        // We've figured out how long we need to delay in order to pace the 

        // simulation time with the real time.  We're going to sleep, but need

        // to work with the synchronizer to make sure we're awakened if something 

        // external happens (like a packet is received).  This next line resets

        // the synchronizer so that any future event will cause it to interrupt.

        //

        m_synchronizer->SetCondition (false);

      }

      //

      // We have a time to delay.  This time may actually not be valid anymore

      // since we released the critical section immediately above, and a real-time

      // ScheduleReal or ScheduleRealNow may have snuck in, well, between the 

      // closing brace above and this comment so to speak.  If this is the case, 

      // that schedule operation will have done a synchronizer Signal() that 

      // will set the condition variable to true and cause the Synchronize call 

      // below to return immediately.

      //

      // It's easiest to understand if you just consider a short tsDelay that only

      // requires a SpinWait down in the synchronizer.  What will happen is that 

      // whan Synchronize calls SpinWait, SpinWait will look directly at its 

      // condition variable.  Note that we set this condition variable to false 

      // inside the critical section above. 

      //

      // SpinWait will go into a forever loop until either the time has expired or

      // until the condition variable becomes true.  A true condition indicates that

      // the wait should stop.  The condition is set to true by one of the Schedule

      // methods of the simulator; so if we are in a wait down in Synchronize, and

      // a Simulator::ScheduleReal is done, the wait down in Synchronize will exit and

      // Synchronize will return false.  This means we have not actually synchronized

      // to the event expiration time.  If no real-time schedule operation is done

      // while down in Synchronize, the wait will time out and Synchronize will return 

      // true.  This indicates that we have synchronized to the event time.

      //

      // So we need to stay in this for loop, looking for the next event timestamp and 

      // attempting to sleep until its due.  If we've slept until the timestamp is due, 

      // Synchronize returns true and we break out of the sync loop.  If an external

      // event happens that requires a re-schedule, Synchronize returns false and

      // we re-evaluate our timing by continuing in the loop.  

      //

      // It is expected that tsDelay become shorter as external events interrupt our

      // waits.

      //

      if (m_synchronizer->Synchronize (tsNow, tsDelay))

        {

          NS_LOG_LOGIC ("Interrupted ...");

          break;

        }

      //

      // If we get to this point, we have been interrupted during a wait by a real-time

      // schedule operation.  This means all bets are off regarding tsDelay and we need

      // to re-evaluate what it is we want to do.  We'll loop back around in the 

      // for-loop and start again from scratch.

      //

    }

  //

  // If we break out of the for-loop above, we have waited until the time specified

  // by the event that was at the head of the event list when we started the process.

  // Since there is a bunch of code that was executed outside a critical section (the

  // Synchronize call) we cannot be sure that the event at the head of the event list

  // is the one we think it is.  What we can be sure of is that it is time to execute

  // whatever event is at the head of this list if the list is in time order.

  //

  Scheduler::Event next;

  { 

    CriticalSection cs (m_mutex);

    // 

    // We do know we're waiting for an event, so there had better be an event on the 

    // event queue.  Let's pull it off.  When we release the critical section, the

    // event we're working on won't be on the list and so subsequent operations won't

    // mess with us.

    //

    NS_ASSERT_MSG (m_events->IsEmpty () == false, 

      "RealtimeSimulatorImpl::ProcessOneEvent(): event queue is empty");

    next = m_events->RemoveNext ();

    --m_unscheduledEvents;

    //

    // We cannot make any assumption that "next" is the same event we originally waited 

    // for.  We can only assume that only that it must be due and cannot cause time 

    // to move backward.

    //

    NS_ASSERT_MSG (next.key.m_ts >= m_currentTs,

                   "RealtimeSimulatorImpl::ProcessOneEvent(): "

                   "next.GetTs() earlier than m_currentTs (list order error)");

    NS_LOG_LOGIC ("handle " << next.key.m_ts);

    // 

    // Update the current simulation time to be the timestamp of the event we're 

    // executing.  From the rest of the simulation's point of view, simulation time

    // is frozen until the next event is executed.

    //

    m_currentTs = next.key.m_ts;

    m_currentUid = next.key.m_uid;

    // 

    // We're about to run the event and we've done our best to synchronize this

    // event execution time to real time.  Now, if we're in SYNC_HARD_LIMIT mode

    // we have to decide if we've done a good enough job and if we haven't, we've

    // been asked to commit ritual suicide.

    //

    // We check the simulation time against the current real time to make this

    // judgement.

    //

    if (m_synchronizationMode == SYNC_HARD_LIMIT)

      {

        uint64_t tsFinal = m_synchronizer->GetCurrentRealtime ();

        uint64_t tsJitter;

        if (tsFinal >= m_currentTs)

          {

            tsJitter = tsFinal - m_currentTs;

          }

        else

          {

            tsJitter = m_currentTs - tsFinal;

          }

        if (tsJitter > static_cast<uint64_t>(m_hardLimit.GetTimeStep ()))

          {

            NS_FATAL_ERROR ("RealtimeSimulatorImpl::ProcessOneEvent (): "

                            "Hard real-time limit exceeded (jitter = " << tsJitter << ")");

          }

      }

  }

  //

  // We have got the event we're about to execute completely disentangled from the 

  // event list so we can execute it outside a critical section without fear of someone

  // changing things out from under us.

  EventImpl *event = next.impl;

  m_synchronizer->EventStart ();

  event->Invoke ();

  m_synchronizer->EventEnd ();

  event->Unref ();

}

bool 

RealtimeSimulatorImpl::IsFinished (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  bool rc;

  {

    CriticalSection cs (m_mutex);

    rc = m_events->IsEmpty ();

  }

  return rc;

}

//

// Peeks into event list.  Should be called with critical section locked.

//

uint64_t

RealtimeSimulatorImpl::NextTs (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  NS_ASSERT_MSG (m_events->IsEmpty () == false, 

    "RealtimeSimulatorImpl::NextTs(): event queue is empty");

  Scheduler::Event ev = m_events->PeekNext ();

  return ev.key.m_ts;

}

//

// Calls NextTs().  Should be called with critical section locked.

//

Time

RealtimeSimulatorImpl::Next (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return TimeStep (NextTs ());

}

void

RealtimeSimulatorImpl::Run (void)

{

  NS_LOG_FUNCTION_NOARGS ();

  NS_ASSERT_MSG (m_running == false, 

                 "RealtimeSimulatorImpl::Run(): Simulator already running");

  m_running = true;

  m_synchronizer->SetOrigin (m_currentTs);

  for (;;) 

    {

      bool done = false;

      {

        CriticalSection cs (m_mutex);

        //

        // In all cases we stop when the event list is empty.  If you are doing a 

        // realtime simulation and you want it to extend out for some time, you must

        // call StopAt.  In the realtime case, this will stick a placeholder event out

        // at the end of time.

        //

        if (m_stop || m_events->IsEmpty ())

          {

            done = true;

          }

      }

      if (done)

        {

          break;

        }

      ProcessOneEvent ();

    }

  //

  // If the simulator stopped naturally by lack of events, make a

  // consistency test to check that we didn't lose any events along the way.

  //

  {

    CriticalSection cs (m_mutex);

    NS_ASSERT_MSG (m_events->IsEmpty () == false || m_unscheduledEvents == 0,

      "RealtimeSimulatorImpl::Run(): Empty queue and unprocessed events");

  }

  m_running = false;

}

bool

RealtimeSimulatorImpl::Running (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_running;

}

bool

RealtimeSimulatorImpl::Realtime (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_synchronizer->Realtime ();

}

//

// This will run the first event on the queue without considering any realtime

// synchronization.  It's mainly implemented to allow simulations requiring

// the multithreaded ScheduleRealtimeNow() functions the possibility of driving

// the simulation from their own event loop.

//

// It is expected that if there are any realtime requirements, the responsibility

// for synchronizing with real time in an external event loop will be picked up

// by that loop.  For example, they may call Simulator::Next() to find the 

// execution time of the next event and wait for that time somehow -- then call

// RunOneEvent to fire the event.

// 

void

RealtimeSimulatorImpl::RunOneEvent (void)

{

  NS_LOG_FUNCTION_NOARGS ();

  NS_ASSERT_MSG (m_running == false, 

                 "RealtimeSimulatorImpl::RunOneEvent(): An internal simulator event loop is running");

  EventImpl *event = 0;

  //

  // Run this in a critical section in case there's another thread around that

  // may be inserting things onto the event list.

  //

  {

    CriticalSection cs (m_mutex);

    Scheduler::Event next = m_events->RemoveNext ();

    NS_ASSERT (next.key.m_ts >= m_currentTs);