2008-10-13:

Brakująca funkcja gettimeofday i race condition

c:c++:race condition:windows:easy:winapi
Dzisiaj będzie post wyrwany z kontekstu. Post będzie dotyczył funkcji gettimeofday na Windowsie, a raczej jej braku.

Z pewnym moim przyjacielem portujemy pewną aplikację m.in. na system z rodziny Windows. Aplikacja była pisana już jakiś czas temu, i korzysta z w/w funkcji - gettimeofday - do odczytu czasu. Ponieważ jest to nowa funkcja ze stosunkowo nowego standardu IEEE Std 1003.1:2001 (POSIX), to jej implementacja nie znalazła się w Microsoft C Runtime Library aka msvcrt.dll, ani w żadnej innej bibliotece systemu Windows która wpadła w moje ręce podczas poszukiwań. W związku z czym powstała potrzeba jej zaimplementowania (skorzystanie z gotowej implementacji odrzuciliśmy - czytanie licencji trwało by dłużej niż pisanie nowej funkcji).

Kilka słów na temat funkcji gettimeofday. Zacznijmy od prototypu:

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

Jak widać wyżej, gettimeofday przyjmuje dwie struktury które wypełnia (nie ma const przy pointerach, stąd wniosek że struktury są wypełniane). Zacznijmy od drugiej struktury - jak można przeczytać w man'ie, jest to struktura nieużywana (noo przynajmniej pod Linuxem, ale w portowanym projekcie zakładamy że również jest nieużywana) ;>

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.


Jeden struct z głowy, został struct timeval, który jest standardowym (w bardzo wąskim znaczeniu tego słowa) structem definiowanym na kilka sposobów:

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;
};


Komentarze w pierwszym strukcie wyjaśniają sporo, ale żeby było to jasne i oczywiste dla wszystkich, ponownie to napiszę. Struct ma dwa pola, pierwsze - tv_sec - zawiera Unix Time Stamp, a drugie - tv_usec - zawiera mikrosekundy (10E-6), czyli ma na celu zwiększenie precyzji struktury opisującej moment na osi czasu (wartości przyjmuje od 0 do 999999).

Wracając do funkcji, wystarczy więc wypełnić jakoś oba pola. Żeby jeszcze ułatwić, zakładam że wystarczy nam dokładność na poziomie milisekund (10E-3). Pole tv_sec można oczywiście wypełnić wywołując funkcję time(NULL) która zwraca dokładnie to co potrzeba, czyli Unix Time Stamp. Co do tv_usec, to do wyboru jest kilka funkcji. Osobiście wybrałem GetLocalTime z WinAPI, która wypełnia strukturę SYSTEMTIME, w której między innymi są pola wMilliseconds zawierające milisekundy (od rozpoczęcia ostatniej pełnej sekundy lokalnego czasu ;>), oraz wSeconds (ilość sekund w danej minucie). Przykładowy kod wygląda więc tak:

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;
}


Nyom. I implementacja gotowa. To tyle na dzisiaj, do zobaczenia ;>

Hee? ^_-; A co z tym race condition o który pisałeś w tytule ???

Hyhy żartuje, jeszcze nie koniec. Dopiero dotarliśmy do najciekawszego.

Z implementacją na pierwszy rzut jest wszystko OK. Pobierane są sekundy, następnie są wrzucane w strukta, potem pobierane są milisekundy i wrzucane w strukta, i tyle. Niemniej jednak jest pewien złośliwy przypadek który sprawia że gdy pobierzemy czas w dwóch momentach, A oraz B, to różnica B - A będzie ujemna (mimo że B następuje wyraźnie PO A).
Przypadek ten występuje w momencie gdy wywołanie time(NULL) następuje w ostatniej "chwili" danej sekundy, np. gdy pozostaje jedna nanosekunda do końca danej sekundy (np. obecna sekunda to 10.999999999999999), a wywołanie do GetLocalTime następuje kilka nanosekund później, gdy sekundy już się "przekręcą" na następne, a miliseundy wyzerują (czyli 11.0, niemniej jednak sekundy już są wypełnione, więc w strukcie zostanie 10.0 zamiast 11.0 - następuje powrót do przeszłości ;>). Możemy to sprawdzić uruchamiając następujący kod:

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;
}


