Семантика получения и выпуска атомарных операций Intel-64 и ia32 и GCC 5+ - PullRequest
0 голосов
/ 02 июня 2018

Я изучаю атомарные особенности процессора Intel на моем процессоре Haswell (4/8 ядро ​​2.3-3.9 ГГц i7-4790M), и считаю, что его действительно сложно построить, например.надежные операции mutex_lock () и mutex_unlock (), как предлагается, например, в руководстве GCC:

6,53 x86-специфичные расширения модели памяти для транзакционной памяти

Архитектура x86 поддерживаетдополнительные флаги упорядочения памяти для обозначения критических секций блокировки для устранения аппаратной блокировки.Они должны быть указаны в дополнение к существующей модели памяти для атомарных встроенных функций.

 '__ATOMIC_HLE_ACQUIRE'
 Start lock elision on a lock variable.  Memory model must be
 '__ATOMIC_ACQUIRE' or stronger.
 '__ATOMIC_HLE_RELEASE'
 End lock elision on a lock variable.  Memory model must be
 '__ATOMIC_RELEASE' or stronger.

При сбое получения блокировки требуется для хорошей производительности, чтобы быстро прервать транзакцию.Это можно сделать с помощью '_mm_pause'

 #include <immintrin.h> // For _mm_pause

 int lockvar;

 /* Acquire lock with lock elision */
 while (__atomic_exchange_n(&lockvar, 1, 
     __ATOMIC_ACQUIRE|__ATOMIC_HLE_ACQUIRE))
     _mm_pause(); /* Abort failed transaction */
 ...
 /* Free lock with lock elision */
 __atomic_store_n(&lockvar, 0, __ATOMIC_RELEASE|__ATOMIC_HLE_RELEASE);

Итак, прочитав это, и в разделе 8.1 Руководства разработчика программного обеспечения Intel, раздел 8.1, «Заблокированные атомарные операции», в частности, в разделе 8.1.4, «Влияние операции LOCK на внутренние кэши процессора», побудило меня сначала реализовать мой тест mutex_lock () mutex_unlock (), например:

... static inline <strong>attribute</strong>((always_inline,const)) bool ia64_has_clflush(void) { register unsigned int ebx=0; asm volatile ( "MOV $7, %%eax\n\t" "MOV $0, %%ecx\n\t" "CPUID\n\t" "MOV %%ebx, %0\n\t" : "=r" (ebx) : : "%eax", "%ecx", "%ebx" ); return ((ebx & (1U<<23)) ? true : false); }</p> <pre><code>#define _LD_SEQ_CST_ __ATOMIC_SEQ_CST #define _ST_SEQ_CST_ __ATOMIC_SEQ_CST #define _ACQ_SEQ_CST_ (__ATOMIC_SEQ_CST|__ATOMIC_HLE_ACQUIRE) #define _REL_SEQ_CST_ (__ATOMIC_SEQ_CST|__ATOMIC_HLE_RELEASE) static bool has_clflush=false; static void init_has_clflush(void) { has_clflush = ia64_has_clflush(); } static void init_has_clflush(void) __attribute__((constructor)); static inline __attribute__((always_inline)) void mutex_lock( register _Atomic int *ua ) { // the SDM states that memory to be used as semaphores // should not be in the WB cache memory, but nearest we // can get to uncached memory is to explicitly un-cache it: if(has_clflush) asm volatile ( "CLFLUSHOPT (%0)" :: "r" (ua) ); // why isn't the cache flush enough? else asm volatile ( "LFENCE" :: ); register unsigned int x; x = __atomic_sub_fetch( ua, 1, _ACQ_SEQ_CST_); _mm_pause(); if(has_clflush) asm volatile ( "CLFLUSHOPT (%0)" :: "r" (ua) ); else asm volatile ( "SFENCE" :: ); while((x = __atomic_load_n(ua,_LD_SEQ_CST_)) != 0) switch(syscall( SYS_futex, ua, FUTEX_WAIT, x, nullptr,nullptr,0)) {case 0: break; case -1: switch( errno ) { case EINTR: case EAGAIN: continue; default: fprintf(stderr,"Unexpected futex error: %d : '%s'.", errno, strerror(errno)); return; } } } static inline __attribute__((always_inline)) void mutex_unlock( register _Atomic int *ua ) { if(has_clflush) asm volatile ( "CLFLUSHOPT (%0)" :: "r" (ua) ); else asm volatile( "LFENCE" :: ); register unsigned int x; x = __atomic_add_fetch( ua, 1, _REL_SEQ_CST_); _mm_pause(); if(has_clflush) asm volatile ( "CLFLUSHOPT (%0)" :: "r" (ua) ); else asm volatile ( "SFENCE" :: ); if(x == 0) while( (1 < syscall( SYS_futex, ua, FUTEX_WAKE, 1, nullptr,nullptr,0)) && (errno == EINTR)); }

