Of Mutexes and Nodeunits

Last week I expressed an interest with converting the WebVTT tests we had for our implementation of WebVTT into unit tests for WebKit to test WebKit’s implementation as well as our own tests. Unfortunately this idea was abandoned as our professor decided against it, citing the amount of time it had taken to simply build WebKit. Thus the first few days of working towards release 0.3 were spent trying to find a way to meaningfully to add to WebVTT in time for our 0.3 release deadline of Nov. 15.

The first thing I decided I might take a stab at was adding thread safety to our implementation of WebVTT. Since I had no experience with multi-threading before I spent a bit of time familiarizing myself with multi-threading before thinking about ways to lock threads. To do this I started by attempting to understand the following program developed for C in Linux:
(slightly modified from an example located here)

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void *functionC();
void *functionD();
int  counter = 0;

main()
{
   int rc1, rc2;
   pthread_t thread1, thread2;

   /* Create independent threads each of which will execute functionC */

   if( (rc1=pthread_create( &thread1, NULL, &functionC, NULL)) )
   {
      printf("Thread creation failed: %d\n", rc1);
   }

   if( (rc2=pthread_create( &thread2, NULL, &functionD, NULL)) )
   {
      printf("Thread creation failed: %d\n", rc2);
   }

   /* Wait till threads are complete before main continues. Unless we  */
   /* wait we run the risk of executing an exit which will terminate   */
   /* the process and all threads before the threads have completed.   */

   pthread_join( thread1, NULL);
   pthread_join( thread2, NULL);

   exit(0);
}

void *functionC()
{
   int i = 0;
   for(i = 0; i < 100; i++){
      counter++;
      printf("%d\n", counter);
   }
   printf("Counter value: %d\n",counter);
}

void *functionD()
{
   int i = 0;
   for(i = 0; i < 10; i++){
      counter*=2;
      printf("%d\n", counter);
   }
   printf("Counter value: %d\n",counter);
}

This code is a classic example of thread safety and the need to ensure processes are properly locked for thread-safety. The above code will generate a random result every time as threads access the global counter variable in mid-execution of each function. One way to fix this is to create a mutex and prevent access to the counter variable while it is being used like below:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void *functionC();
void *functionD();
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
int  counter = 0;

main()
{
   int rc1, rc2;
   pthread_t thread1, thread2;

   /* Create independent threads each of which will execute functionC */

   if( (rc1=pthread_create( &thread1, NULL, &functionC, NULL)) )
   {
      printf("Thread creation failed: %d\n", rc1);
   }

   if( (rc2=pthread_create( &thread2, NULL, &functionD, NULL)) )
   {
      printf("Thread creation failed: %d\n", rc2);
   }

   /* Wait till threads are complete before main continues. Unless we  */
   /* wait we run the risk of executing an exit which will terminate   */
   /* the process and all threads before the threads have completed.   */

   pthread_join( thread1, NULL);
   pthread_join( thread2, NULL);

   exit(0);
}

void *functionC()
{
   int i = 0;

   pthread_mutex_lock( &mutex1 );
   for(i = 0; i < 100; i++){
      counter++;
      printf("%d\n", counter);
   }
   printf("Counter value: %d\n",counter);
   pthread_mutex_unlock( &mutex1 );
}

void *functionD()
{
   int i = 0;
   pthread_mutex_lock( &mutex1 );
   for(i = 0; i < 10; i++){
      counter*=2;
      printf("%d\n", counter);
   }
   printf("Counter value: %d\n",counter);
   pthread_mutex_unlock( &mutex1 );
}

A mutex lock allows only one thread the ability to lock it at a time. This means that the first thread to lock it will block others from locking the same mutex at a time. Note however, that this lock has no bearing on WHICH thread gains access first, so while it is predictable that the first thread to lock the mutex will run the for loop to completion, there is still a factor of randomness based on how the OS’ scheduler decides which thread should execute first.

This implementation of the mutex requires the pthread.h library be present on the system for compilation. This library is known to be present on Linux OSes and through research I have seen that it is present on Mac OSX systems as well. However, it is not present on Windows systems (and I have not read about its presence on earlier versions of the Mac OS). This leaves two ways to add mutexes to Windows. Either use the Windows implementation or find a pthread library useable by Windows. In order to help with the decision of this I decided to try seeing if it was possible to convert the above code into something that would work in Windows. After some tinkering I ended up with the following as a rough equivalent to the above Linux implementation:

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

