1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
3 * Copyright (c) 2008 University of Washington
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 #include "simulator.h"
20 #include "realtime-simulator-impl.h"
21 #include "wall-clock-synchronizer.h"
22 #include "scheduler.h"
23 #include "event-impl.h"
24 #include "synchronizer.h"
27 #include "ns3/pointer.h"
28 #include "ns3/assert.h"
29 #include "ns3/fatal-error.h"
31 #include "ns3/system-mutex.h"
32 #include "ns3/boolean.h"
38 NS_LOG_COMPONENT_DEFINE ("RealtimeSimulatorImpl");
42 NS_OBJECT_ENSURE_REGISTERED (RealtimeSimulatorImpl);
45 RealtimeSimulatorImpl::GetTypeId (void)
47 static TypeId tid = TypeId ("ns3::RealtimeSimulatorImpl")
49 .AddConstructor<RealtimeSimulatorImpl> ()
50 .AddAttribute ("SynchronizationMode",
51 "What to do if the simulation cannot keep up with real time.",
52 EnumValue (SYNC_BEST_EFFORT),
53 MakeEnumAccessor (&RealtimeSimulatorImpl::SetSynchronizationMode),
54 MakeEnumChecker (SYNC_BEST_EFFORT, "BestEffort",
55 SYNC_HARD_LIMIT, "HardLimit"))
56 .AddAttribute ("HardLimit",
57 "Maximum acceptable real-time jitter (used in conjunction with SynchronizationMode=HardLimit)",
58 TimeValue (Seconds (0.1)),
59 MakeTimeAccessor (&RealtimeSimulatorImpl::m_hardLimit),
66 RealtimeSimulatorImpl::RealtimeSimulatorImpl ()
68 NS_LOG_FUNCTION_NOARGS ();
72 // uids are allocated from 4.
73 // uid 0 is "invalid" events
74 // uid 1 is "now" events
75 // uid 2 is "destroy" events
77 // before ::Run is entered, the m_currentUid will be zero
80 m_unscheduledEvents = 0;
82 // Be very careful not to do anything that would cause a change or assignment
83 // of the underlying reference counts of m_synchronizer or you will be sorry.
84 m_synchronizer = CreateObject<WallClockSynchronizer> ();
87 RealtimeSimulatorImpl::~RealtimeSimulatorImpl ()
89 NS_LOG_FUNCTION_NOARGS ();
90 while (m_events->IsEmpty () == false)
92 Scheduler::Event next = m_events->RemoveNext ();
100 RealtimeSimulatorImpl::Destroy ()
102 NS_LOG_FUNCTION_NOARGS ();
105 // This function is only called with the private version "disconnected" from
106 // the main simulator functions. We rely on the user not calling
107 // Simulator::Destroy while there is a chance that a worker thread could be
108 // accessing the current instance of the private object. In practice this
109 // means shutting down the workers and doing a Join() before calling the
110 // Simulator::Destroy().
112 while (m_destroyEvents.empty () == false)
114 Ptr<EventImpl> ev = m_destroyEvents.front ().PeekEventImpl ();
115 m_destroyEvents.pop_front ();
116 NS_LOG_LOGIC ("handle destroy " << ev);
117 if (ev->IsCancelled () == false)
125 RealtimeSimulatorImpl::SetScheduler (ObjectFactory schedulerFactory)
127 NS_LOG_FUNCTION_NOARGS ();
129 Ptr<Scheduler> scheduler = schedulerFactory.Create<Scheduler> ();
132 CriticalSection cs (m_mutex);
136 while (m_events->IsEmpty () == false)
138 Scheduler::Event next = m_events->RemoveNext ();
139 scheduler->Insert (next);
142 m_events = scheduler;
147 RealtimeSimulatorImpl::ProcessOneEvent (void)
149 NS_LOG_FUNCTION_NOARGS ();
151 // The idea here is to wait until the next event comes due. In the case of
152 // a realtime simulation, we want real time to be consumed between events.
153 // It is the realtime synchronizer that causes real time to be consumed by
154 // doing some kind of a wait.
156 // We need to be able to have external events (such as a packet reception event)
157 // cause us to re-evaluate our state. The way this works is that the synchronizer
158 // gets interrupted and returs. So, there is a possibility that things may change
159 // out from under us dynamically. In this case, we need to re-evaluate how long to
160 // wait in a for-loop until we have waited sucessfully (until a timeout) for the
161 // event at the head of the event list.
163 // m_synchronizer->Synchronize will return true if the wait was completed without
164 // interruption, otherwise it will return false indicating that something has changed
165 // out from under us. If we sit in the for-loop trying to synchronize until
166 // Synchronize() returns true, we will have successfully synchronized the execution
167 // time of the next event with the wall clock time of the synchronizer.
172 uint64_t tsDelay = 0;
176 // It is important to understand that m_currentTs is interpreted only as the
177 // timestamp of the last event we executed. Current time can a bit of a
178 // slippery concept in realtime mode. What we have here is a discrete event
179 // simulator, so the last event is, by defintion, executed entirely at a single
180 // discrete time. This is the definition of m_currentTs. It really has
181 // nothing to do with the current real time, except that we are trying to arrange
182 // that at the instant of the beginning of event execution, the current real time
183 // and m_currentTs coincide.
185 // We use tsNow as the indication of the current real time.
190 CriticalSection cs (m_mutex);
192 // Since we are in realtime mode, the time to delay has got to be the
193 // difference between the current realtime and the timestamp of the next
194 // event. Since m_currentTs is actually the timestamp of the last event we
195 // executed, it's not particularly meaningful for us here since real time has
196 // certainly elapsed since it was last updated.
198 // It is possible that the current realtime has drifted past the next event
199 // time so we need to be careful about that and not delay in that case.
201 NS_ASSERT_MSG (m_synchronizer->Realtime (),
202 "RealtimeSimulatorImpl::ProcessOneEvent (): Synchronizer reports not Realtime ()");
205 // tsNow is set to the normalized current real time. When the simulation was
206 // started, the current real time was effectively set to zero; so tsNow is
207 // the current "real" simulation time.
209 // tsNext is the simulation time of the next event we want to execute.
211 tsNow = m_synchronizer->GetCurrentRealtime ();
215 // tsDelay is therefore the real time we need to delay in order to bring the
216 // real time in sync with the simulation time. If we wait for this amount of
217 // real time, we will accomplish moving the simulation time at the same rate
218 // as the real time. This is typically called "pacing" the simulation time.
220 // We do have to be careful if we are falling behind. If so, tsDelay must be
221 // zero. If we're late, don't dawdle.
229 tsDelay = tsNext - tsNow;
233 // We've figured out how long we need to delay in order to pace the
234 // simulation time with the real time. We're going to sleep, but need
235 // to work with the synchronizer to make sure we're awakened if something
236 // external happens (like a packet is received). This next line resets
237 // the synchronizer so that any future event will cause it to interrupt.
239 m_synchronizer->SetCondition (false);
243 // We have a time to delay. This time may actually not be valid anymore
244 // since we released the critical section immediately above, and a real-time
245 // ScheduleReal or ScheduleRealNow may have snuck in, well, between the
246 // closing brace above and this comment so to speak. If this is the case,
247 // that schedule operation will have done a synchronizer Signal() that
248 // will set the condition variable to true and cause the Synchronize call
249 // below to return immediately.
251 // It's easiest to understand if you just consider a short tsDelay that only
252 // requires a SpinWait down in the synchronizer. What will happen is that
253 // whan Synchronize calls SpinWait, SpinWait will look directly at its
254 // condition variable. Note that we set this condition variable to false
255 // inside the critical section above.
257 // SpinWait will go into a forever loop until either the time has expired or
258 // until the condition variable becomes true. A true condition indicates that
259 // the wait should stop. The condition is set to true by one of the Schedule
260 // methods of the simulator; so if we are in a wait down in Synchronize, and
261 // a Simulator::ScheduleReal is done, the wait down in Synchronize will exit and
262 // Synchronize will return false. This means we have not actually synchronized
263 // to the event expiration time. If no real-time schedule operation is done
264 // while down in Synchronize, the wait will time out and Synchronize will return
265 // true. This indicates that we have synchronized to the event time.
267 // So we need to stay in this for loop, looking for the next event timestamp and
268 // attempting to sleep until its due. If we've slept until the timestamp is due,
269 // Synchronize returns true and we break out of the sync loop. If an external
270 // event happens that requires a re-schedule, Synchronize returns false and
271 // we re-evaluate our timing by continuing in the loop.
273 // It is expected that tsDelay become shorter as external events interrupt our
276 if (m_synchronizer->Synchronize (tsNow, tsDelay))
278 NS_LOG_LOGIC ("Interrupted ...");
283 // If we get to this point, we have been interrupted during a wait by a real-time
284 // schedule operation. This means all bets are off regarding tsDelay and we need
285 // to re-evaluate what it is we want to do. We'll loop back around in the
286 // for-loop and start again from scratch.
291 // If we break out of the for-loop above, we have waited until the time specified
292 // by the event that was at the head of the event list when we started the process.
293 // Since there is a bunch of code that was executed outside a critical section (the
294 // Synchronize call) we cannot be sure that the event at the head of the event list
295 // is the one we think it is. What we can be sure of is that it is time to execute
296 // whatever event is at the head of this list if the list is in time order.
298 Scheduler::Event next;
301 CriticalSection cs (m_mutex);
304 // We do know we're waiting for an event, so there had better be an event on the
305 // event queue. Let's pull it off. When we release the critical section, the
306 // event we're working on won't be on the list and so subsequent operations won't
309 NS_ASSERT_MSG (m_events->IsEmpty () == false,
310 "RealtimeSimulatorImpl::ProcessOneEvent(): event queue is empty");
311 next = m_events->RemoveNext ();
312 --m_unscheduledEvents;
315 // We cannot make any assumption that "next" is the same event we originally waited
316 // for. We can only assume that only that it must be due and cannot cause time
319 NS_ASSERT_MSG (next.key.m_ts >= m_currentTs,
320 "RealtimeSimulatorImpl::ProcessOneEvent(): "
321 "next.GetTs() earlier than m_currentTs (list order error)");
322 NS_LOG_LOGIC ("handle " << next.key.m_ts);
325 // Update the current simulation time to be the timestamp of the event we're
326 // executing. From the rest of the simulation's point of view, simulation time
327 // is frozen until the next event is executed.
329 m_currentTs = next.key.m_ts;
330 m_currentUid = next.key.m_uid;
333 // We're about to run the event and we've done our best to synchronize this
334 // event execution time to real time. Now, if we're in SYNC_HARD_LIMIT mode
335 // we have to decide if we've done a good enough job and if we haven't, we've
336 // been asked to commit ritual suicide.
338 // We check the simulation time against the current real time to make this
341 if (m_synchronizationMode == SYNC_HARD_LIMIT)
343 uint64_t tsFinal = m_synchronizer->GetCurrentRealtime ();
346 if (tsFinal >= m_currentTs)
348 tsJitter = tsFinal - m_currentTs;
352 tsJitter = m_currentTs - tsFinal;
355 if (tsJitter > static_cast<uint64_t>(m_hardLimit.GetTimeStep ()))
357 NS_FATAL_ERROR ("RealtimeSimulatorImpl::ProcessOneEvent (): "
358 "Hard real-time limit exceeded (jitter = " << tsJitter << ")");
364 // We have got the event we're about to execute completely disentangled from the
365 // event list so we can execute it outside a critical section without fear of someone
366 // changing things out from under us.
368 EventImpl *event = next.impl;
369 m_synchronizer->EventStart ();
371 m_synchronizer->EventEnd ();
376 RealtimeSimulatorImpl::IsFinished (void) const
378 NS_LOG_FUNCTION_NOARGS ();
381 CriticalSection cs (m_mutex);
382 rc = m_events->IsEmpty () || m_stop;
389 // Peeks into event list. Should be called with critical section locked.
392 RealtimeSimulatorImpl::NextTs (void) const
394 NS_LOG_FUNCTION_NOARGS ();
395 NS_ASSERT_MSG (m_events->IsEmpty () == false,
396 "RealtimeSimulatorImpl::NextTs(): event queue is empty");
397 Scheduler::Event ev = m_events->PeekNext ();
402 // Calls NextTs(). Should be called with critical section locked.
405 RealtimeSimulatorImpl::Next (void) const
407 NS_LOG_FUNCTION_NOARGS ();
408 return TimeStep (NextTs ());
412 RealtimeSimulatorImpl::Run (void)
414 NS_LOG_FUNCTION_NOARGS ();
416 NS_ASSERT_MSG (m_running == false,
417 "RealtimeSimulatorImpl::Run(): Simulator already running");
421 m_synchronizer->SetOrigin (m_currentTs);
428 CriticalSection cs (m_mutex);
430 // In all cases we stop when the event list is empty. If you are doing a
431 // realtime simulation and you want it to extend out for some time, you must
432 // call StopAt. In the realtime case, this will stick a placeholder event out
433 // at the end of time.
435 if (m_stop || m_events->IsEmpty ())
450 // If the simulator stopped naturally by lack of events, make a
451 // consistency test to check that we didn't lose any events along the way.
454 CriticalSection cs (m_mutex);
456 NS_ASSERT_MSG (m_events->IsEmpty () == false || m_unscheduledEvents == 0,
457 "RealtimeSimulatorImpl::Run(): Empty queue and unprocessed events");
464 RealtimeSimulatorImpl::Running (void) const
466 NS_LOG_FUNCTION_NOARGS ();
471 RealtimeSimulatorImpl::Realtime (void) const
473 NS_LOG_FUNCTION_NOARGS ();
474 return m_synchronizer->Realtime ();
478 // This will run the first event on the queue without considering any realtime
479 // synchronization. It's mainly implemented to allow simulations requiring
480 // the multithreaded ScheduleRealtimeNow() functions the possibility of driving
481 // the simulation from their own event loop.
483 // It is expected that if there are any realtime requirements, the responsibility
484 // for synchronizing with real time in an external event loop will be picked up
485 // by that loop. For example, they may call Simulator::Next() to find the
486 // execution time of the next event and wait for that time somehow -- then call
487 // RunOneEvent to fire the event.
490 RealtimeSimulatorImpl::RunOneEvent (void)
492 NS_LOG_FUNCTION_NOARGS ();
494 NS_ASSERT_MSG (m_running == false,
495 "RealtimeSimulatorImpl::RunOneEvent(): An internal simulator event loop is running");
497 EventImpl *event = 0;
500 // Run this in a critical section in case there's another thread around that
501 // may be inserting things onto the event list.
504 CriticalSection cs (m_mutex);
506 Scheduler::Event next = m_events->RemoveNext ();
508 NS_ASSERT (next.key.m_ts >= m_currentTs);
509 --m_unscheduledEvents;
511 NS_LOG_LOGIC ("handle " << next.key.m_ts);
512 m_currentTs = next.key.m_ts;
513 m_currentUid = next.key.m_ts;
521 RealtimeSimulatorImpl::Stop (void)
523 NS_LOG_FUNCTION_NOARGS ();
528 // Schedule an event for a _relative_ time in the future.
531 RealtimeSimulatorImpl::Schedule (Time const &time, EventImpl *impl)
533 NS_LOG_FUNCTION (time << impl);
537 CriticalSection cs (m_mutex);
539 // This is the reason we had to bring the absolute time calcualtion in from the
540 // simulator.h into the implementation. Since the implementations may be
541 // multi-threaded, we need this calculation to be atomic. You can see it is
542 // here since we are running in a CriticalSection.
544 Time tAbsolute = Simulator::Now () + time;
545 NS_ASSERT_MSG (tAbsolute.IsPositive (), "RealtimeSimulatorImpl::Schedule(): Negative time");
546 NS_ASSERT_MSG (tAbsolute >= TimeStep (m_currentTs), "RealtimeSimulatorImpl::Schedule(): time < m_currentTs");
548 ev.key.m_ts = (uint64_t) tAbsolute.GetTimeStep ();
549 ev.key.m_uid = m_uid;
551 ++m_unscheduledEvents;
552 m_events->Insert (ev);
553 m_synchronizer->Signal ();
556 return EventId (impl, ev.key.m_ts, ev.key.m_uid);
560 RealtimeSimulatorImpl::ScheduleNow (EventImpl *impl)
562 NS_LOG_FUNCTION_NOARGS ();
565 CriticalSection cs (m_mutex);
568 ev.key.m_ts = m_currentTs;
569 ev.key.m_uid = m_uid;
571 ++m_unscheduledEvents;
572 m_events->Insert (ev);
573 m_synchronizer->Signal ();
576 return EventId (impl, ev.key.m_ts, ev.key.m_uid);
580 RealtimeSimulatorImpl::Now (void) const
582 return TimeStep (m_currentTs);
586 // Schedule an event for a _relative_ time in the future.
589 RealtimeSimulatorImpl::ScheduleRealtime (Time const &time, EventImpl *impl)
591 NS_LOG_FUNCTION (time << impl);
595 CriticalSection cs (m_mutex);
597 uint64_t ts = m_synchronizer->GetCurrentRealtime () + time.GetTimeStep ();
598 NS_ASSERT_MSG (ts >= m_currentTs, "RealtimeSimulatorImpl::ScheduleRealtime(): schedule for time < m_currentTs");
602 ev.key.m_uid = m_uid;
604 ++m_unscheduledEvents;
605 m_events->Insert (ev);
606 m_synchronizer->Signal ();
612 RealtimeSimulatorImpl::ScheduleRealtimeNow (EventImpl *impl)
614 NS_LOG_FUNCTION_NOARGS ();
616 CriticalSection cs (m_mutex);
619 // If the simulator is running, we're pacing and have a meaningful
620 // realtime clock. If we're not, then m_currentTs is were we stopped.
622 uint64_t ts = m_running ? m_synchronizer->GetCurrentRealtime () : m_currentTs;
623 NS_ASSERT_MSG (ts >= m_currentTs, "RealtimeSimulatorImpl::ScheduleRealtimeNow(): schedule for time < m_currentTs");
627 ev.key.m_uid = m_uid;
629 ++m_unscheduledEvents;
630 m_events->Insert (ev);
631 m_synchronizer->Signal ();
636 RealtimeSimulatorImpl::RealtimeNow (void) const
638 return TimeStep (m_synchronizer->GetCurrentRealtime ());
642 RealtimeSimulatorImpl::ScheduleDestroy (EventImpl *impl)
644 NS_LOG_FUNCTION_NOARGS ();
648 CriticalSection cs (m_mutex);
651 // Time doesn't really matter here (especially in realtime mode). It is
652 // overridden by the uid of 2 which identifies this as an event to be
653 // executed at Simulator::Destroy time.
655 id = EventId (Ptr<EventImpl> (impl, false), m_currentTs, 2);
656 m_destroyEvents.push_back (id);
664 RealtimeSimulatorImpl::GetDelayLeft (const EventId &id) const
667 // If the event has expired, there is no delay until it runs. It is not the
668 // case that there is a negative time until it runs.
675 return TimeStep (id.GetTs () - m_currentTs);
679 RealtimeSimulatorImpl::Remove (const EventId &id)
681 if (id.GetUid () == 2)
684 for (DestroyEvents::iterator i = m_destroyEvents.begin ();
685 i != m_destroyEvents.end ();
690 m_destroyEvents.erase (i);
702 CriticalSection cs (m_mutex);
704 Scheduler::Event event;
705 event.impl = id.PeekEventImpl ();
706 event.key.m_ts = id.GetTs ();
707 event.key.m_uid = id.GetUid ();
709 m_events->Remove (event);
710 --m_unscheduledEvents;
711 event.impl->Cancel ();
712 event.impl->Unref ();
717 RealtimeSimulatorImpl::Cancel (const EventId &id)
719 if (IsExpired (id) == false)
721 id.PeekEventImpl ()->Cancel ();
726 RealtimeSimulatorImpl::IsExpired (const EventId &ev) const
728 if (ev.GetUid () == 2)
730 if (ev.PeekEventImpl () == 0 ||
731 ev.PeekEventImpl ()->IsCancelled ())
736 for (DestroyEvents::const_iterator i = m_destroyEvents.begin ();
737 i != m_destroyEvents.end (); i++)
748 // If the time of the event is less than the current timestamp of the
749 // simulator, the simulator has gone past the invocation time of the
750 // event, so the statement ev.GetTs () < m_currentTs does mean that
751 // the event has been fired even in realtime mode.
753 // The same is true for the next line involving the m_currentUid.
755 if (ev.PeekEventImpl () == 0 ||
756 ev.GetTs () < m_currentTs ||
757 (ev.GetTs () == m_currentTs && ev.GetUid () <= m_currentUid) ||
758 ev.PeekEventImpl ()->IsCancelled ())
769 RealtimeSimulatorImpl::GetMaximumSimulationTime (void) const
771 // XXX: I am fairly certain other compilers use other non-standard
772 // post-fixes to indicate 64 bit constants.
773 return TimeStep (0x7fffffffffffffffLL);
777 RealtimeSimulatorImpl::SetSynchronizationMode (enum SynchronizationMode mode)
779 NS_LOG_FUNCTION (mode);
780 m_synchronizationMode = mode;
783 RealtimeSimulatorImpl::SynchronizationMode
784 RealtimeSimulatorImpl::GetSynchronizationMode (void) const
786 NS_LOG_FUNCTION_NOARGS ();
787 return m_synchronizationMode;
791 RealtimeSimulatorImpl::SetHardLimit (Time limit)
793 NS_LOG_FUNCTION (limit);
798 RealtimeSimulatorImpl::GetHardLimit (void) const
800 NS_LOG_FUNCTION_NOARGS ();