Теперь интересно то, что критические операции вычитания mutex_lock () и сложения mutex_unlock () заканчиваются в виде инструкций:

mutex_lock:

# 61 "intel_lock1.c" 1
    CLFLUSHOPT (%rbx)
# 0 "" 2
#NO_APP
.L7:
    lock xacquire subl  $1, lck(%rip)
    rep nop
    cmpb    $0, has_clflush(%rip)
    je  .L8
#APP
# 72 "intel_lock1.c" 1
    CLFLUSHOPT (%rbx)
# 0 "" 2

mutex_unlock:

#APP
# 98 "intel_lock1.c" 1
    CLFLUSHOPT (%rbx)
# 0 "" 2
#NO_APP
.L24:
    movl    $1, %eax
    lock xacquire xaddl %eax, lck(%rip)
    rep nop
    addl    $1, %eax
    cmpb    $0, has_clflush(%rip)
    je  .L25
#APP
# 109 "intel_lock1.c" 1
    CLFLUSHOPT (%rbx)
# 0 "" 2
#NO_APP

Но эта реализация, похоже, требует, чтобы LFENCE / SFENCE работали надежно (CLFLUSHOPT недостаточно), в противном случае оба потока могут оказаться заблокированными в futex () со значением блокировки, равным -1.

Из прочтения документации Intel не видно, как может получиться, что два потока, вводящие последовательность команд:

# %rbx == $lck
CLFLUSHOPT (%rbx)
lock xacquire subl  $1, lck(%rip)
rep nop

, могут оба завершиться с результатом '-1' в *lck, если * lck был 0;конечно, один поток ДОЛЖЕН получить -1, а другой - -2?

Но Стрейс не говорит:

