Verrouillage de 4 octets à un seul graveur/plusieurs lecteurs futex

Question

Vous recherchez une implémentation minimale, basée sur futex, d'un verrou à un seul graveur/plusieurs lecteurs ne nécessitant aucun espace supplémentaire au-delà d'une seule variable d'état futex de 4 octets.

Un peu d'arrière-plan: J'ai une application qui va intégrer un verrou dans chacune des dizaines à des centaines de millions de petits objets. En raison de la nature très fine du verrouillage et de la structure de l'application, je prévois une contention minimale. En outre, les écrivains seront rares et les écrivains en concurrence plus rares encore. Pour toutes ces raisons, dans ce contexte particulier, une solution sujette (en théorie) au phénomène du «tonnerre entendu» est tout à fait acceptable.

Answer 1

Vous trouverez ma mise en œuvre à https://gist.github.com/smokku/653c469d695d60be4fe8170630ba8205

L'idée est qu'il ne peut y avoir qu'un seul fil prenant la serrure pour l'écriture (futex valeur 0), verrouillage peut être ouvert (valeur futex 1) ou il peut y avoir beaucoup lecture des threads (valeurs de futex supérieures à 1). Donc, les valeurs inférieures à 1 (il n'y en a qu'une seule) bloquent les lecteurs et les écrivains sur futex, et les valeurs supérieures à 1 bloquent uniquement les auteurs. Déverrouiller le fil réveille l'un des threads en attente, mais vous devez faire attention à ne pas consommer un lecteur seulement réveiller par un thread écrivain.

#define cpu_relax() __builtin_ia32_pause() 
#define cmpxchg(P, O, N) __sync_val_compare_and_swap((P), (O), (N)) 

static unsigned _lock = 1; // read-write lock futex 
const static unsigned _lock_open = 1; 
const static unsigned _lock_wlocked = 0; 

static void _unlock() 
{ 
    unsigned current, wanted; 
    do { 
     current = _lock; 
     if (current == _lock_open) return; 
     if (current == _lock_wlocked) { 
      wanted = _lock_open; 
     } else { 
      wanted = current - 1; 
     } 
    } while (cmpxchg(&_lock, current, wanted) != current); 
    syscall(SYS_futex, &_lock, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0); 
} 

static void _rlock() 
{ 
    unsigned current; 
    while ((current = _lock) == _lock_wlocked || cmpxchg(&_lock, current, current + 1) != current) { 
     while (syscall(SYS_futex, &_lock, FUTEX_WAIT_PRIVATE, current, NULL, NULL, 0) != 0) { 
      cpu_relax(); 
      if (_lock >= _lock_open) break; 
     } 
     // will be able to acquire rlock no matter what unlock woke us 
    } 
} 

static void _wlock() 
{ 
    unsigned current; 
    while ((current = cmpxchg(&_lock, _lock_open, _lock_wlocked)) != _lock_open) { 
     while (syscall(SYS_futex, &_lock, FUTEX_WAIT_PRIVATE, current, NULL, NULL, 0) != 0) { 
      cpu_relax(); 
      if (_lock == _lock_open) break; 
     } 
     if (_lock != _lock_open) { 
      // in rlock - won't be able to acquire lock - wake someone else 
      syscall(SYS_futex, &_lock, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0); 
     } 
    } 
}