Linux 3.0: Futox-Lock Deadlock Bug?

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 fornisce una chiamata di sistema chiamata < Strong> Futox , su cui si basano numerose utilità di concorrenza incluse le recenti implementazioni Pthread_Mutex. Ogni volta che scrivi il codice, dovresti sempre considerare se utilizzare un'implementazione esistente o scrivere da solo è la scelta migliore per il tuo progetto.

sopra è un'implementazione di un blocco (Mutex, 1 permesso di conteggio del conteggio del semaforo) basato su Futox e la descrizione semantica in uomo futix (7)

Sembra contenere un bug deadlock per cui dopo che più fili stanno cercando di bloccare e sbloccarlo da poche migliaia di volte, i fili possono entrare in uno stato in cui x== -1 e tutti i thread sono bloccati nel confronto sta tenendo la serratura.

Qualcuno può vedere dove è il bug?

Aggiornamento: Sono un po 'sorpreso che Futox (7) / Semantics sia così rotto. Ho completamente riscritto il blocco come segue ... è così corretto ora?

// 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'idea qui è che X ha i seguenti tre stati:

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

.

Answer 1

Il problema è che si è esplicitamente -1 assegnare a x se il SubFetch non riesce ad acquisire il blocco.Questo gare con lo sblocco.

.
1. thread 1 acquisisce il blocco.x==0.
2. Thread 2 tenta di acquisire la serratura.I SubFetch SET x TO -1, quindi Thread 2 è sospeso.
3. thread 1 rilascia il blocco.Il AddFetch imposta x a 0, quindi il codice imposta quindi esplicitamente x su 1 e chiama Wake.
4. Thread 2 Si sveglia e imposta x in -1, quindi chiama CompareWait.

   Thread 2 è ora bloccato in attesa, con x impostato su -1, ma non c'è nessuno a svegliarlo, poiché il filo 1 ha già rilasciato il blocco.

Answer 2

La corretta implementazione di un mutex basato su Futax è descritto nella carta di Ulrich Drepper "ITexes sono complicati"

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

Include non solo il codice ma anche una spiegazione molto dettagliata del perché è corretto.Il codice dalla carta:

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

.

Confrontando il codice nella carta con il tuo codice, ho individuato una differenza

hai

if (x== 2 || confrontoesign (x, 1, 2))

Usando il valore di FUTEX direttamente mentre Drepper utilizza il valore di ritorno dal precedente confronto ().Quella differenza probabilmente influenzerà solo le prestazioni.

Il tuo codice di sblocco è diverso anche, ma sembra essere semanticamente equivalente.

In ogni caso ti consiglierei vivamente di seguire il codice di Drepper alla lettera.Quel carta ha rimasto la prova del tempo e ha ricevuto molta revisione tra pari.Non guadagni nulla dal rotolare il tuo.

Answer 3

Che ne dici di questo scenario con tre fili, A, B e C.

Lo stato iniziale di questo scenario ha:

.
• Thread a Holding the Lock
• Thread B non si accontenta per il blocco solo
• Thread c in CompareWait()
• x == -1 da quando c non è riuscito ad acquisire il blocco

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

  .

  A questo punto se B o C sono sbloccati, non riceveranno il risultato di 0 quando generano SubFetch().