strace: Process 11978 attached with 2 threads
[pid 11979] futex(0x60209c, FUTEX_WAIT, 4294967295, NULL <unfinished ...>
[pid 11978] futex(0x60209c, FUTEX_WAIT, 4294967295, NULL^C

, это тупиковая ситуация.Где я ошибся?

Пожалуйста, любые специалисты Intel по блокировке и кэшированию процессоров Intel могут объяснить, как два атомных уменьшения или приращения одного и того же некэшированного местоположения * lck, оба утверждают сигнал шины #LOCK (эксклюзивный доступ к шине)и XACQUIRE может в итоге получить тот же результат в * lck?

Я думал, что это то, что префикс #LOCK (и HLE) должен был предотвратить?Я пытался НЕ использовать HLE и просто __ATOMIC_SEQ_CST для всех обращений (это просто добавляет префикс LOCK, а не XACQUIRE), но это не имеет значения - тупик по-прежнему приводит к отсутствию {L, S} FENCE-ов.

Я прочитал отличную статью Ульриха Дреппера [Futexes is Tricky]: http://www.akkadia.org/drepper/futex.pdf, но он представляет реализацию мьютекса, которая записывает только жестко запрограммированные константы в память блокировки.Я понимаю почему.Очень трудно заставить мьютекс работать надежно с счетчиком официантов или любым другим арифметическим, сделанным на значении блокировки.Кто-нибудь нашел способы сделать надежную блокированную арифметику такой, чтобы результат соответствовал значению блокировки / семафора в Linux x86_64?Больше всего интересно обсудить их ...

Так что после нескольких тупиков, исследующих HLE & CLFLUSH, ЕДИНСТВЕННАЯ рабочая версия блокировки / разблокировки, на которую я смог прийти, использует жестко закодированные константы и __atomic_compare_exchange_n -Полный источник тестовой программы, который увеличивает счетчик (без блокировки) до получения сигнала + / выхода, находится по адресу:

Рабочий пример: intel_lock3.c

[]: https://drive.google.com/open?id=1ElB0qmwcDMxy9NBYkSXVxljj5djITYxa

enum LockStatus
{ LOCKED_ONE_WAITER = -1
, LOCKED_NO_WAITERS = 0
, UNLOCKED=1
};

static inline __attribute__((always_inline))
bool mutex_lock( register _Atomic int *ua )
{ register int x;
  int cx;
 lock_superceded:
  x  = __atomic_load_n( ua, _LD_SEQ_CST_ );
  cx = x;
  x = (x == UNLOCKED)
       ? LOCKED_NO_WAITERS
       : LOCKED_ONE_WAITER;
  if (! __atomic_compare_exchange_n
      ( ua, &cx, x, false, _ACQ_SEQ_CST_,  _ACQ_SEQ_CST_) )
    goto lock_superceded;
  if( x == LOCKED_ONE_WAITER )
  { do{
    switch(syscall( SYS_futex, ua, FUTEX_WAIT, x, nullptr,nullptr,0))
    {case 0:
      break;
     case -1:
      switch( errno )
      { case EINTR:
         return false;
        case EAGAIN:
          break;
        default:
          fprintf(stderr,"Unexpected futex WAIT error: %d : '%s'.",
                  errno, strerror(errno));
          return false;
       }
    }
    x = __atomic_load_n(ua,_LD_SEQ_CST_);
    } while(x < 0);
  }
  return true;
}

static inline __attribute__((always_inline))
bool mutex_unlock( register _Atomic int *ua )
{ register int x;
  int cx;
 unlock_superceded:
  x  = __atomic_load_n( ua, _LD_SEQ_CST_ );
  cx = x;
  x = (x == LOCKED_ONE_WAITER)
       ? LOCKED_NO_WAITERS
       : UNLOCKED;
  if (! __atomic_compare_exchange_n
       ( ua, &cx, x, false, _ACQ_SEQ_CST_,  _ACQ_SEQ_CST_) )
    goto unlock_superceded;
    if(x == LOCKED_NO_WAITERS)
    { while((1 < 
             syscall( SYS_futex, ua, FUTEX_WAKE, 1, nullptr,nullptr,0))
         ||( UNLOCKED != __atomic_load_n( ua, _LD_SEQ_CST_ ))
         ) // we were a waiter, so wait for locker to unlock !
      { if( errno != 0 )
          switch(errno)
          {case EINTR:
            return false;
           case EAGAIN:
            break;
           default:
            fprintf(stderr,
                  "Unexpected futex WAKE error: %d : '%s'.", 
                  errno, strerror(errno));
            return false;
          }
      }
   }
   return true;
 }

 Build & Test (GCC 7.3.1 & 6.4.1 & 5.4.0) used:
 $ gcc -std=gnu11 -march=x86-64 -mtune=native -D_REENTRANT \
   -pthread -Wall -Wextra -O3 -o intel_lock3 intel_lock3.c

 $ ./intel_lock3
 # wait a couple of seconds and press ^C
 ^C59362558

Нерабочая версия с использованием арифметики:

https://drive.google.com/open?id=10yLrohdKLZT4p3G1icFHdjF5eHY68Yws

Компилировать, например, с:

$ gcc -std=gnu11 -march=x86_64 -mtune=native -O3 -Wall -Wextra 
  -o intel_lock2 intel_lock2.c
$ ./intel_lock2
# wait a couple of seconds and press ^C
$ ./intel_lock2
^Cwas locked!
446

Не должно быть печати "былозаблокирован!»и в течение пары секунд должно быть превышено число, напечатанное в конце, @ 5e8: 5x10 ^ 8, а не 446.

Запуск с помощью strace показывает, что два потока блокируют в ожидании значения блокировки -1 становится 0:

$ strace -f -e trace=futex ./intel_lock2
strace: Process 14481 attached
[pid 14480] futex(0x602098, FUTEX_WAIT, 4294967295, NULL <unfinished ...>
[pid 14481] futex(0x602098, FUTEX_WAKE, 1 <unfinished ...>
[pid 14480] <... futex resumed> )       = -1 EAGAIN (Resource temporarily
                                          unavailable)
[pid 14481] <... futex resumed> )       = 0
[pid 14480] futex(0x602098, FUTEX_WAKE, 1 <unfinished ...>
[pid 14481] futex(0x602098, FUTEX_WAIT, 4294967295, NULL <unfinished ...>
[pid 14480] <... futex resumed> )       = 0
[pid 14481] <... futex resumed> )       = -1 EAGAIN (Resource temporarily
                                          unavailable)
[pid 14480] futex(0x602098, FUTEX_WAIT, 4294967295, NULL <unfinished ...>
[pid 14481] futex(0x602098, FUTEX_WAIT, 4294967295, NULL^C <unfinished  
...>
[pid 14480] <... futex resumed> )       = ? ERESTARTSYS (To be restarted 
if SA_RESTART is set)
strace: Process 14480 detached
strace: Process 14481 detached
was locked!
7086

$

Обычно WAIT следует планировать до WAKE, но каким-то образом GCC интерпретирует семантику упорядочения памяти так, чтоWAKE всегда назначается раньше, чем WAIT;но даже если это произойдет, код должен просто задерживаться и никогда не заканчиваться тем, что два потока получат значение -1 lck при входе в futex (... FUTEX_WAIT ..).

Почти идентичный алгоритм, использующий арифметику для значения блокировки, ВСЕГДА блокируется, когда оба потока получают (-1, -1) - обратите внимание, значение -2 никогда не будет замечено никаким потоком:

static inline __attribute__((always_inline))
bool mutex_lock( register _Atomic volatile int *ua )
{ register int x;
  x = __atomic_add_fetch( ua, -1, _ACQ_SEQ_);
  if( x < 0 )
  { do{
    // here you can put:
    // if( x == -2) { .. NEVER REACHED! }
    switch(syscall( SYS_futex, ua, FUTEX_WAIT, x, nullptr,nullptr,0))
    {case 0:
      break;
     case -1:
      switch( errno )
      { case EINTR:
         return false; // interrupted - user wants to exit?
        case EAGAIN:
          break;
        default:
          fprintf(stderr,"Unexpected futex WAIT error: %d : '%s'.",
                  errno, strerror(errno));
          return false;
       }
    }
    x = __atomic_load_n(ua,_LD_SEQ_);
    } while(x < 0);
  }
  return true;
}

static inline __attribute__((always_inline))
bool mutex_unlock( register _Atomic volatile int *ua )
{ register int x;
  x = __atomic_add_fetch( ua, 1, _REL_SEQ_);
  if(x == 0) // there was ONE waiter
     while(  (1 < 
             syscall( SYS_futex, ua, FUTEX_WAKE, 1, nullptr,nullptr,0)
             )
           ||(1 < __atomic_load_n(ua, _LD_SEQ_)
             ) // wait for first locker to unlock
           ) 
     { if( errno != 0 )
         switch(errno)
         {case EINTR:
           return false;
          case EAGAIN:
           break;
          default:
           fprintf(stderr,"Unexpected futex WAKE error: %d : '%s'.", 
                  errno, strerror(errno));
           return false;
         }
       }
     return true;
   }

Итак, я думаю, если бы арифметические операции работали так, как ожидалось, т.е.были бы сериализованными и атомарными, тогда вышеприведенный код не блокировалсяарифметика должна генерировать те же числа, что и значения перечисления LockStatus, используемые в рабочем примере.

Но что-то не так с арифметикой, которая теперь выдает инструкции:

mutex_lock:

movl    $-1, %eax
lock xaddl  %eax, (%rdx)

mutex_unlock:

movl    $1, %eax
lock xaddl  %eax, (%rdx)

Theсам код не вставляет никаких ограждений, но каждый __atomic_store_n (ua, ...) генерирует единицу.

AFAICS, нет допустимого расписания для этого кода, в результате которого оба потока получают одинаковое значение -1. ​​

Таким образом, мой вывод заключается в том, что использование префикса Intel LOCK в арифметических инструкциях небезопасно и приводит к ошибочному поведению в пользовательских режимах скомпилированных программ Linux x86_64 gcc - только запись постоянных значений из текстовой памяти в память данных атомарна и последовательно упорядочена поПлатформы Intel Haswell i7-4790M с gcc и Linux и арифметика на таких платформах не могут быть сделаны атомарными и последовательно упорядочены с использованием любой комбинации HLE / XACQUIRE, префикса блокировки или инструкций FENCE.

Мои догадкиявляется то, что предсказание ветвления почему-то терпит неудачу и добавляет дополнительную арифметическую операцию / неудачу к pвыполнить арифметическую операцию на этой платформе с установленным префиксом LOCK и несколькими потоками на разных физических ядрах.Поэтому все арифметические операции с заявленным префиксом LOCK являются подозрительными и их следует избегать.

Ответы [ 2 ]

0 голосов
/ 04 июня 2018

Последний пример программы intel_lock2.c на

: https://drive.google.com/open?id=10yLrohdKLZT4p3G1icFHdjF5eHY68Yws

теперь работает так же, как и последняя программа intel_lock3.c на

: https://drive.google.com/open?id=1ElB0qmwcDMxy9NBYkSXVxljj5djITYxa

, и теперь существует версия, которая поддерживает точное отрицательное число официантов и использует заблокированную арифметику, по адресу:

intel_lock4.c: https://drive.google.com/open?id=1kNOppMtobNHU0lfkfWTh8auXvRcbZfhO

Unlock_mutex ()рутина, если есть официанты, должна ждать разблокировки каждого существующего официанта, чтобы при возврате мьютекс разблокировался и официантов не было.Он может либо достичь этого с помощью spin-lock + sched_yield (), ожидая, пока значение блокировки не станет равным 1, либо может использовать другой вызов futex.Таким образом, оригинальный шкафчик, когда он входит в mutex_unlock (), становится ответственным за то, чтобы каждый существующий официант проснулся и разблокировал мьютекс.

Ранее этот ответ содержал:

Но естьвсе еще странность: если какой-либо процесс ptrace-ed () по strace или скомпилирован с '-g3' вместо '-O3', он теперь испытывает 'несоответствие' - т.е.противоречивые критические секции измененных значений.Этого не происходит, если программа не ptrace-d и скомпилирована с -O3.

См. Обсуждение ниже.Для того чтобы встроенные функции GCC __atomic* работали, необходимо вызвать фазы оптимизации GCC, при этом во время компиляции должен быть указан флаг ANY -O$x, достаточный для обеспечения правильной работы встроенных __atomic*.

Окончательная лучшая версияпроцедуры mutex_lock () / unlock:

</p> <pre><code>static inline __attribute__((always_inline)) bool mutex_lock( register _Atomic volatile int *ua ) // lock the mutex value pointed to by 'ua'; // can return false if operation was interrupted ( a signal received ). { register int x; // lock_again: x = __atomic_add_fetch( ua, -1, _ACQ_SEQ_); while( x < 0 ) { switch(syscall( SYS_futex, ua, FUTEX_WAIT, x, nullptr,nullptr,0)) {case 0: break; case -1: switch( errno ) { case EINTR: return false; case EAGAIN: break; default: // this has never been observed to happen, but in any // production implementation // should be replaced by some kind of // 'throw( exception )' statement: fprintf(stderr,"Unexpected futex WAIT error: %d : '%s'.", errno, strerror(errno)); return false; } } x = __atomic_load_n(ua,_LD_SEQ_); } return true; } static inline __attribute__((always_inline)) bool mutex_unlock( register _Atomic volatile int *ua ) // unlock: returns false only if interrupted, else returns true // only when the mutex pointed to by *ua has been unlocked and // has no waiters. { #ifdef _WITH_UWAIT_ static int has_unlock_waiter = 0; #endif register int x; x = __atomic_add_fetch( ua, 1, _REL_SEQ_); if(x < 1) // there was at least ONE waiter, // so we are the original locker { while(1 < syscall( SYS_futex, ua, FUTEX_WAKE, 1, nullptr,nullptr,0)) { if( errno != 0 ) switch(errno) {case EINTR: return false; case EAGAIN: break; default: // never observed to happen - should be a throw() fprintf(stderr,"Unexpected futex WAKE error: %d : '%s'.", errno, strerror(errno)); return false; } } #ifdef _WITH_UWAIT_ // this is strictly unnecessary, and can be replaced by use of // sched_yield() (see below), but it // makes the situation clearer: // unlock : // so we have woken a waiter; wait for that waiter to // actually unlock before returning - // by definition, when that waiter enters mutex_unlock() // (AND IT MUST!!), it will not // enter the clause containing this code unless there is more than // one other waiter., in which case we want to continue until there // are no waiters. while(1 > (x = __atomic_load_n( ua, _LD_SEQ_ ))) { __atomic_store_n(&has_unlock_waiter, 1, _ST_SEQ_); if( (-1 == syscall( SYS_futex, ua, FUTEX_WAIT, x, nullptr,nullptr,0) ) && (errno == EINTR) ) return false; } if( __atomic_load_n(&has_unlock_waiter, _ST_SEQ_) ) __atomic_store_n(&has_unlock_waiter, 0, _ST_SEQ_); #else // The same result is actually achieved by this loop: while(1 > (x = __atomic_load_n(ua, _LD_SEQ_))) sched_yield(); #endif // we do need to wait for the waiting locker to unlock // before proceeding, else // mutex_lock could be reentered with lck < 0 and deadlock // would result. #ifdef _WITH_UWAIT_ }else if( (x==1) && __atomic_load_n(&has_unlock_waiter, _ST_SEQ_) ) { // so we're the waiter that a previous unlock woke up // and is waiting for - it now needs to be woken: while(1 < syscall( SYS_futex, ua, FUTEX_WAKE, 1, nullptr,nullptr,0)) { if( errno != 0 ) switch(errno) {case EINTR: // no, we cannot let user try to unlock again, since modification of lock value succeeded. case EAGAIN: break; default: fprintf(stderr,"Unexpected futex WAKE error: %d : '%s'.", errno, strerror(errno)); return false; } } } #else } #endif return true; }

Тестирование:

$ gcc -std=gnu11 -pthread -D_WITH_UWAIT_ -O3 -o il2 il2.c
$ ./il2
^C20906015
$ gcc -std=gnu11 -pthread -O3 -o il2 il2.c
$ ./il2
^C45851541

(«^ C» означает нажатие+ клавиши одновременно).

Теперь все версии никогда не блокируются и работают с:

$ strace -f -e trace=futex ./{intel_lock2 OR intel_lock3 OR intel_lock4} 

Я пытался связать скомпилированную версию (-g) и получил несоответствие -этого не происходит, если также используется ЛЮБОЙ флаг '-O'.

0 голосов
/ 02 июня 2018

lock subl $1, (%rdi) или lock xaddl %eax, (%rdx) являются 100% атомными во всех случаях, даже если указатель смещен (но в этом случае намного медленнее), и являются полными барьерами памяти.В кешируемой памяти не будет никакого внешнего сигнала шины #LOCK;внутренняя реализация просто блокирует строку кэша в состоянии M MESI внутри ядра, в котором выполняется инструкция lock ed.См. Может ли num ++ быть атомарным для 'int num'? для получения более подробной информации.

Если ваш тест обнаруживает, что он не атомарный, ваше оборудование сломано или ваш тест сломан.Обнаружение тупика говорит о том, что в вашем дизайне есть ошибка, а не то, что ваши атомарные примитивные строительные блоки не являются атомными.Вы можете очень легко протестировать атомарные приращения, используя два потока для увеличения общего счетчика, и заметить, что счетчики не потеряны.В отличие от того, что вы использовали addl $1, shared(%rip) без lock, где вы бы увидели потерянные значения.

Кроме того, lfence, sfence и pause не влияют на корректность в обычном случае (нетNT хранит и использует только WB (Write-Back) память).Если что-то из вашего забора / clflush помогает, то только добавляя дополнительную задержку где-то, что может привести к тому, что этот поток всегда проиграет гонку в вашем тесте, а не сделает его безопасным.mfence - это единственное ограждение, которое имеет значение, блокируя эффекты переупорядочения StoreLoad и перенаправления магазина.(Именно поэтому gcc использует его как часть реализации хранилища seq-cst).

Получите базовую версию, работающую прямо перед тем, как вы даже подумаете о том, чтобы возиться с HLE / транзакционной памятью.


Состояние гонки в первой версии получения блокировки

x = __atomic_sub_fetch( ua, 1, _ACQ_SEQ_CST_); является атомарным, и lock sub только одного потока может изменить ua с 0 на -1и получите x=-1 оттуда .

Но вы не используете sub_fetch результат , вы выполняете другую загрузку с
while((x = __atomic_load_n(ua,_LD_SEQ_CST_)) != 0)

Таким образом, другой поток может видеть ua=-1, если первый поток блокируется, а затем разблокируется между lock sub и нагрузкой во втором потоке .

Причинаон называется sub_fetch в том, что он атомарно возвращает старое значение, а также атомно изменяет значение в памяти.Тот факт, что вы отбрасываете результат sub_fetch, объясняется тем, что он вообще может компилироваться в lock sub вместо lock xadd с регистром, содержащим -1.

(или умный компилятор может скомпилировать его вlock sub и отметьте ZF, потому что вы можете определить, когда значение стало ненулевым или отрицательным из флагов, установленных lock sub.)


См. C & реализация низкоуровневого семафора для простого семафора без отступления от режима сна / пробуждения с помощью ОС.Он вращается на нагрузке до тех пор, пока мы не увидим значение больше 0, затем попытается снять блокировку с помощью C11 fetch_add(-1).

Но если он проиграл гонку другому потоку, он отменяет декремент.

Это, вероятно, плохой дизайн;Вероятно, лучше всего попытаться уменьшить значение с помощью lock cmpxchg, поэтому потокам, которые потерпели неудачу, не придется отменять их уменьшение.


Я не использовал HLE, но я предполагаю, что эта ошибка - это то, что ломаетваш HLE также блокируется.

Вам не нужны SFENCE, LFENCE или CLFLUSH [OPT] или что-либо еще.lock xadd уже является полным барьером памяти и на 100% атомарен сам по себе для любого типа памяти (включая WB).

Возможно, вы неправильно прочитали SDM, если подумали, что следует избегать использования памяти WB для мьютексов /семафоры.


Во время пробуждения у вас также есть окно гонки, которое может привести к тупику

Этот код в mutex_lock выглядит неработающим / склонным к гонкам

x = __atomic_sub_fetch( ua, 1, _ACQ_SEQ_CST_);  // ok, fine
_mm_pause();   // you don't want a pause on the fast path.

if( x < 0 )   // just make this a while(x<0) loop
do {
   futex(..., FUTEX_WAIT, ...);

   x = __atomic_load_n(ua,_LD_SEQ_CST_);        // races with lock sub in other threads.
} while(x < 0);

Данный поток A спит в futex с lck == -1 (если это возможно?):

  • поток B разблокируется, в результате чего lck == 0, и вызывает futex (FUTEX_WAKE)
  • поток A просыпается, futex возвращается, пока lck по-прежнему 0
  • какой-то другой поток (B или 3-й поток) входит в mutex_lock и запускает __atomic_sub_fetch( ua, 1, _ACQ_SEQ_CST_);, оставляя lck == -1
  • поток A проходит x = __atomic_load_n(ua,_LD_SEQ_CST_); в нижней части своего цикла и видит -1

Теперь у вас есть 2 потока, застрявшие в цикле ожидания futex, и ни один поток фактически не получил мьютекс / не вошел в критическую секцию.


Я думаю, что ваш дизайн не работает, если он зависит отвыполнение загрузки после возврата futex

В примере справочной страницы futex(2) из fwait() показано, что он возвращается после возврата futex, без загрузки снова.

futex() является атомарной операцией сравнения и блокировки .Ваш дизайн изменяет значение вашего счетчика на -1, если один поток ожидает блокировки, в то время как третий поток пытается ее получить.Так что, возможно, ваш дизайн подходит для 2 потоков, но не для 3.

Вероятно, будет хорошей идеей использовать атомарный CAS для декремента, поэтому вы никогда не измените lck на -1 или ниже,и futex может оставаться заблокированным.

Тогда, если вы можете рассчитывать на него только для пробуждения 1, тогда вы также можете доверять его возвращаемому значению, которое означает, что у вас действительно есть блокировка без гоночной нагрузки.Я думаю.

...