A Discrete-Event Network Simulator
API
wall-clock-synchronizer.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 <ctime> // clock_t
20 #include <sys/time.h> // gettimeofday
21  // clock_getres: glibc < 2.17, link with librt
22 
23 #include "log.h"
25 
26 #include <condition_variable>
27 #include <chrono>
28 #include <mutex>
29 
36 namespace ns3 {
37 
38 NS_LOG_COMPONENT_DEFINE ("WallClockSynchronizer");
39 
40 NS_OBJECT_ENSURE_REGISTERED (WallClockSynchronizer);
41 
42 TypeId
44 {
45  static TypeId tid = TypeId ("ns3::WallClockSynchronizer")
47  .SetGroupName ("Core")
48  ;
49  return tid;
50 }
51 
53 {
54  NS_LOG_FUNCTION (this);
55 //
56 // In Linux, the basic timekeeping unit is derived from a variable called HZ
57 // HZ is the frequency in hertz of the system timer. The system timer fires
58 // every 1/HZ seconds and a counter, called the jiffies counter is incremented
59 // at each tick. The time between ticks is called a jiffy (American slang for
60 // a short period of time). The ticking of the jiffies counter is how the
61 // the kernel tells time.
62 //
63 // Now, the shortest time the kernel can sleep is one jiffy since a timer
64 // has to be set to expire and trigger the process to be made ready. The
65 // Posix clock CLOCK_REALTIME is defined as a 1/HZ clock, so by doing a
66 // clock_getres () on the realtime clock we can infer the scheduler quantum
67 // and the minimimum sleep time for the system. This is most certainly NOT
68 // going to be one nanosecond even though clock_nanosleep () pretends it is.
69 //
70 // The reason this number is important is that we are going to schedule lots
71 // of waits for less time than a jiffy. The clock_nanosleep function is
72 // going to guarantee that it will sleep for AT LEAST the time specified.
73 // The least time that it will sleep is a jiffy.
74 //
75 // In order to deal with this, we are going to do a spin-wait if the simulator
76 // requires a delay less than a jiffy. This is on the order of one millisecond
77 // (999848 ns) on the ns-regression machine.
78 //
79 // If the underlying OS does not support posix clocks, we'll just assume a
80 // one millisecond quantum and deal with this as best we can
81 
82 #ifdef CLOCK_REALTIME
83  struct timespec ts;
84  clock_getres (CLOCK_REALTIME, &ts);
85  m_jiffy = ts.tv_sec * NS_PER_SEC + ts.tv_nsec;
86  NS_LOG_INFO ("Jiffy is " << m_jiffy << " ns");
87 #else
88  m_jiffy = 1000000;
89 #endif
90 }
91 
93 {
94  NS_LOG_FUNCTION (this);
95 }
96 
97 bool
99 {
100  NS_LOG_FUNCTION (this);
101  return true;
102 }
103 
104 uint64_t
106 {
107  NS_LOG_FUNCTION (this);
108  return GetNormalizedRealtime ();
109 }
110 
111 void
113 {
114  NS_LOG_FUNCTION (this << ns);
115 //
116 // In order to make sure we're really locking the simulation time to some
117 // wall-clock time, we need to be able to compare that simulation time to
118 // that wall-clock time. The wall clock will have been running for some
119 // long time and will probably have a huge count of nanoseconds in it. We
120 // save the real time away so we can subtract it from "now" later and get
121 // a count of nanoseconds in real time since the simulation started.
122 //
124  NS_LOG_INFO ("origin = " << m_realtimeOriginNano);
125 }
126 
127 int64_t
129 {
130  NS_LOG_FUNCTION (this << ns);
131 //
132 // In order to make sure we're really locking the simulation time to some
133 // wall-clock time, we need to be able to compare that simulation time to
134 // that wall-clock time. In DoSetOrigin we saved the real time at the start
135 // of the simulation away. This is the place where we subtract it from "now"
136 // to a count of nanoseconds in real time since the simulation started. We
137 // then subtract the current real time in normalized nanoseconds we just got
138 // from the normalized simulation time in nanoseconds that is passed in as
139 // the parameter ns. We return an integer difference, but in reality all of
140 // the mechanisms that cause wall-clock to simuator time drift cause events
141 // to be late. That means that the wall-clock will be higher than the
142 // simulation time and drift will be positive. I would be astonished to
143 // see a negative drift, but the possibility is admitted for other
144 // implementations; and we'll use the ability to report an early result in
145 // DoSynchronize below.
146 //
147  uint64_t nsNow = GetNormalizedRealtime ();
148 
149  if (nsNow > ns)
150  {
151 //
152 // Real time (nsNow) is larger/later than the simulator time (ns). We are
153 // behind real time and the difference (drift) is positive.
154 //
155  return (int64_t)(nsNow - ns);
156  }
157  else
158  {
159 //
160 // Real time (nsNow) is smaller/earlier than the simulator time (ns). We are
161 // ahead of real time and the difference (drift) is negative.
162 //
163  return -(int64_t)(ns - nsNow);
164  }
165 }
166 
167 bool
168 WallClockSynchronizer::DoSynchronize (uint64_t nsCurrent, uint64_t nsDelay)
169 {
170  NS_LOG_FUNCTION (this << nsCurrent << nsDelay);
171 //
172 // This is the belly of the beast. We have received two parameters from the
173 // simulator proper -- a current simulation time (nsCurrent) and a simulation
174 // time to delay which identifies the time the next event is supposed to fire.
175 //
176 // The first thing we need to do is to (try and) correct for any realtime
177 // drift that has happened in the system. In this implementation, we realize
178 // that all mechanisms for drift will cause the drift to be such that the
179 // realtime is greater than the simulation time. This typically happens when
180 // our process is put to sleep for a given time, but actually sleeps for
181 // longer. So, what we want to do is to "catch up" to realtime and delay for
182 // less time than we are actually asked to delay. DriftCorrect will return a
183 // number from 0 to nsDelay corresponding to the amount of catching-up we
184 // need to do. If we are more than nsDelay behind, we do not wait at all.
185 //
186 // Note that it will be impossible to catch up if the amount of drift is
187 // cumulatively greater than the amount of delay between events. The method
188 // GetDrift () is available to clients of the syncrhonizer to keep track of
189 // the cumulative drift. The client can assert if the drift gets out of
190 // hand, print warning messages, or just ignore the situation and hope it will
191 // go away.
192 //
193  uint64_t ns = DriftCorrect (nsCurrent, nsDelay);
194  NS_LOG_INFO ("Synchronize ns = " << ns);
195 //
196 // Once we've decided on how long we need to delay, we need to split this
197 // time into sleep waits and busy waits. The reason for this is described
198 // in the comments for the constructor where jiffies and jiffy resolution is
199 // explained.
200 //
201 // Here, I'll just say that we need that the jiffy is the minimum resolution
202 // of the system clock. It can only sleep in blocks of time equal to a jiffy.
203 // If we want to be more accurate than a jiffy (we do) then we need to sleep
204 // for some number of jiffies and then busy wait for any leftover time.
205 //
206  uint64_t numberJiffies = ns / m_jiffy;
207  NS_LOG_INFO ("Synchronize numberJiffies = " << numberJiffies);
208 //
209 // This is where the real world interjects its very ugly head. The code
210 // immediately below reflects the fact that a sleep is actually quite probably
211 // going to end up sleeping for some number of jiffies longer than you wanted.
212 // This is because your system is going to be off doing other unimportant
213 // stuff during that extra time like running file systems and networks. What
214 // we want to do is to ask the system to sleep enough less than the requested
215 // delay so that it comes back early most of the time (coming back early is
216 // fine, coming back late is bad). If we can convince the system to come back
217 // early (most of the time), then we can busy-wait until the requested
218 // completion time actually comes around (most of the time).
219 //
220 // The tradeoff here is, of course, that the less time we spend sleeping, the
221 // more accurately we will sync up; but the more CPU time we will spend busy
222 // waiting (doing nothing).
223 //
224 // I'm not really sure about this number -- a boss of mine once said, "pick
225 // a number and it'll be wrong." But this works for now.
226 //
227 // \todo Hardcoded tunable parameter below.
228 //
229  if (numberJiffies > 3)
230  {
231  NS_LOG_INFO ("SleepWait for " << numberJiffies * m_jiffy << " ns");
232  NS_LOG_INFO ("SleepWait until " << nsCurrent + numberJiffies * m_jiffy
233  << " ns");
234 //
235 // SleepWait is interruptible. If it returns true it meant that the sleep
236 // went until the end. If it returns false, it means that the sleep was
237 // interrupted by a Signal. In this case, we need to return and let the
238 // simulator re-evaluate what to do.
239 //
240  if (SleepWait ((numberJiffies - 3) * m_jiffy) == false)
241  {
242  NS_LOG_INFO ("SleepWait interrupted");
243  return false;
244  }
245  }
246  NS_LOG_INFO ("Done with SleepWait");
247 //
248 // We asked the system to sleep for some number of jiffies, but that doesn't
249 // mean we actually did. Let's re-evaluate what we need to do here. Maybe
250 // we're already late. Probably the "real" delay time left has little to do
251 // with what we would calculate it to be naively.
252 //
253 // We are now at some Realtime. The important question now is not, "what
254 // would we calculate in a mathematicians paradise," it is, "how many
255 // nanoseconds do we need to busy-wait until we get to the Realtime that
256 // corresponds to nsCurrent + nsDelay (in simulation time). We have a handy
257 // function to do just that -- we ask for the time the realtime clock has
258 // drifted away from the simulation clock. That's our answer. If the drift
259 // is negative, we're early and we need to busy wait for that number of
260 // nanoseconds. The place were we want to be is described by the parameters
261 // we were passed by the simulator.
262 //
263  int64_t nsDrift = DoGetDrift (nsCurrent + nsDelay);
264 //
265 // If the drift is positive, we are already late and we need to just bail out
266 // of here as fast as we can. Return true to indicate that the requested time
267 // has, in fact, passed.
268 //
269  if (nsDrift >= 0)
270  {
271  NS_LOG_INFO ("Back from SleepWait: IML8 " << nsDrift);
272  return true;
273  }
274 //
275 // There are some number of nanoseconds left over and we need to wait until
276 // the time defined by nsDrift. We'll do a SpinWait since the usual case
277 // will be that we are doing this Spinwait after we've gotten a rough delay
278 // using the SleepWait above. If SpinWait completes to the end, it will
279 // return true; if it is interrupted by a signal it will return false.
280 //
281  NS_LOG_INFO ("SpinWait until " << nsCurrent + nsDelay);
282  return SpinWait (nsCurrent + nsDelay);
283 }
284 
285 void
287 {
288  NS_LOG_FUNCTION (this);
289 
290  std::unique_lock<std::mutex> lock (m_mutex);
291  m_condition = true;
292 
293  // Manual unlocking is done before notifying, to avoid waking up
294  // the waiting thread only to block again (see notify_one for details).
295  // Reference: https://en.cppreference.com/w/cpp/thread/condition_variable
296  lock.unlock ();
297  m_conditionVariable.notify_one ();
298 }
299 
300 void
302 {
303  NS_LOG_FUNCTION (this << cond);
304  m_condition = cond;
305 }
306 
307 void
309 {
310  NS_LOG_FUNCTION (this);
312 }
313 
314 uint64_t
316 {
317  NS_LOG_FUNCTION (this);
319 }
320 
321 bool
323 {
324  NS_LOG_FUNCTION (this << ns);
325 // We just sit here and spin, wasting CPU cycles until we get to the right
326 // time or are told to leave.
327  for (;;)
328  {
329  if (GetNormalizedRealtime () >= ns)
330  {
331  return true;
332  }
333  if (m_condition)
334  {
335  return false;
336  }
337  }
338 // Quiet compiler
339  return true;
340 }
341 
342 bool
344 {
345  NS_LOG_FUNCTION (this << ns);
346 
347  std::unique_lock<std::mutex> lock (m_mutex);
348  bool finishedWaiting = m_conditionVariable.wait_for (
349  lock,
350  std::chrono::nanoseconds (ns), // Timeout
351  [this](){ return m_condition; }); // Wait condition
352 
353  return finishedWaiting;
354 }
355 
356 uint64_t
357 WallClockSynchronizer::DriftCorrect (uint64_t nsNow, uint64_t nsDelay)
358 {
359  NS_LOG_FUNCTION (this << nsNow << nsDelay);
360  int64_t drift = DoGetDrift (nsNow);
361 //
362 // If we're running late, drift will be positive and we need to correct by
363 // delaying for less time. If we're early for some bizarre reason, we don't
364 // do anything since we'll almost instantly self-correct.
365 //
366  if (drift < 0)
367  {
368  return nsDelay;
369  }
370 //
371 // If we've drifted out of sync by less than the requested delay, then just
372 // subtract the drift from the delay and fix up the drift in one go. If we
373 // have more drift than delay, then we just play catch up as fast as possible
374 // by not delaying at all.
375 //
376  uint64_t correction = (uint64_t)drift;
377  if (correction <= nsDelay)
378  {
379  return nsDelay - correction;
380  }
381  else
382  {
383  return 0;
384  }
385 }
386 
387 uint64_t
389 {
390  NS_LOG_FUNCTION (this);
391  struct timeval tvNow;
392  gettimeofday (&tvNow, NULL);
393  return TimevalToNs (&tvNow);
394 }
395 
396 uint64_t
398 {
399  NS_LOG_FUNCTION (this);
400  return GetRealtime () - m_realtimeOriginNano;
401 }
402 
403 void
404 WallClockSynchronizer::NsToTimeval (int64_t ns, struct timeval *tv)
405 {
406  NS_LOG_FUNCTION (this << ns << tv);
407  NS_ASSERT ((ns % US_PER_NS) == 0);
408  tv->tv_sec = static_cast<long> (ns / NS_PER_SEC);
409  tv->tv_usec = (ns % NS_PER_SEC) / US_PER_NS;
410 }
411 
412 uint64_t
414 {
415  NS_LOG_FUNCTION (this << tv);
416  uint64_t nsResult = tv->tv_sec * NS_PER_SEC + tv->tv_usec * US_PER_NS;
417  NS_ASSERT ((nsResult % US_PER_NS) == 0);
418  return nsResult;
419 }
420 
421 void
423  struct timeval *tv1,
424  struct timeval *tv2,
425  struct timeval *result)
426 {
427  NS_LOG_FUNCTION (this << tv1 << tv2 << result);
428  result->tv_sec = tv1->tv_sec + tv2->tv_sec;
429  result->tv_usec = tv1->tv_usec + tv2->tv_usec;
430  if (result->tv_usec > (int64_t)US_PER_SEC)
431  {
432  ++result->tv_sec;
433  result->tv_usec %= US_PER_SEC;
434  }
435 }
436 
437 } // namespace ns3
Base class used for synchronizing the simulation events to some real time "wall clock....
Definition: synchronizer.h:52
uint64_t m_realtimeOriginNano
The real time, in ns, when SetOrigin was called.
Definition: synchronizer.h:317
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
virtual void DoSetOrigin(uint64_t ns)
Establish a correspondence between a simulation time and a wall-clock (real) time.
static const uint64_t NS_PER_SEC
Conversion constant between ns and s.
uint64_t GetNormalizedRealtime(void)
Get the current normalized real time, in ns.
bool SleepWait(uint64_t ns)
Put our process to sleep for some number of nanoseconds.
virtual ~WallClockSynchronizer()
Destructor.
void NsToTimeval(int64_t ns, struct timeval *tv)
Convert an absolute time in ns to a timeval.
virtual bool DoSynchronize(uint64_t nsCurrent, uint64_t nsDelay)
Wait until the real time is in sync with the specified simulation time.
uint64_t m_jiffy
Size of the system clock tick, as reported by clock_getres, in ns.
virtual bool DoRealtime(void)
Return true if this synchronizer is actually synchronizing to a realtime clock.
uint64_t TimevalToNs(struct timeval *tv)
Convert a timeval to absolute time, in ns.
bool m_condition
The condition state.
static const uint64_t US_PER_NS
Conversion constant between μs and ns.
virtual void DoSignal(void)
Tell a possible simulator thread waiting in the DoSynchronize method that an event has happened which...
static TypeId GetTypeId(void)
Get the registered TypeId for this class.
virtual uint64_t DoGetCurrentRealtime(void)
Retrieve the value of the origin of the underlying normalized wall clock time in Time resolution unit...
virtual int64_t DoGetDrift(uint64_t ns)
Get the drift between the real time clock used to synchronize the simulation and the current simulati...
uint64_t GetRealtime(void)
Get the current absolute real time (in ns since the epoch).
uint64_t m_nsEventStart
Time recorded by DoEventStart.
void TimevalAdd(struct timeval *tv1, struct timeval *tv2, struct timeval *result)
Add two timeval.
bool SpinWait(uint64_t ns)
Do a busy-wait until the normalized realtime equals the argument or the condition variable becomes tr...
static const uint64_t US_PER_SEC
Conversion constant between μs and seconds.
std::condition_variable m_conditionVariable
Condition variable for thread synchronizer.
virtual void DoEventStart(void)
Record the normalized real time at which the current event is starting execution.
virtual void DoSetCondition(bool cond)
Set the condition variable to tell a possible simulator thread waiting in the Synchronize method that...
virtual uint64_t DoEventEnd(void)
Return the amount of real time elapsed since the last call to EventStart.
uint64_t DriftCorrect(uint64_t nsNow, uint64_t nsDelay)
Compute a correction to the nominal delay to account for realtime drift since the last DoSynchronize.
std::mutex m_mutex
Mutex controlling access to the condition variable.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition: assert.h:67
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:281
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::WallClockSynchronizer declaration.