Kompilacja i uruchomienie:

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

22:38:41 gynvael >a
1223930327.999000
1223930327.0

22:38:48 gynvael >


Jak widać po 8 sekundach działania zdarzył się przypadek "wyzerowania" milisekund między wywołaniami dwóch funkcji do pobierania czasu.
Należy zatem jakoś rozwiązać ten problem. Ignorując na chwilę sekundy przestępne możemy to zrobić w bardzo prosty sposób - sprawdzić czy ostatnia cyfra dziesiętna sekund tv_sec oraz wSecond się zgadza. Jeżeli nie, to nastąpiło "wyzerowanie", i należy dodać do tv_sec jedną sekundę.
Ostateczny kod funkcji wygląda tak:

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;
}


Nie jest to oczywiście najlepsze z możliwych rozwiązań, jednak jest stosunkowo szybkie (najlepsze było by załatwienie obu pól strukta jednym wywołaniem, ale wtedy nie było by o czym napisać posta ;>).
Zapraszam do wrzucania swoich propozycji rozwiązania problemu do komentarzy =^^=

OK, tym razem na prawdę koniec posta. Dziękuje za uwagę ;>

PS. gratz dla IceWalla za obejście mojego systemu "captcha" =^^= jak będę miał chwilę zrobię level drugi =^^=

Comments:

2008-10-13 14:01:21 = kapitan_hak
{
Nyom, nareszcie jakaś notka ;). Ja jakoś nie potrzebowałem nigdy tej funkcji. Czy race condition ma jakieś znaczenie przy bezpieczeństwie?
}
2008-10-13 14:21:33 = Gynvael Coldwind
{
Często ma ;> Mój ulubiony przykład to race condition w PHP sprzed 2ch lat (symlink vs open base dir restriction):
http://www.securityfocus.com/archive/1/447649

Co do bezpieczeństw w przypadku tematu posta, to akurat żaden "bypass" mi nie przychodzi do głowy. Natomiast stabilność aplikacji to inna sprawa. Rozważmy przypadek błędnej implementacji funkcji w aplikacji która co 100 milisekund musi jakąś akcję wykonywać - np. chłodzić reaktor atomowy (przykład z bajki wzięty), i jeżeli powiedzmy przez 150 milisekund nie będzie chłodzenia, to będzie Чернобыль 2. No i sobie program chodzący chodzi w pętli, sprawdza czy od ostatniego momentu upłynęło >= 100 mili sekund, jeśli tak to chłodzi, i zapisuje obecny czas. A tu nagle dochodzimy do przypadku że od ostatniego razu upłynęło -999 milisekund. I teraz może się albo coś stać (np. program może zasnąć na 50 milisekund bo stwierdzi że ma sporo czasu i nie ma co CPU marnować, albo może zamiast long być użyty unsigned long, więc z -999 by się zrobiło 4294966297 milisekund, więc program zaczął by panikować że przez 49 dni nie chłodził, i zużył by cały zbiornik chłodziwa od razu po czym by nie miał czy chłodzić, i bum ;D). Oczywiście to przykład kapkę na siłę, niemniej jednak może komuś coś zilustrować ;>
}
2008-10-13 14:25:44 = kapitan_hak
{
Zrozumiałem ideę, ale z reaktorem przykład to naprawde na siłę ;). W przypadku takich urządzeń stosuje się "troche" bezpieczniejsze metody. ;)
}
2008-10-13 14:26:43 = Gynvael Coldwind
{
Wiem wiem, ale co to za przykład który nie robi BOOOM na końcu ? ;D
}

Add a comment:

Nick:
URL (optional):
Math captcha: 8 ∗ 2 + 10 =