A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
realtime-simulator-impl.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2008 University of Washington
4  *
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;
8  *
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.
13  *
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
17  */
18 
19 #include "simulator.h"
22 #include "scheduler.h"
23 #include "event-impl.h"
24 #include "synchronizer.h"
25 
26 #include "ptr.h"
27 #include "pointer.h"
28 #include "assert.h"
29 #include "fatal-error.h"
30 #include "log.h"
31 #include "system-mutex.h"
32 #include "boolean.h"
33 #include "enum.h"
34 
35 
36 #include <math.h>
37 
38 NS_LOG_COMPONENT_DEFINE ("RealtimeSimulatorImpl");
39 
40 namespace ns3 {
41 
42 NS_OBJECT_ENSURE_REGISTERED (RealtimeSimulatorImpl);
43 
44 TypeId
46 {
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.",
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),
60  MakeTimeChecker ())
61  ;
62  return tid;
63 }
64 
65 
67 {
69 
70  m_stop = false;
71  m_running = false;
72  // uids are allocated from 4.
73  // uid 0 is "invalid" events
74  // uid 1 is "now" events
75  // uid 2 is "destroy" events
76  m_uid = 4;
77  // before ::Run is entered, the m_currentUid will be zero
78  m_currentUid = 0;
79  m_currentTs = 0;
80  m_currentContext = 0xffffffff;
82 
84 
85  // Be very careful not to do anything that would cause a change or assignment
86  // of the underlying reference counts of m_synchronizer or you will be sorry.
87  m_synchronizer = CreateObject<WallClockSynchronizer> ();
88 }
89 
91 {
92 }
93 
94 void
96 {
98  while (!m_events->IsEmpty ())
99  {
101  next.impl->Unref ();
102  }
103  m_events = 0;
104  m_synchronizer = 0;
106 }
107 
108 void
110 {
112 
113  //
114  // This function is only called with the private version "disconnected" from
115  // the main simulator functions. We rely on the user not calling
116  // Simulator::Destroy while there is a chance that a worker thread could be
117  // accessing the current instance of the private object. In practice this
118  // means shutting down the workers and doing a Join() before calling the
119  // Simulator::Destroy().
120  //
121  while (m_destroyEvents.empty () == false)
122  {
123  Ptr<EventImpl> ev = m_destroyEvents.front ().PeekEventImpl ();
124  m_destroyEvents.pop_front ();
125  NS_LOG_LOGIC ("handle destroy " << ev);
126  if (ev->IsCancelled () == false)
127  {
128  ev->Invoke ();
129  }
130  }
131 }
132 
133 void
135 {
137 
138  Ptr<Scheduler> scheduler = schedulerFactory.Create<Scheduler> ();
139 
140  {
142 
143  if (m_events != 0)
144  {
145  while (m_events->IsEmpty () == false)
146  {
148  scheduler->Insert (next);
149  }
150  }
151  m_events = scheduler;
152  }
153 }
154 
155 void
157 {
159  //
160  // The idea here is to wait until the next event comes due. In the case of
161  // a realtime simulation, we want real time to be consumed between events.
162  // It is the realtime synchronizer that causes real time to be consumed by
163  // doing some kind of a wait.
164  //
165  // We need to be able to have external events (such as a packet reception event)
166  // cause us to re-evaluate our state. The way this works is that the synchronizer
167  // gets interrupted and returns. So, there is a possibility that things may change
168  // out from under us dynamically. In this case, we need to re-evaluate how long to
169  // wait in a for-loop until we have waited sucessfully (until a timeout) for the
170  // event at the head of the event list.
171  //
172  // m_synchronizer->Synchronize will return true if the wait was completed without
173  // interruption, otherwise it will return false indicating that something has changed
174  // out from under us. If we sit in the for-loop trying to synchronize until
175  // Synchronize() returns true, we will have successfully synchronized the execution
176  // time of the next event with the wall clock time of the synchronizer.
177  //
178 
179  for (;;)
180  {
181  uint64_t tsDelay = 0;
182  uint64_t tsNext = 0;
183 
184  //
185  // It is important to understand that m_currentTs is interpreted only as the
186  // timestamp of the last event we executed. Current time can a bit of a
187  // slippery concept in realtime mode. What we have here is a discrete event
188  // simulator, so the last event is, by defintion, executed entirely at a single
189  // discrete time. This is the definition of m_currentTs. It really has
190  // nothing to do with the current real time, except that we are trying to arrange
191  // that at the instant of the beginning of event execution, the current real time
192  // and m_currentTs coincide.
193  //
194  // We use tsNow as the indication of the current real time.
195  //
196  uint64_t tsNow;
197 
198  {
200  //
201  // Since we are in realtime mode, the time to delay has got to be the
202  // difference between the current realtime and the timestamp of the next
203  // event. Since m_currentTs is actually the timestamp of the last event we
204  // executed, it's not particularly meaningful for us here since real time has
205  // certainly elapsed since it was last updated.
206  //
207  // It is possible that the current realtime has drifted past the next event
208  // time so we need to be careful about that and not delay in that case.
209  //
211  "RealtimeSimulatorImpl::ProcessOneEvent (): Synchronizer reports not Realtime ()");
212 
213  //
214  // tsNow is set to the normalized current real time. When the simulation was
215  // started, the current real time was effectively set to zero; so tsNow is
216  // the current "real" simulation time.
217  //
218  // tsNext is the simulation time of the next event we want to execute.
219  //
221  tsNext = NextTs ();
222 
223  //
224  // tsDelay is therefore the real time we need to delay in order to bring the
225  // real time in sync with the simulation time. If we wait for this amount of
226  // real time, we will accomplish moving the simulation time at the same rate
227  // as the real time. This is typically called "pacing" the simulation time.
228  //
229  // We do have to be careful if we are falling behind. If so, tsDelay must be
230  // zero. If we're late, don't dawdle.
231  //
232  if (tsNext <= tsNow)
233  {
234  tsDelay = 0;
235  }
236  else
237  {
238  tsDelay = tsNext - tsNow;
239  }
240 
241  //
242  // We've figured out how long we need to delay in order to pace the
243  // simulation time with the real time. We're going to sleep, but need
244  // to work with the synchronizer to make sure we're awakened if something
245  // external happens (like a packet is received). This next line resets
246  // the synchronizer so that any future event will cause it to interrupt.
247  //
248  m_synchronizer->SetCondition (false);
249  }
250 
251  //
252  // We have a time to delay. This time may actually not be valid anymore
253  // since we released the critical section immediately above, and a real-time
254  // ScheduleReal or ScheduleRealNow may have snuck in, well, between the
255  // closing brace above and this comment so to speak. If this is the case,
256  // that schedule operation will have done a synchronizer Signal() that
257  // will set the condition variable to true and cause the Synchronize call
258  // below to return immediately.
259  //
260  // It's easiest to understand if you just consider a short tsDelay that only
261  // requires a SpinWait down in the synchronizer. What will happen is that
262  // whan Synchronize calls SpinWait, SpinWait will look directly at its
263  // condition variable. Note that we set this condition variable to false
264  // inside the critical section above.
265  //
266  // SpinWait will go into a forever loop until either the time has expired or
267  // until the condition variable becomes true. A true condition indicates that
268  // the wait should stop. The condition is set to true by one of the Schedule
269  // methods of the simulator; so if we are in a wait down in Synchronize, and
270  // a Simulator::ScheduleReal is done, the wait down in Synchronize will exit and
271  // Synchronize will return false. This means we have not actually synchronized
272  // to the event expiration time. If no real-time schedule operation is done
273  // while down in Synchronize, the wait will time out and Synchronize will return
274  // true. This indicates that we have synchronized to the event time.
275  //
276  // So we need to stay in this for loop, looking for the next event timestamp and
277  // attempting to sleep until its due. If we've slept until the timestamp is due,
278  // Synchronize returns true and we break out of the sync loop. If an external
279  // event happens that requires a re-schedule, Synchronize returns false and
280  // we re-evaluate our timing by continuing in the loop.
281  //
282  // It is expected that tsDelay become shorter as external events interrupt our
283  // waits.
284  //
285  if (m_synchronizer->Synchronize (tsNow, tsDelay))
286  {
287  NS_LOG_LOGIC ("Interrupted ...");
288  break;
289  }
290 
291  //
292  // If we get to this point, we have been interrupted during a wait by a real-time
293  // schedule operation. This means all bets are off regarding tsDelay and we need
294  // to re-evaluate what it is we want to do. We'll loop back around in the
295  // for-loop and start again from scratch.
296  //
297  }
298 
299  //
300  // If we break out of the for-loop above, we have waited until the time specified
301  // by the event that was at the head of the event list when we started the process.
302  // Since there is a bunch of code that was executed outside a critical section (the
303  // Synchronize call) we cannot be sure that the event at the head of the event list
304  // is the one we think it is. What we can be sure of is that it is time to execute
305  // whatever event is at the head of this list if the list is in time order.
306  //
307  Scheduler::Event next;
308 
309  {
311 
312  //
313  // We do know we're waiting for an event, so there had better be an event on the
314  // event queue. Let's pull it off. When we release the critical section, the
315  // event we're working on won't be on the list and so subsequent operations won't
316  // mess with us.
317  //
318  NS_ASSERT_MSG (m_events->IsEmpty () == false,
319  "RealtimeSimulatorImpl::ProcessOneEvent(): event queue is empty");
320  next = m_events->RemoveNext ();
322 
323  //
324  // We cannot make any assumption that "next" is the same event we originally waited
325  // for. We can only assume that only that it must be due and cannot cause time
326  // to move backward.
327  //
328  NS_ASSERT_MSG (next.key.m_ts >= m_currentTs,
329  "RealtimeSimulatorImpl::ProcessOneEvent(): "
330  "next.GetTs() earlier than m_currentTs (list order error)");
331  NS_LOG_LOGIC ("handle " << next.key.m_ts);
332 
333  //
334  // Update the current simulation time to be the timestamp of the event we're
335  // executing. From the rest of the simulation's point of view, simulation time
336  // is frozen until the next event is executed.
337  //
338  m_currentTs = next.key.m_ts;
339  m_currentContext = next.key.m_context;
340  m_currentUid = next.key.m_uid;
341 
342  //
343  // We're about to run the event and we've done our best to synchronize this
344  // event execution time to real time. Now, if we're in SYNC_HARD_LIMIT mode
345  // we have to decide if we've done a good enough job and if we haven't, we've
346  // been asked to commit ritual suicide.
347  //
348  // We check the simulation time against the current real time to make this
349  // judgement.
350  //
352  {
353  uint64_t tsFinal = m_synchronizer->GetCurrentRealtime ();
354  uint64_t tsJitter;
355 
356  if (tsFinal >= m_currentTs)
357  {
358  tsJitter = tsFinal - m_currentTs;
359  }
360  else
361  {
362  tsJitter = m_currentTs - tsFinal;
363  }
364 
365  if (tsJitter > static_cast<uint64_t>(m_hardLimit.GetTimeStep ()))
366  {
367  NS_FATAL_ERROR ("RealtimeSimulatorImpl::ProcessOneEvent (): "
368  "Hard real-time limit exceeded (jitter = " << tsJitter << ")");
369  }
370  }
371  }
372 
373  //
374  // We have got the event we're about to execute completely disentangled from the
375  // event list so we can execute it outside a critical section without fear of someone
376  // changing things out from under us.
377 
378  EventImpl *event = next.impl;
380  event->Invoke ();
382  event->Unref ();
383 }
384 
385 bool
387 {
389  bool rc;
390  {
392  rc = m_events->IsEmpty () || m_stop;
393  }
394 
395  return rc;
396 }
397 
398 //
399 // Peeks into event list. Should be called with critical section locked.
400 //
401 uint64_t
403 {
405  NS_ASSERT_MSG (m_events->IsEmpty () == false,
406  "RealtimeSimulatorImpl::NextTs(): event queue is empty");
408  return ev.key.m_ts;
409 }
410 
411 void
413 {
415 
416  NS_ASSERT_MSG (m_running == false,
417  "RealtimeSimulatorImpl::Run(): Simulator already running");
418 
419  // Set the current threadId as the main threadId
421 
422  m_stop = false;
423  m_running = true;
425 
426  // Sleep until signalled
427  uint64_t tsNow;
428  uint64_t tsDelay = 1000000000; // wait time of 1 second (in nanoseconds)
429 
430  while (!m_stop)
431  {
432  bool process = false;
433  {
435 
436  if (!m_events->IsEmpty ())
437  {
438  process = true;
439  }
440  else
441  {
442  // Get current timestamp while holding the critical section
444  }
445  }
446 
447  if (!process)
448  {
449  // Sleep until signalled
450  tsNow = m_synchronizer->Synchronize (tsNow, tsDelay);
451 
452  // Re-check event queue
453  continue;
454  }
455 
456  ProcessOneEvent ();
457  }
458 
459  //
460  // If the simulator stopped naturally by lack of events, make a
461  // consistency test to check that we didn't lose any events along the way.
462  //
463  {
465 
466  NS_ASSERT_MSG (m_events->IsEmpty () == false || m_unscheduledEvents == 0,
467  "RealtimeSimulatorImpl::Run(): Empty queue and unprocessed events");
468  }
469 
470  m_running = false;
471 }
472 
473 bool
475 {
477  return m_running;
478 }
479 
480 bool
482 {
484  return m_synchronizer->Realtime ();
485 }
486 
487 void
489 {
491  m_stop = true;
492 }
493 
494 void
496 {
498 }
499 
500 //
501 // Schedule an event for a _relative_ time in the future.
502 //
503 EventId
505 {
506  NS_LOG_FUNCTION (time << impl);
507 
508  Scheduler::Event ev;
509  {
511  //
512  // This is the reason we had to bring the absolute time calcualtion in from the
513  // simulator.h into the implementation. Since the implementations may be
514  // multi-threaded, we need this calculation to be atomic. You can see it is
515  // here since we are running in a CriticalSection.
516  //
517  Time tAbsolute = Simulator::Now () + time;
518  NS_ASSERT_MSG (tAbsolute.IsPositive (), "RealtimeSimulatorImpl::Schedule(): Negative time");
519  NS_ASSERT_MSG (tAbsolute >= TimeStep (m_currentTs), "RealtimeSimulatorImpl::Schedule(): time < m_currentTs");
520  ev.impl = impl;
521  ev.key.m_ts = (uint64_t) tAbsolute.GetTimeStep ();
522  ev.key.m_context = GetContext ();
523  ev.key.m_uid = m_uid;
524  m_uid++;
526  m_events->Insert (ev);
528  }
529 
530  return EventId (impl, ev.key.m_ts, ev.key.m_context, ev.key.m_uid);
531 }
532 
533 void
534 RealtimeSimulatorImpl::ScheduleWithContext (uint32_t context, Time const &time, EventImpl *impl)
535 {
536  NS_LOG_FUNCTION (time << impl);
537 
538  {
540  uint64_t ts;
541 
543  {
544  ts = m_currentTs + time.GetTimeStep ();
545  }
546  else
547  {
548  //
549  // If the simulator is running, we're pacing and have a meaningful
550  // realtime clock. If we're not, then m_currentTs is where we stopped.
551  //
553  ts += time.GetTimeStep ();
554  }
555 
556  NS_ASSERT_MSG (ts >= m_currentTs, "RealtimeSimulatorImpl::ScheduleRealtime(): schedule for time < m_currentTs");
557  Scheduler::Event ev;
558  ev.impl = impl;
559  ev.key.m_ts = ts;
560  ev.key.m_context = context;
561  ev.key.m_uid = m_uid;
562  m_uid++;
564  m_events->Insert (ev);
566  }
567 }
568 
569 EventId
571 {
573  Scheduler::Event ev;
574  {
576 
577  ev.impl = impl;
578  ev.key.m_ts = m_currentTs;
579  ev.key.m_context = GetContext ();
580  ev.key.m_uid = m_uid;
581  m_uid++;
583  m_events->Insert (ev);
585  }
586 
587  return EventId (impl, ev.key.m_ts, ev.key.m_context, ev.key.m_uid);
588 }
589 
590 Time
592 {
593  return TimeStep (m_currentTs);
594 }
595 
596 //
597 // Schedule an event for a _relative_ time in the future.
598 //
599 void
601 {
602  NS_LOG_FUNCTION (context << time << impl);
603 
604  {
606 
607  uint64_t ts = m_synchronizer->GetCurrentRealtime () + time.GetTimeStep ();
608  NS_ASSERT_MSG (ts >= m_currentTs, "RealtimeSimulatorImpl::ScheduleRealtime(): schedule for time < m_currentTs");
609  Scheduler::Event ev;
610  ev.impl = impl;
611  ev.key.m_ts = ts;
612  ev.key.m_uid = m_uid;
613  m_uid++;
615  m_events->Insert (ev);
617  }
618 }
619 
620 void
622 {
623  NS_LOG_FUNCTION (time << impl);
624  ScheduleRealtimeWithContext (GetContext (), time, impl);
625 }
626 
627 void
629 {
630  NS_LOG_FUNCTION (context << impl);
631  {
633 
634  //
635  // If the simulator is running, we're pacing and have a meaningful
636  // realtime clock. If we're not, then m_currentTs is were we stopped.
637  //
639  NS_ASSERT_MSG (ts >= m_currentTs,
640  "RealtimeSimulatorImpl::ScheduleRealtimeNowWithContext(): schedule for time < m_currentTs");
641  Scheduler::Event ev;
642  ev.impl = impl;
643  ev.key.m_ts = ts;
644  ev.key.m_uid = m_uid;
645  ev.key.m_context = context;
646  m_uid++;
648  m_events->Insert (ev);
650  }
651 }
652 
653 void
655 {
656  NS_LOG_FUNCTION (impl);
658 }
659 
660 Time
662 {
664 }
665 
666 EventId
668 {
670 
671  EventId id;
672  {
674 
675  //
676  // Time doesn't really matter here (especially in realtime mode). It is
677  // overridden by the uid of 2 which identifies this as an event to be
678  // executed at Simulator::Destroy time.
679  //
680  id = EventId (Ptr<EventImpl> (impl, false), m_currentTs, 0xffffffff, 2);
681  m_destroyEvents.push_back (id);
682  m_uid++;
683  }
684 
685  return id;
686 }
687 
688 Time
690 {
691  //
692  // If the event has expired, there is no delay until it runs. It is not the
693  // case that there is a negative time until it runs.
694  //
695  if (IsExpired (id))
696  {
697  return TimeStep (0);
698  }
699 
700  return TimeStep (id.GetTs () - m_currentTs);
701 }
702 
703 void
705 {
706  if (id.GetUid () == 2)
707  {
708  // destroy events.
709  for (DestroyEvents::iterator i = m_destroyEvents.begin ();
710  i != m_destroyEvents.end ();
711  i++)
712  {
713  if (*i == id)
714  {
715  m_destroyEvents.erase (i);
716  break;
717  }
718  }
719  return;
720  }
721  if (IsExpired (id))
722  {
723  return;
724  }
725 
726  {
728 
729  Scheduler::Event event;
730  event.impl = id.PeekEventImpl ();
731  event.key.m_ts = id.GetTs ();
732  event.key.m_context = id.GetContext ();
733  event.key.m_uid = id.GetUid ();
734 
735  m_events->Remove (event);
737  event.impl->Cancel ();
738  event.impl->Unref ();
739  }
740 }
741 
742 void
744 {
745  if (IsExpired (id) == false)
746  {
747  id.PeekEventImpl ()->Cancel ();
748  }
749 }
750 
751 bool
753 {
754  if (ev.GetUid () == 2)
755  {
756  if (ev.PeekEventImpl () == 0 ||
757  ev.PeekEventImpl ()->IsCancelled ())
758  {
759  return true;
760  }
761  // destroy events.
762  for (DestroyEvents::const_iterator i = m_destroyEvents.begin ();
763  i != m_destroyEvents.end (); i++)
764  {
765  if (*i == ev)
766  {
767  return false;
768  }
769  }
770  return true;
771  }
772 
773  //
774  // If the time of the event is less than the current timestamp of the
775  // simulator, the simulator has gone past the invocation time of the
776  // event, so the statement ev.GetTs () < m_currentTs does mean that
777  // the event has been fired even in realtime mode.
778  //
779  // The same is true for the next line involving the m_currentUid.
780  //
781  if (ev.PeekEventImpl () == 0 ||
782  ev.GetTs () < m_currentTs ||
783  (ev.GetTs () == m_currentTs && ev.GetUid () <= m_currentUid) ||
784  ev.PeekEventImpl ()->IsCancelled ())
785  {
786  return true;
787  }
788  else
789  {
790  return false;
791  }
792 }
793 
794 Time
796 {
797  // XXX: I am fairly certain other compilers use other non-standard
798  // post-fixes to indicate 64 bit constants.
799  return TimeStep (0x7fffffffffffffffLL);
800 }
801 
802 // System ID for non-distributed simulation is always zero
803 uint32_t
805 {
806  return 0;
807 }
808 
809 uint32_t
811 {
812  return m_currentContext;
813 }
814 
815 void
817 {
818  NS_LOG_FUNCTION (mode);
819  m_synchronizationMode = mode;
820 }
821 
824 {
826  return m_synchronizationMode;
827 }
828 
829 void
831 {
832  NS_LOG_FUNCTION (limit);
833  m_hardLimit = limit;
834 }
835 
836 Time
838 {
840  return m_hardLimit;
841 }
842 
843 } // namespace ns3