void *functionC();
void *functionD();
HANDLE hMutex;
int  counter = 0;

main()
{
   HANDLE thread[2];
   DWORD thread_id;

   hMutex = CreateMutex( NULL, FALSE, NULL );

   /* Create independent threads each of which will execute functionC */

   if( NULL == (thread[0] = CreateThread( 0, 0, (LPTHREAD_START_ROUTINE)functionC, NULL, NULL, &thread_id)) )
   {
      printf("Thread creation failed \n");
   }

   if( NULL == (thread[1] = CreateThread( 0, 0, (LPTHREAD_START_ROUTINE)functionD, NULL, NULL, &thread_id)) )
   {
      printf("Thread creation failed \n");
   }

   /* Wait till threads are complete before main continues. Unless we  */
   /* wait we run the risk of executing an exit which will terminate   */
   /* the process and all threads before the threads have completed.   */

   WaitForMultipleObjects(2, thread, TRUE, INFINITE);

   exit(0);
}

void *functionC()
{
  int i;
  WaitForSingleObject( hMutex, INFINITE );
  for (i = 0; i < 100; i++){
   counter++;
   printf("Counter value: %d; %d\n", i, counter);
  }
  ReleaseMutex( hMutex );
}

void *functionD()
{
  int i;
  WaitForSingleObject( hMutex, INFINITE );
  for (i = 0; i < 10; i++){
   counter *= 2;
   printf("Counter value: %d; %d\n", i, counter);
  }
  ReleaseMutex( hMutex );
}

This Windows implementation is almost the same in structure as the Linux implementation with one key difference. The Windows HANDLE variable that stores the mutex must be initialized in the main function whereas the Linux pthread_mutex_t variable that stores the mutex can be initialized in or outside of the windows main function. Taking the above into account one possible way to implement a mutex lock working in both systems could use macros like below:

#if ( defined(_WIN32) )
#include <windows.h>
#define CREATE_MUTEX HANDLE mutex;
#define INIT_MUTEX mutex = CreateMutex(NULL, FALSE, NULL);
#define MUTEX_LOCK WaitForSingleObject( mutex, INFINITE );
#define MUTEX_UNLOCK ReleaseMutex( mutex );
#else
#include <pthread.h>
#define CREATE_MUTEX pthread_mutex_t mutex;
#define INIT_MUTEX pthread_mutex_init(&mutex, NULL);
#define MUTEX_LOCK pthread_mutex_lock(&mutex);
#define MUTEX_UNLOCK pthread_mutex_unlock( &mutex );
#endif

Which would make one of the modified functions look like:

void *functionD()
{
  int i;
  MUTEX_LOCK
  for (i = 0; i < 10; i++){
   counter *= 2;
   printf("Counter value: %d; %d\n", i, counter);
  }
  MUTEX_UNLOCK
}

Of course this is only one of the ways to make a library thread safe. The other possibilities include using a semaphore (allowing a set number of threads access to a locked variable) or making code re-entrant (refactoring the code so that it can be interrupted before completion). However based on the way the issue is worded on GitHub (research indicates that thread safety for memory allocation functions typically suggests a mutex-type lock) this seemed like the kind of action that was being requested.

Edit: Actually in hindsight I have realized that this is probably not a good way to implement it in alloc as it would require the passing of a mutex in addition to the address, which while technically doable probably isn’t the way that it should be done. I will likely try to study an implementation to see how it can be done without using a mutex.

The second thing I decided to do was prepare for the coming need of unit tests by introducing myself to Nodeunit. I decided to try installing it on both the Virtual Boxes I was using for WebKit earlier as well as on Windows. Ironically enough, I discovered that it was simplest to install it on Windows as following the provided instructions directly yielded a working installation immediately. Fedora is outright unsupported by node.js due to its official library not supporting the required version of Chromium’s v8 engine and Ubuntu already has a package named node which is used for something else. While this doesn’t directly affect the installation of nodejs, it means that either some tweaking is required or a legacy version of nodejs needs to be installed before Nodeunit can work with Ubuntu (nodeunit assumes ‘node’ as the calling program rather than ‘nodejs’). Regardless, doing the tutorial on both Ubuntu and Windows yielded the same result. I hope that by doing the tutorial and learning nodeunit early will allow me to work on nodeunit tests much faster.

Moving forward I hope to see whether the WebKit unit tests can apply to ours, and to convert the ones I made previously into unit tests for the upcoming nodeunit implementation.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s