x86 эквивалент для LWARX и STWCX - PullRequest
Новая
       58

x86 эквивалент для LWARX и STWCX

9 голосов
/ 18 июля 2009

Я ищу эквивалент LWARX и STWCX (как на процессорах PowerPC) или способ реализации аналогичной функциональности на платформе x86. Кроме того, где было бы лучше всего узнать о таких вещах (например, хорошие статьи / веб-сайты / форумы для блокировки / программирования без ожидания).

Редактировать
Я думаю, что мне, возможно, потребуется дать более подробную информацию, поскольку предполагается, что я просто ищу операцию CAS (сравнение и своп). Я пытаюсь реализовать систему подсчета ссылок без блокировки с помощью умных указателей, которые могут быть доступны и изменены несколькими потоками. Мне в основном нужен способ реализовать следующую функцию на процессоре x86. 

int* IncrementAndRetrieve(int **ptr)
{
  int val;
  int *pval;
  do
  {
    // fetch the pointer to the value
    pval = *ptr;

    // if its NULL, then just return NULL, the smart pointer
    // will then become NULL as well
    if(pval == NULL)
      return NULL;

    // Grab the reference count
    val = lwarx(pval);

    // make sure the pointer we grabbed the value from
    // is still the same one referred to by  'ptr'
    if(pval != *ptr)
      continue;

    // Increment the reference count via 'stwcx' if any other threads
    // have done anything that could potentially break then it should
    // fail and try again
  } while(!stwcx(pval, val + 1));
  return pval;
}

Мне действительно нужно что-то, что достаточно точно имитирует LWARX и STWCX, чтобы осуществить это (я не могу найти способ сделать это с помощью функций CompareExchange, swap или add, которые я до сих пор нашел для x86).

Спасибо

Ответы [ 6 ]

11 голосов
/ 20 июля 2009

Как уже упоминал Майкл, вы, вероятно, ищете инструкцию cmpxchg.

Важно отметить, что метод PPC для этого известен как Условие загрузки ссылки / сохранения (LL / SC), в то время как архитектура x86 использует Compare And Swap (ССС). LL / SC имеет более строгую семантику, чем CAS, так как любое изменение значения по условному адресу приведет к сбою хранилища, даже если другое изменение заменит значение тем же значением, на котором была загружена нагрузка. CAS, с другой стороны, преуспел бы в этом случае. Это известно как проблема ABA (см. Ссылку CAS для получения дополнительной информации).

Если вам нужна более строгая семантика в архитектуре x86, вы можете приблизить ее, используя инструкцию сравнения и замены двойной ширины x86s (DWCAS) cmpxchg8b или cmpxchg16b в x86_64. Это позволяет вам атомарно поменять два последовательных слова «натурального размера» сразу вместо обычного. Основная идея состоит в том, что одно из двух слов содержит интересующее значение, а другое содержит постоянно увеличивающийся «счетчик мутаций». Хотя технически это не устраняет проблему, вероятность того, что счетчик мутаций обернется между попытками, настолько низка, что для большинства целей является разумной заменой.

2 голосов
/ 18 июля 2009

x86 не поддерживает напрямую «оптимистический параллелизм», как это делает PPC - скорее, поддержка параллелизма в x86 основана на «префиксе блокировки», см. здесь . (Некоторые так называемые «атомарные» инструкции, такие как XCHG, фактически получают свою атомарность, внутренне утверждая префикс LOCK, независимо от того, кодировал ли его программист ассемблерного кода или нет). Это не совсем «бомбоубежище», если говорить дипломатично (на самом деле, оно скорее подвержено несчастным случаям, я бы сказал; -).

1 голос
/ 10 августа 2010

Не знаю, делают ли LWARX и STWCX недействительными всю строку кэша, CAS и DCAS делают. Это означает, что если вы не захотите выбросить много памяти (64 байта для каждого независимого «блокируемого» указателя), вы не увидите значительных улучшений, если вы действительно подвергаете свое программное обеспечение стрессу. Наилучшие результаты, которые я видел до сих пор, были, когда люди сознательно подвергали риску 64b, планировали свои структуры вокруг него (упаковывая вещи, которые не будут предметом раздора), сохраняли все выравнивание на границах 64b и использовали явные барьеры для чтения и записи данных. Аннулирование строки кэша может стоить приблизительно от 20 до 100 циклов, что делает ее более серьезной проблемой, чем просто блокировка.

Кроме того, вам нужно было бы спланировать другую стратегию выделения памяти для управления либо контролируемой утечкой (если вы можете разделить код на логическую «обработку запроса» - один запрос «утечет», а затем в конце освободит всю его объем памяти), либо управление распределением данных, чтобы одна конфликтующая структура никогда не получала память, повторно реализованную элементами одной и той же структуры / коллекции (чтобы предотвратить ABA). Кое-что из этого может быть очень нелогичным, но это либо так, либо плата за GC.

1 голос
/ 26 сентября 2009

если вы используете 64 бита и ограничиваете себя объемом 1 ТБ кучи, вы можете поместить счетчик в 24 неиспользованных старших бита. если у вас есть выровненные по словам указатели, также доступны 5 нижних битов. 

int* IncrementAndRetrieve(int **ptr)
{
  int val;
  int *unpacked;
  do
  {   
    val = *ptr;
    unpacked = unpack(val);

    if(unpacked == NULL)
      return NULL;
    // pointer is on the bottom
  } while(!cas(unpacked, val, val + 1));
  return unpacked;
}
1 голос
/ 18 июля 2009

Возможно, вы ищете семейство команд cmpxchg.

Вам нужно будет предвосхитить их инструкцией блокировки, чтобы получить эквивалентное поведение.

Посмотрите здесь для быстрого обзора того, что доступно.

Скорее всего, вы получите нечто похожее на это: 

mov ecx,dword ptr [esp+4]
mov edx,dword ptr [esp+8]
mov eax,dword ptr [esp+12]
lock cmpxchg dword ptr [ecx],edx
ret 12

Вы должны прочитать этот документ ...

Редактировать

В ответ на обновленный вопрос, вы хотите сделать что-то вроде Boost shared_ptr ? Если это так, взгляните на этот код и файлы в этом каталоге - они определенно помогут вам.

0 голосов
/ 25 июля 2009

То, что вы пытаетесь сделать, не будет работать так, как вы ожидаете. То, что вы реализовали выше, можно сделать с помощью функции InterlockedIncrement (функция Win32; сборка: XADD).

Причина, по которой ваш код не выполняет то, о чем вы думаете, заключается в том, что другой поток все еще может изменять значение между вторым чтением * ptr и stwcx без аннулирования stwcx.

...