2008-10-15:

Missing gettimeofday function and a race condition

c:c++:race condition:windows:easy:winapi
Todays post will be an out of order one, and it will be dedicated to the function gettimeofday on the Windows system, or to be precise, the lack of this function.

With my friend we are working on porting some application to, inter alia, the Windows systems. The application was written some time ago, and it's using the previously mentioned gettimeofday function to read time (surprise). The function is not present in the ANSI standard, and it was just recently drawn into the IEEE Std 1003.1:2001 (POSIX) standard, so, as one may expect, it not present in the Microsoft C Runtime Library (aka msvcrt.dll), or any other standard Windows library that I have seen while searching for the function. Hence the need to implement it (we didn't won't to use any existing implementation, since reading the license would take more time then writing the function).

And now, a few short (well, not really short) words about the gettimeofday function. First, the prototype:

int gettimeofday(struct timeval *tp, struct timezone *tpz);

As one can see, gettimeofday takes two structures (pointer to ofc) which are filled by the function (there is no const before the variable type, so the function probably changes the structured data that it receives pointers to). Let's start with the second structure - as it's written in the man, it's not used (well, at least under Linux, but never mind that) ;>

The  use  of  the timezone struct is obsolete: the tz_dsttime field has
never been used under Linux; it has not been and will not be  supported
by  libc or glibc.  Each and every occurrence of this field in the ker-
nel source (other than the declaration) is a bug. Thus,  the  following
is purely of historic interest.


So one struct less to worry about, and only struct timeval is left on the battlefield. It's a standard (in a very narrow meaning of the word) struct that has two fields, which are of course defined in a few different ways:

Linux Programmer's Manual:
struct timeval {
 time_t      tv_sec;   /* seconds */
 suseconds_t tv_usec;  /* microseconds */
};


MinGW sys/time.h:
struct timeval {
 long tv_sec;
 long tv_usec;
};


The comments in the quote from the manual explain everything, but since I want to make sure it's obvious to everybody, I'll write it again - the struct has two fields, the first one - tv_sec - contains a Unix Time Stamp, while the second one - tv_usec - contains microseconds (10E-6, it contains values from 0 to 999999). The second field is used to rise the precession of the time information contained in the structure.

Back to the function. As one can see, all that needs to be done is filling both fields. To makes things even simpler, I'll assume that the precession of the second field can be on the miliseconds level (10E-3).
So, to fill the first field, a call to the time(NULL) function is sufficient (since it returns a time stamp). As for the field tv_usec, there are few possible choices. Personally I've chosen GetLocalTime from WinAPI, which fills a SYSTEMTIME structure, which contains, inter alia, fields wMilliseconds and wSeconds (it's the seconds from the start of this minute, not a unix time stamp).

An example implementation of gettimeofday looks like this:

int
gettimeofday (struct timeval *tp, struct timezone *tzp)
{
 SYSTEMTIME st;

 /* timezone is obsolute according to UNIX man pages */
 (void) tzp;

 /* Set time */
 tp->tv_sec = (long) time (NULL);

 /* Get time info from the system */
 GetLocalTime (&st);
 tp->tv_usec = (long) st.wMilliseconds * 1000;
 
 /* return success, nothing there to fail */
 return 0;
}


Yep, and the function is ready. Thats all for today, see you later ;>

Whaaa? ^_-; What about the race condition you've written about in the title ???

Hehe, just joking. We just got to the most interesting part.

The function implementation is OK at the first sight. The seconds are received in the first call, inserted into the struct, then the second call acquires the miliseconds, and also inserts them into the structure. However, there is one evil case, in which the distance between two time points, A and B (B happens after A) is negative (B-A < 0). This happens when the call to time(NULL) function takes place in the last "moment" of a second (for example, one nanosecond is left to the end of the second), and the call to GetLocalTime takes place when the second counter already increments. In that case, the miliseconds are set to 0 (or something around 0), while the second field is still set to the previous second (so the first call to gettimeofday may return 10.998, but the next one might return 10.001).
Let's make this happen:

int
main (void)
{
 struct timezone tzp;
 static struct timeval tp[2];

 int i = 0, j;

 while (1)
 {
   gettimeofday (&tp[i], &tzp);
   j = !i;

   /* until the future is in the past */
   if(tp[i].tv_sec == tp[j].tv_sec && tp[i].tv_usec < tp[j].tv_usec)
      break;

   i = j;
 }

 printf ("%u.%u\n", tp[j].tv_sec, tp[j].tv_usec);
 printf ("%u.%u\n", tp[i].tv_sec, tp[i].tv_usec);

 return 0;
}


