[Kos-dev] Race condition 2

[Thomas Petazzoni]

This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enig6CA95CE9805F365CE1D6508A
Content-Type: multipart/mixed;
 boundary="------------080202000007010402090800"

This is a multi-part message in MIME format.
--------------080202000007010402090800
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit

Bonjour,

Je pense avoir trouvé d'ou vient le problème de race condition dans
l'implémentation des sémaphores : lors du codage avec David, on avait
déjà pensé qu'il pouvait y avoir un problème potentiel.

Extrait de kitc/_ksem.c :

 /********* Fonction ksem_up **********/
 /* Le lock 'global_semaphore_lock' est pris */
  sem->value++;

  if(sem->value <= 0)
    kwaitqueue_wake_up(& sem->wq, NULL, NULL);
 /* Le lock 'global_semaphore_lock' est relache */

 /************* Fonction ksem_down ************/
 /* Le lock 'global_semaphore_lock' est pris */
  sem->value--;

  if (sem->value < 0)
    {
      write_spin_unlock(global_semaphore_lock, flags);
      kwaitqueue_add_waiting(& sem->wq, NULL, NULL);
    }

Dans ksem_down, on relache le lock, parce que kwaitqueue_add_waiting
peut être bloquant. Mais, si on est interrompu entre le moment ou on
relache le lock, et le moment ou effectivement le thread est ajouté dans
la waitqueue, il y a un probléme.

Scénario :

Soit semaphore, de valeur 0.
Le thread A éxécute ksem_down, la valeur passe à -1, et on rentre dans
le test if(sem->value < 0), puis on relache le lock. A ce moment précis
=> bing interruption.
Le thread B éxécute ksem_up (sur la même sémaphore), la valeur de la
sémaphore est donc -1, on l'incrémente, et on passe à 0. ON rentre donc
dans le test if(sem->value <= 0) qui va réveiller un thread, alors que
le thread A n'est pas encore dans la liste.

Reproduction :

Le fichier joint contient de quoi reproduire le bug. En gros, le
principe du test est de créer TEST_NB_PRODUCTER_PER_SEMAPHORE threads
"producteur" (qui font des Up) et TEST_NB_CONSUMER_PER_SEMAPHORE (avec
TEST_NB_PRODUCTER_PER_SEMAPHORE == TEST_NB_CONSUMER_PER_SEMAPHORE)
threads "consommateur". Chaque thread fait TEST_DURATION boucles sur
ksem_down ou ksem_up. Comme le nombre de consommateurs est égal au
nombre de producteurs, à la fin du test, tous les threads devraient se
terminer. Malheureusement, j'ai un compteur des threads, qui vaut 0
quand ils sont tous terminés, et pour un certain nombre de threads,
quelques threads consommateurs ne se terminent pas, ce qui veut dire que
certains ksem_up ont été squizzés, ce qui semble rejoindre l'hypothèse
de race condition explicitée plus haut.
Le tableau nb_reception permet de savoir combien de ksem_down ont
réussi, et effectivement on s'aperçoit que pour certains threads, la
valeur n'est pas arrivée à TEST_DURATION.

Les valeurs fournies ne permettront peut être pas de reproduire le bug
chez vous, il faut donc les augmenter un peu si besoin est, mais une
fois que le bug est reproduit une fois, il est toujours identique, sauf
si évidemment le reste de l'OS est modifié.

Solution possible :

La solution possible avait été proposée par David, et consisterait à
filer le lock à kwaitqueue_add_waiting pour qu'il le relache au moment
opportun, et seulement à ce moment.

Thomas
-- 
PETAZZONI Thomas - thomas.petazzoni@enix.org - UIN : 34937744
http://www.enix.org/~thomas/
KOS: http://kos.enix.org/ - Lolut: http://lolut.utbm.info
Fingerprint : 0BE1 4CF3 CEA4 AC9D CC6E  1624 F653 CB30 98D3 F7A7

--------------080202000007010402090800
Content-Type: text/x-csrc;
 name="sem_test.c"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="sem_test.c"

/*
 * Copyright (C) 2000, Thomas Petazzoni
 * http://kos.enix.org
 *
 * Semaphore function test.
 *
 * @(#) $Id$
 */

#include <scheduler/scheduler.h>
#include <kitc/ksem.h>
#include <debug/debug.h>
#include <kmem/kmem.h>
#include <task/task.h>
#include <test/_test.h>

#define TEST_NB_SEMAPHORE               1
#define TEST_NB_CONSUMER_PER_SEMAPHORE  20
#define TEST_NB_PRODUCER_PER_SEMAPHORE  TEST_NB_CONSUMER_PER_SEMAPHORE
#define TEST_DURATION                   10

static uint thread_count = 0;

struct args 
{
  ksem_t *sem;
  int id;
};

int nb_reception[TEST_NB_CONSUMER_PER_SEMAPHORE];

static void sem_consumer(void *data)
{
  int i,j;
  struct args *args = (struct args *) data;
  ksem_t *sem = args->sem;

  nb_reception[args->id] = 0;

  for (i = 0; i < TEST_DURATION; i++)
    {
      ksem_down(sem);
      for (j = 0; j < 100; j++)
	j++; j--;

      nb_reception[args->id]++;
    }

  thread_count --;
  //  __dbg_printk("Ended consumer (thread=%d)", args->id);
}

static void sem_producer(void *data)
{
  int i;
  ksem_t *sem = (ksem_t *) data;

  for (i = 0; i < TEST_DURATION; i++)
    {
      ksem_up(sem);
      usleep(1000000);
    }

  thread_count --;
}

result_t sem_test()
{
  int i, j;
  result_t result;
  
  for (i = 0; i < TEST_NB_SEMAPHORE; i++)
    {
      struct ksem * ksem = kmalloc(sizeof(struct ksem));

      if(ksem == NULL)
	return -ENOMEM;

      result = ksem_init(ksem, 1);
      if(result < 0)
	return result;

      for (j = 0; j < TEST_NB_CONSUMER_PER_SEMAPHORE; j++)
	{
	  struct args * args = kmalloc(sizeof(struct args));

	  if(args == NULL)
	    return -ENOMEM;

	  args->sem = ksem;
	  args->id  = j;

	  __dbg_printk("Creating thread %d\n", j);
	  create_kernel_thread(NULL, sem_consumer, (void *) args);
	  thread_count++;
	}

      for (j = 0; j < TEST_NB_PRODUCER_PER_SEMAPHORE; j++)
	{
	  create_kernel_thread(NULL, sem_producer, (void *) ksem);
	  thread_count++;
	}
    }

  while(thread_count != 0)
    {
      usleep(10000000);
      __dbg_printk("Current thread_count = %d : ", thread_count);
      for (i = 0; i < TEST_NB_CONSUMER_PER_SEMAPHORE; i++)
	__dbg_printk("%d ", nb_reception[i]);
      __dbg_printk("\n");
    }

  return ESUCCESS;
}

--------------080202000007010402090800--

--------------enig6CA95CE9805F365CE1D6508A
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
Comment: Using GnuPG with Debian - http://enigmail.mozdev.org

iD8DBQE+0ScV9lPLMJjT96cRArIlAJwIBa3/HlD5E8/p2y4DZ9SGAFi69gCfevDQ
mNhlPrsMUbJEhb3gbFzangg=
=cPkv
-----END PGP SIGNATURE-----

--------------enig6CA95CE9805F365CE1D6508A--