Linux 3.0 :Bug de blocage du futex-lock ?

Question

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch)
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch)
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters

struct Lock
{
Lock() : x(1) {}

void lock()
{
    while (true)
    {
        if (SubFetch(x, 1) == 0)
            return;

        x = -1;

        CompareWait(x, -1);
    }
}

void unlock()
{
    if (AddFetch(x, 1) == 1)
        return;

    x = 1;

    Wake(x, 1);
}

private:
    int x;
};

Linux 3.0 fournit un appel système appelé futex, sur lequel sont basés de nombreux utilitaires de concurrence, y compris les implémentations récentes de pthread_mutex.Chaque fois que vous écrivez du code, vous devez toujours vous demander si utiliser une implémentation existante ou l'écrire vous-même est le meilleur choix pour votre projet.

Ci-dessus se trouve une implémentation d'un verrou (mutex, 1 sémaphore de comptage de permis) basé sur futex et la description sémantique dans homme futex(7)

Il semble contenir un bogue de blocage selon lequel, après que plusieurs threads ont tenté de le verrouiller et de le déverrouiller plusieurs milliers de fois, les threads peuvent entrer dans un état où x == -1 et tous les threads sont bloqués dans CompareWait, mais personne ne détient le verrouillage.

Quelqu'un peut-il voir où se trouve le bug ?

Mise à jour: Je suis un peu surpris que futex(7)/semantics soit si cassé.J'ai complètement réécrit Lock comme suit...est-ce correct maintenant ?

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false;

struct Lock
{
Lock() : x(0) {}

void lock()
{
    while (!CompareAssign(x, 0, 1))
        if (x == 2 || CompareAssign(x, 1, 2))
            CompareWait(x, 2);
}

void unlock()
{
    if (SubFetch(x, 1) == 0)
        return;

    x = 0;

    Wake(x, 1);
}

private:
int x;
};

L’idée ici est que x a les trois états suivants :

0: unlocked
1: locked & no waiters
2: locked & waiters

Answer 1

Le problème est que vous attribuez explicitement -1 à x si la SubFetch ne parvient pas à acquérir le verrou.Cela fait la course avec le déverrouillage.

1. Le thread 1 acquiert le verrou. x==0.
2. Le thread 2 tente d'acquérir le verrou.Le SubFetch ensembles x à -1, puis le thread 2 est suspendu.
3. Le thread 1 libère le verrou.Le AddFetch ensembles x à 0, donc le code définit alors explicitement x à 1 et appelle Wake.
4. Le fil 2 se réveille et se fixe x à -1, puis appelle CompareWait.

Le fil de discussion 2 est maintenant bloqué en attente, avec x défini sur -1, mais il n'y a personne pour le réveiller, car le thread 1 a déjà libéré le verrou.

Answer 2

La mise en œuvre correcte d'un mutex basé sur Futex est décrite dans le papier de Ulrich Drepper "Les Fuexes sont difficiles"

http://people.redhat.com/dpper/futex.pdf

Il inclut non seulement le code, mais aussi une explication très détaillée de la raison pour laquelle il est correct.Le code du papier:

class mutex
{
 public:
 mutex () : val (0) { }
 void lock () {
   int c;
   if ((c = cmpxchg (val, 0, 1)) != 0)
     do {
       if (c == 2 || cmpxchg (val, 1, 2) != 0)
         futex_wait (&val, 2);
     } while ((c = cmpxchg (val, 0, 2)) != 0);
 }
 void unlock () {
//NOTE: atomic_dec returns the value BEFORE the operation, unlike your SubFetch !
   if (atomic_dec (val) != 1) {
     val = 0;
     futex_wake (&val, 1);
   }
 }
 private:
   int val;
};

comparer le code dans le papier avec votre code, je repey une différence

vous avez

si (x== 2 || comparaisse (x, 1, 2))

Utilisation de la valeur de Futex directement alors que Drepper utilise la valeur de retour de la précédente comparaisse ().Cette différence n'affectera probablement que les performances seulement.

Votre code de déverrouillage est également différent, mais semble être sémantiquement équivalent.

En tout cas, je vous conseillerais vivement de suivre le code de Drepper à la lettre.Ce papier a résisté à l'épreuve du temps et a reçu beaucoup d'examen par les pairs.Vous ne gagnerez rien de rouler le vôtre.

Answer 3

Que diriez-vous de ce scénario avec trois threads, A, B et C.

L'état initial de ce scénario a :

• fil A tenant le verrou
• le fil B ne se bat pas encore pour le verrou
• enfiler C dans CompareWait()
• x == -1 à partir du moment où C n'a pas réussi à acquérir le verrou

        A                  B                C
    ==============   ================  ===============
     AddFetch()
     (so x == 0)
                       SubFetch()
                       (so x == -1)

     x = 1

                       x = -1

     Wake()

À ce stade, que B ou C soient débloqués, ils n'obtiendront pas de résultat de 0 quand ils SubFetch().