Compile and run:

22:38:04 gynvael >gcc gettime.c -DRACE_CONDITION_TEST

22:38:41 gynvael >a
1223930327.999000
1223930327.0

22:38:48 gynvael >


As one can see, after 8 seconds of execution, the 'evil case' took place.

This problem has to be solved in some way. Let's ignore the leap seconds for a moment, and do it in a very simple way - let's check if the last decimal digit of the seconds returned by time() and GetLocalTime() is the same - if not, and the 'incrementation' took place, and we have to increment our seconds too.

The final code looks like this:

int
gettimeofday (struct timeval *tp, struct timezone *tzp)
{
 SYSTEMTIME st;

 /* timezone is obsolute according to UNIX man pages */
 (void) tzp;

 /* Set time */
 tp->tv_sec = (long) time (NULL);

 /* Get time info from the system */
 GetLocalTime (&st);
 tp->tv_usec = (long) st.wMilliseconds * 1000;

 /* Anti race condition sec fix
  * When the milliseconds are at 999 at the time of call to time(), and at
  * 999+1 = 0 at the time of the GetLocalTime call, then the tv_sec and
  * tv_usec would be set to one second in the past. To correct this, just
  * check if the last decimal digit of the seconds match, and if not, add
  * a second to the tv_sec.
  */
 if (tp->tv_sec % 10 != st.wSecond % 10)
   tp->tv_sec++;
 
 /* return success, nothing there to fail */
 return 0;
}


It may not be the best method to solve this problem, however it's quite fast (well, the best method would be to use some other function to get both fields filled, but then again, I wouldn't have anything to write about ;>)

I encourage the readers to think about a solution, and leave a comment about the stupidity of my solution =^^=

OK, this time it's the end for real. Thank for reading and c u next time ;>

PS. congratz for IceWall for bypassing my "captcha" system =^^= I'll make a 'second level captcha' when I have some time =^^=

Comments:

2008-10-16 05:55:15 = asf
{
GetLocalTime>SystemTimeToFileTime>ULONGLONG, you now have the current time since whatever windows uses in 64 bit, add/remove by whatever number you need to get to unix time
}
2008-10-16 06:31:59 = Gynvael Coldwind
{
@asf
Thank You for your comment ;>

Yes, it's a good idea, however one thing bothers me.
The GetLocalTime is implemented by taking a LARGE INT from a system structure (something with VA 7FFE0014h-7FFE001Ch under XP SP2), and then, it calls RtlTimeToTimeFields to split the LARGE INT time to a structure.
Then, we should (as u suggest) call the SystemTimeToFileTime, to sum up the time again, and aquire a LARGE INT split into two DWORDS, which, before usage, have to be merged into a LARGE INT once again.
So basically, we have spliting the time, and then merging it again (it would give me an optimisation hangover ;p).

However, your idea is good, but we should search for a function that just retunrs that LARGE INT acquired from the system with as minimum spliting as possible.

One of such functions is GetSystemTimeAsFileTime (I don't see a 'GetLocalTimeAs...' funciton), however the 2xDWORD->LARGEINT merge still has to take place (via MSDN, on 32-bit system it's not a problem, since a simple cast would do; however, on 64-bit systems, the align messes everything, and it takes few more things then a simple cast to do it).

I couldn't locate any procedure that would let you acquire the time as LARGE INT.

Btw "since whatever" = "since January 1, 1601" (why 1601 ? I'm sure there's a story behind this).
}
2008-10-16 06:42:36 = asf
{
CRT for VC6 uses a helper function: time_t __loctotime_t(yr, mo, dy, hr, mn, sc, dstflag) and does all the calculations by hand, dealing with leapdays/seconds and other junk on its own, I don't see why doing it that way is any better
}
2008-10-16 07:05:13 = Gynvael Coldwind
{
Hmm, I've checked out the VC7 implementation of the __loctotime_t function, but I don't see any leapseconds handling. Neverming that.

"I don't see why doing it that way is any better" - which way are you refering to ?
}
2008-10-16 08:16:41 = asf
{
Any other way pretty much. You can use SystemTimeToFileTime, if not, then you have to call time(0) or get to the time_t from SYSTEMTIME on your own, either way you are just doing it on your own (or with the CRT) instead of using the stuff in windows. ( Too bad there is no documented and/or undocumented "GetMillisecSince1601()" (AFAIK))
}

Add a comment:

Nick:
URL (optional):
Math captcha: 9 ∗ 5 + 7 =