--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/simulator/wall-clock-synchronizer.cc Tue Aug 26 15:34:57 2008 -0700
@@ -0,0 +1,490 @@
+/* -*- 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 <time.h>
+#include <sys/time.h>
+#include <sched.h>
+
+#include "ns3/log.h"
+#include "ns3/system-condition.h"
+
+#include "wall-clock-synchronizer.h"
+
+NS_LOG_COMPONENT_DEFINE ("WallClockSynchronizer");
+
+namespace ns3 {
+
+WallClockSynchronizer::WallClockSynchronizer ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// In Linux, the basic timekeeping unit is derived from a variable called HZ
+// HZ is the frequency in hertz of the system timer. The system timer fires
+// every 1/HZ seconds and a counter, called the jiffies counter is incremented
+// at each tick. The time between ticks is called a jiffy (American slang for
+// a short period of time). The ticking of the jiffies counter is how the
+// the kernel tells time.
+//
+// Now, the shortest time the kernel can sleep is one jiffy since a timer
+// has to be set to expire and trigger the process to be made ready. The
+// Posix clock CLOCK_REALTIME is defined as a 1/HZ clock, so by doing a
+// clock_getres () on the realtime clock we can infer the scheduler quantum
+// and the minimimum sleep time for the system. This is most certainly NOT
+// going to be one nanosecond even though clock_nanosleep () pretends it is.
+//
+// The reason this number is important is that we are going to schedule lots
+// of waits for less time than a jiffy. The clock_nanosleep function is
+// going to guarantee that it will sleep for AT LEAST the time specified.
+// The least time that it will sleep is a jiffy.
+//
+// In order to deal with this, we are going to do a spin-wait if the simulator
+// requires a delay less than a jiffy. This is on the order of one millisecond
+// (999848 ns) on the ns-regression machine.
+//
+ struct timespec ts;
+ clock_getres (CLOCK_REALTIME, &ts);
+ m_jiffy = ts.tv_sec * NS_PER_SEC + ts.tv_nsec;
+ NS_LOG_INFO ("Jiffy is " << m_jiffy << " ns");
+
+#if 0
+//
+// DANGER DANGER WILL ROBINSON
+//
+// Don't enable this code, su root and run a sim unless you really know what
+// you are doing.
+//
+ struct sched_param sp;
+ sp.sched_priority = sched_get_priority_max (SCHED_FIFO);
+ sched_setscheduler (0, SCHED_FIFO, &sp);
+#endif
+}
+
+WallClockSynchronizer::~WallClockSynchronizer ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+ bool
+WallClockSynchronizer::DoRealtime (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return true;
+}
+
+ uint64_t
+WallClockSynchronizer::DoGetCurrentRealtime (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return GetNormalizedRealtime ();
+}
+
+ void
+WallClockSynchronizer::DoSetOrigin (uint64_t ns)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// In order to make sure we're really locking the simulation time to some
+// wall-clock time, we need to be able to compare that simulation time to
+// that wall-clock time. The wall clock will have been running for some
+// long time and will probably have a huge count of nanoseconds in it. We
+// save the real time away so we can subtract it from "now" later and get
+// a count of nanoseconds in real time since the simulation started.
+//
+ m_realtimeOriginNano = GetRealtime ();
+ NS_LOG_INFO ("origin = " << m_realtimeOriginNano);
+}
+
+ int64_t
+WallClockSynchronizer::DoGetDrift (uint64_t ns)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// In order to make sure we're really locking the simulation time to some
+// wall-clock time, we need to be able to compare that simulation time to
+// that wall-clock time. In DoSetOrigin we saved the real time at the start
+// of the simulation away. This is the place where we subtract it from "now"
+// to a count of nanoseconds in real time since the simulation started. We
+// then subtract the current real time in normalized nanoseconds we just got
+// from the normalized simulation time in nanoseconds that is passed in as
+// the parameter ns. We return an integer difference, but in reality all of
+// the mechanisms that cause wall-clock to simuator time drift cause events
+// to be late. That means that the wall-clock will be higher than the
+// simulation time and drift will be positive. I would be astonished to
+// see a negative drift, but the possibility is admitted for other
+// implementations; and we'll use the ability to report an early result in
+// DoSynchronize below.
+//
+ uint64_t nsNow = GetNormalizedRealtime ();
+
+ if (nsNow > ns)
+ {
+//
+// Real time (nsNow) is larger/later than the simulator time (ns). We are
+// behind real time and the difference (drift) is positive.
+//
+ return (int64_t)(nsNow - ns);
+ }
+ else
+ {
+//
+// Real time (nsNow) is smaller/earlier than the simulator time (ns). We are
+// ahead of real time and the difference (drift) is negative.
+//
+ return -(int64_t)(ns - nsNow);
+ }
+}
+
+ bool
+WallClockSynchronizer::DoSynchronize (uint64_t nsCurrent, uint64_t nsDelay)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// This is the belly of the beast. We have received two parameters from the
+// simulator proper -- a current simulation time (nsCurrent) and a simulation
+// time to delay which identifies the time the next event is supposed to fire.
+//
+// The first thing we need to do is to (try and) correct for any realtime
+// drift that has happened in the system. In this implementation, we realize
+// that all mechanisms for drift will cause the drift to be such that the
+// realtime is greater than the simulation time. This typically happens when
+// our process is put to sleep for a given time, but actually sleeps for
+// longer. So, what we want to do is to "catch up" to realtime and delay for
+// less time than we are actually asked to delay. DriftCorrect will return a
+// number from 0 to nsDelay corresponding to the amount of catching-up we
+// need to do. If we are more than nsDelay behind, we do not wait at all.
+//
+// Note that it will be impossible to catch up if the amount of drift is
+// cumulatively greater than the amount of delay between events. The method
+// GetDrift () is available to clients of the syncrhonizer to keep track of
+// the cumulative drift. The client can assert if the drift gets out of
+// hand, print warning messages, or just ignore the situation and hope it will
+// go away.
+//
+ uint64_t ns = DriftCorrect (nsCurrent, nsDelay);
+ NS_LOG_INFO ("Synchronize ns = " << ns);
+//
+// Once we've decided on how long we need to delay, we need to split this
+// time into sleep waits and busy waits. The reason for this is described
+// in the comments for the constructor where jiffies and jiffy resolution is
+// explained.
+//
+// Here, I'll just say that we need that the jiffy is the minimum resolution
+// of the system clock. It can only sleep in blocks of time equal to a jiffy.
+// If we want to be more accurate than a jiffy (we do) then we need to sleep
+// for some number of jiffies and then busy wait for any leftover time.
+//
+ uint64_t numberJiffies = ns / m_jiffy;
+ NS_LOG_INFO ("Synchronize numberJiffies = " << numberJiffies);
+//
+// This is where the real world interjects its very ugly head. The code
+// immediately below reflects the fact that a sleep is actually quite probably
+// going to end up sleeping for some number of jiffies longer than you wanted.
+// This is because your system is going to be off doing other unimportant
+// stuff during that extra time like running file systems and networks. What
+// we want to do is to ask the system to sleep enough less than the requested
+// delay so that it comes back early most of the time (coming back early is
+// fine, coming back late is bad). If we can convince the system to come back
+// early (most of the time), then we can busy-wait until the requested
+// completion time actually comes around (most of the time).
+//
+// The tradeoff here is, of course, that the less time we spend sleeping, the
+// more accurately we will sync up; but the more CPU time we will spend busy
+// waiting (doing nothing).
+//
+// I'm not really sure about this number -- a boss of mine once said, "pick
+// a number and it'll be wrong." But this works for now.
+//
+// XXX BUGBUG Hardcoded tunable parameter below.
+//
+ if (numberJiffies > 3)
+ {
+ NS_LOG_INFO ("SleepWait for " << numberJiffies * m_jiffy << " ns");
+ NS_LOG_INFO ("SleepWait until " << nsCurrent + numberJiffies * m_jiffy
+ << " ns");
+//
+// SleepWait is interruptible. If it returns true it meant that the sleep
+// went until the end. If it returns false, it means that the sleep was
+// interrupted by a Signal. In this case, we need to return and let the
+// simulator re-evaluate what to do.
+//
+ if (SleepWait ((numberJiffies - 3) * m_jiffy) == false)
+ {
+ NS_LOG_INFO ("SleepWait interrupted");
+ return false;
+ }
+ }
+ NS_LOG_INFO ("Done with SleepWait");
+//
+// We asked the system to sleep for some number of jiffies, but that doesn't
+// mean we actually did. Let's re-evaluate what we need to do here. Maybe
+// we're already late. Probably the "real" delay time left has little to do
+// with what we would calculate it to be naively.
+//
+// We are now at some Realtime. The important question now is not, "what
+// would we calculate in a mathematicians paradise," it is, "how many
+// nanoseconds do we need to busy-wait until we get to the Realtime that
+// corresponds to nsCurrent + nsDelay (in simulation time). We have a handy
+// function to do just that -- we ask for the time the realtime clock has
+// drifted away from the simulation clock. That's our answer. If the drift
+// is negative, we're early and we need to busy wait for that number of
+// nanoseconds. The place were we want to be is described by the parameters
+// we were passed by the simulator.
+//
+ int64_t nsDrift = DoGetDrift (nsCurrent + nsDelay);
+//
+// If the drift is positive, we are already late and we need to just bail out
+// of here as fast as we can. Return true to indicate that the requested time
+// has, in fact, passed.
+//
+ if (nsDrift >= 0)
+ {
+ NS_LOG_INFO ("Back from SleepWait: IML8 " << nsDrift);
+ return true;
+ }
+//
+// There are some number of nanoseconds left over and we need to wait until
+// the time defined by nsDrift. We'll do a SpinWait since the usual case
+// will be that we are doing this Spinwait after we've gotten a rough delay
+// using the SleepWait above. If SpinWait completes to the end, it will
+// return true; if it is interrupted by a signal it will return false.
+//
+ NS_LOG_INFO ("SpinWait until " << nsCurrent + nsDelay);
+ return SpinWait (nsCurrent + nsDelay);
+}
+
+ void
+WallClockSynchronizer::DoSignal (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+
+ m_condition.SetCondition (true);
+ m_condition.Signal ();
+}
+
+ void
+WallClockSynchronizer::DoSetCondition (bool cond)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_condition.SetCondition (cond);
+}
+
+ void
+WallClockSynchronizer::DoEventStart (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_nsEventStart = GetNormalizedRealtime ();
+}
+
+ uint64_t
+WallClockSynchronizer::DoEventEnd (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return GetNormalizedRealtime () - m_nsEventStart;
+}
+
+ bool
+WallClockSynchronizer::SpinWait (uint64_t ns)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// Do a busy-wait until the normalized realtime equals the value passed in
+// or the condition variable becomes true. The condition becomes true if
+// an outside entity (a network device receives a packet, sets the condition
+// and signals the scheduler it needs to re-evaluate).
+//
+// We just sit here and spin, wasting CPU cycles until we get to the right
+// time or are told to leave.
+//
+ for (;;)
+ {
+ if (GetNormalizedRealtime () >= ns)
+ {
+ return true;
+ }
+ if (m_condition.GetCondition ())
+ {
+ return false;
+ }
+ }
+// Quiet compiler
+ return true;
+}
+
+ bool
+WallClockSynchronizer::SleepWait (uint64_t ns)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// Put our process to sleep for some number of nanoseconds. Typically this
+// will be some time equal to an integral number of jiffies. We will usually
+// follow a call to SleepWait with a call to SpinWait to get the kind of
+// accuracy we want.
+//
+// We have to have some mechanism to wake up this sleep in case an external
+// event happens that causes a schedule event in the simulator. This newly
+// scheduled event might be before the time we are waiting until, so we have
+// to break out of both the SleepWait and the following SpinWait to go back
+// and reschedule/resynchronize taking the new event into account. The
+// SystemCondition we have saved in m_condition takes care of this for us.
+//
+// This call will return if the timeout expires OR if the condition is
+// set true by a call to WallClockSynchronizer::SetCondition (true) followed
+// by a call to WallClockSynchronizer::Signal(). In either case, we are done
+// waiting. If the timeout happened, we TimedWait returns true; if a Signal
+// happened, false.
+//
+ return m_condition.TimedWait (ns);
+}
+
+ uint64_t
+WallClockSynchronizer::DriftCorrect (uint64_t nsNow, uint64_t nsDelay)
+{
+ int64_t drift = DoGetDrift (nsNow);
+//
+// If we're running late, drift will be positive and we need to correct by
+// delaying for less time. If we're early for some bizarre reason, we don't
+// do anything since we'll almost instantly self-correct.
+//
+ if (drift < 0)
+ {
+ return nsDelay;
+ }
+//
+// If we've drifted out of sync by less than the requested delay, then just
+// subtract the drift from the delay and fix up the drift in one go. If we
+// have more drift than delay, then we just play catch up as fast as possible
+// by not delaying at all.
+//
+ uint64_t correction = (uint64_t)drift;
+ if (correction <= nsDelay)
+ {
+ return nsDelay - correction;
+ }
+ else
+ {
+ return 0;
+ }
+}
+
+ uint64_t
+WallClockSynchronizer::GetRealtime (void)
+{
+//
+// I originally wrote this code to use CLOCK_PROCESS_CPUTIME_ID. In Linux
+// this is a highly accurate realtime clock. It turns out, though, that this
+// is a Linux bug. This is supposed to be (posix says it is) a highly
+// accurate cumulative running time of the process. In Linux it is (or at
+// least was -- a bug is filed) a highly accurate wall-clock time since the
+// process was created. Posix defines the wall clock you must use as the
+// CLOCK_REALTIME clock. As you can see in the constructor, the resolution
+// of the CLOCK_REALTIME clock is a jiffy. This is not fine-grained enough
+// for us. So, I'm using the gettimeofday clock even though it is an
+// expensive call.
+//
+// I could write some inline assembler here to get to the timestamp counter
+// (RDTSC instruction). It's not as trivial as it sounds to get right.
+// Google for "rdtsc cpuid" to see why. I'm leaving this for another day.
+//
+// N.B. This returns the value of the realtime clock. This does not return
+// the current normalized realtime that we are attempting to make equal to
+// the simulation clock. To get that number, use GetNormalizedRealtime ().
+//
+
+#if 0
+ // This will eventually stop working in linux so don't use it
+ struct timespec tsNow;
+ clock_gettime (CLOCK_REALTIME, &tsNow);
+ return TimespecToNs (&tsNow);
+#endif
+
+ struct timeval tvNow;
+ gettimeofday (&tvNow, NULL);
+ return TimevalToNs (&tvNow);
+}
+
+ uint64_t
+WallClockSynchronizer::GetNormalizedRealtime (void)
+{
+ return GetRealtime () - m_realtimeOriginNano;
+}
+
+ void
+WallClockSynchronizer::NsToTimespec (int64_t ns, struct timespec *ts)
+{
+ NS_ASSERT ((ns % US_PER_NS) == 0);
+ ts->tv_sec = ns / NS_PER_SEC;
+ ts->tv_nsec = ns % NS_PER_SEC;
+}
+
+ void
+WallClockSynchronizer::NsToTimeval (int64_t ns, struct timeval *tv)
+{
+ NS_ASSERT ((ns % US_PER_NS) == 0);
+ tv->tv_sec = ns / NS_PER_SEC;
+ tv->tv_usec = (ns % NS_PER_SEC) / US_PER_NS;
+}
+
+ uint64_t
+WallClockSynchronizer::TimespecToNs (struct timespec *ts)
+{
+ uint64_t nsResult = ts->tv_sec * NS_PER_SEC + ts->tv_nsec;
+ NS_ASSERT ((nsResult % US_PER_NS) == 0);
+ return nsResult;
+}
+
+ uint64_t
+WallClockSynchronizer::TimevalToNs (struct timeval *tv)
+{
+ uint64_t nsResult = tv->tv_sec * NS_PER_SEC + tv->tv_usec * US_PER_NS;
+ NS_ASSERT ((nsResult % US_PER_NS) == 0);
+ return nsResult;
+}
+
+ void
+WallClockSynchronizer::TimespecAdd (
+ struct timespec *ts1,
+ struct timespec *ts2,
+ struct timespec *result)
+{
+ result->tv_sec = ts1->tv_sec + ts2->tv_sec;
+ result->tv_nsec = ts1->tv_nsec + ts2->tv_nsec;
+ if (result->tv_nsec > (int64_t)NS_PER_SEC)
+ {
+ ++result->tv_sec;
+ result->tv_nsec %= NS_PER_SEC;
+ }
+}
+
+ void
+WallClockSynchronizer::TimevalAdd (
+ struct timeval *tv1,
+ struct timeval *tv2,
+ struct timeval *result)
+{
+ result->tv_sec = tv1->tv_sec + tv2->tv_sec;
+ result->tv_usec = tv1->tv_usec + tv2->tv_usec;
+ if (result->tv_usec > (int64_t)US_PER_SEC)
+ {
+ ++result->tv_sec;
+ result->tv_usec %= US_PER_SEC;
+ }
+}
+
+}; // namespace ns3
+
+