CHESS и store buffer vulnerability
От: Mr.Cat  
Дата: 04.06.10 22:14
Оценка:
Анализирую сабжем одну программку и получаю сабж. Суть такова (от кода оставлена только концепция, мог слегка лажануть — но реальный код по всем признакам рабочий).

Есть некий глобальный объект.
volatile object globalOne = ...

Иногда он модифицируется вот таким вот одноразовым методом одноразового инстанса (т.е. инстанс создается на 1 модификацию и метод вызывается единожды):
class ObjectMutator
{
  volatile object oldOne;
  volatile object newOne;
  volatile bool completed = false;

  void Mutate()
  {
    oldOne = globalOne;
    globalOne = this;
    newOne = f(...);
    completed = true; //3
    globalOne = newOne; //1
  }
}

И читается он тоже иногда — вот так вот:
var current = globalOne; //2
if(globalOne is ObjectMutator)
{
  var mutator = (ObjectMutator)globalOne;
  return mutator.completed ? mutator.newOne : mutator.oldOne;
}
else
  return current;

CHESS видит store buffer vulnerability и указывает на строки 1 и 2, при этом перестает ругаться, если 1 заменить на
Interloked.CompareExchange(ref globalOne, newOne, this);

Возникает вопрос, в чем заключается этот самый store buffer vulnerability и почему он исчезает при использовании cas.

Поковырявшись в гугле я родил предположение, что теоретически мутатор может совсем не опубликовать свою мутацию — отложить всю свою запись до следующей среды — и будет прав. А Interlocked-операции заставляют его-таки что-нибудь опубликовать.

Фишка в том, что обычно задержку публикации приводят как раз как пример использования volatile (который тут и так есть), а не cas. И кому в итоге верить? В принципе, я больше верю CHESS. Таки согласно ecma, volatile имеет отношение только к упорядочиванию (типа "если наш volatile read увидел эффект вашего volatite write, то...").
Re: CHESS и store buffer vulnerability
От: drol  
Дата: 05.06.10 09:06
Оценка: 10 (1)
Здравствуйте, Mr.Cat, Вы писали:

MC>от кода оставлена только концепция, мог слегка лажануть — но реальный код по всем признакам рабочий


Э-э-э... Так на концепцию-то CHESS ругается ? Или только на реальный код ?

MC>Возникает вопрос, в чем заключается этот самый store buffer vulnerability


Согласно спецификации volatile, в последовательности "запись в volatile-поле A; чтение из volatile-поля B" оные операции могут подвергаться реордерингу. Вот простой пример store buffer vulnerability:

volatile bool isIdling;
volatile bool hasWork;
   
   //Consumer thread
   void BlockOnIdle(){
      lock (condVariable){
         isIdling = true;
         if (!hasWork)
             Monitor.Wait(condVariable);
         isIdling = false;
      }
   }
   
   //Producer thread
   void NotifyPotentialWork(){
      hasWork = true;
      if (isIdling)
         lock (condVariable) {
            Monitor.Pulse(condVariable);
         }   
   }

*Producer может "не увидеть" isIdling, и посчитать что Consumer занят, тогда как тот курит.

В Вашей "концепции" есть только одно похожее место:
completed = true; //3
globalOne = newOne; //1

Здесь идёт запись в completed, а потом чтение newOne.

В //2 же вообще какой-то ужос. Вы три(!) раза подряд читаете globalOne — он вообще не ObjectMutator уже давно может быть, а Вы его кастуете. Вы уверены в соответствии "концепции" реальному коду ?

MC>и почему он исчезает при использовании cas.


Ну это-то очевидно. Interlocked.CompareExchange — атомарная операция, да ещё и с полным барьером => чтения volatile-поля больше нет.

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


Никто ничего не откладывает. Вопрос только в том, какой порядок выполнения операций будет наблюдаться другими потоками.

MC>Фишка в том, что обычно задержку публикации приводят как раз как пример использования volatile (который тут и так есть), а не cas.


Вы это о чём ? Можно пример ?
Re: CHESS и store buffer vulnerability
От: drol  
Дата: 05.06.10 09:13
Оценка:
Кстати, а зачем вообще такая жуть порождена ? globalOne ведь volatile, все операции с ним атомарны, надо сменить значение — берёте и тупо проставляете.
Re[2]: CHESS и store buffer vulnerability
От: Mr.Cat  
Дата: 05.06.10 11:40
Оценка:
Здравствуйте, drol, Вы писали:
D>В //2 же вообще какой-то ужос. Вы три(!) раза подряд читаете globalOne — он вообще не ObjectMutator уже давно может быть, а Вы его кастуете. Вы уверены в соответствии "концепции" реальному коду ?
Да, там ошибка, должно быть одно чтение в current и дальнейшее неиспользование globalOne.
Re[2]: CHESS и store buffer vulnerability
От: Mr.Cat  
Дата: 05.06.10 11:45
Оценка:
Здравствуйте, drol, Вы писали:
D>Э-э-э... Так на концепцию-то CHESS ругается ?
Не проверял
Re[2]: CHESS и store buffer vulnerability
От: Mr.Cat  
Дата: 05.06.10 11:50
Оценка:
Здравствуйте, drol, Вы писали:
D>Кстати, а зачем вообще такая жуть порождена ? globalOne ведь volatile, все операции с ним атомарны, надо сменить значение — берёте и тупо проставляете.
В реальной программе несколько globalOne и несколько писателей — жуть призвана апдейты нескольких globalOne сделать атомарными.
Re[2]: CHESS и store buffer vulnerability
От: Mr.Cat  
Дата: 05.06.10 12:05
Оценка:
Здравствуйте, drol, Вы писали:
D>В Вашей "концепции" есть только одно похожее место:
D>
D>completed = true; //3
D>globalOne = newOne; //1
D>

D>Здесь идёт запись в completed, а потом чтение newOne.
Хм, спасибо, не заметил. Осталось перечитать доки по модели памяти и понять, на что это может влиять.
Re[3]: CHESS и store buffer vulnerability
От: Jolly Roger  
Дата: 06.06.10 03:45
Оценка:
Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, drol, Вы писали:

D>>В Вашей "концепции" есть только одно похожее место:
D>>
D>>completed = true; //3
D>>globalOne = newOne; //1
D>>

D>>Здесь идёт запись в completed, а потом чтение newOne.
MC>Хм, спасибо, не заметил. Осталось перечитать доки по модели памяти и понять, на что это может влиять.

В спецификации C# приводится такой пример для демонстрации volatile, похожий на Вашу ситуацию:

Пример

using System;
using System.Threading;
class Test
{
    public static int result;   
    public static volatile bool finished;
    static void Thread2() {
        result = 143;    
        finished = true; 
    }
    static void Main() {
        finished = false;
        // Запуск Thread2() в новом потоке
        new Thread(new ThreadStart(Thread2)).Start();
        // Дождаться, пока Thread2 не сообщит о наличии result установкой
        // finished в true.
        for (;;) {
            if (finished) {
                Console.WriteLine("result = {0}", result);
                return;
            }
        }
    }
}

дает на выходе :
result = 143
В этом примере метод Main запускает новый поток, выполняющий метод Thread2. Этот метод сохраняет значение в поле не-volatile с именем result, затем сохраняет true в поле volatile с именем finished. Главный поток дожидается, пока поле finished не будет установлено в true, затем читает поле result. Так как finished объявлено как volatile, главный поток должен прочитать значение 143 из поля result. Если бы поле finished не было объявлено как volatile, то сохранение в result могло быть видимым в главном потоке после сохранения в finished, и главный поток мог прочитать значение 0 из поля result. Объявление finished как поля volatile предотвращает все такие несогласованности.


Однако (и в Вашей недавней ветке это обсуждалось), результат такого кода на многопроцессорной системе оказывается нестабильным по причине, видимо, отсутствия связи между присвоением значений completed и globalOne, что позволяет процессору разложить эти операции по разным конвейерам, а тогда очерёдность их выполнения оказывается зависимой от случайных факторов.

MC>если 1 заменить на

MC>
Interloked.CompareExchange(ref globalOne, newOne, this);


Тут ещё, возможно, сказывается тот факт, что к этому моменту globalOne может содержать уже не данный объект, а совсем другой экземпляр ObjectMutator, помещённый туда другим потоком, а это может означать, что newOne уже устарела. CompareExchange как раз избавляет от такой опасности.
"Нормальные герои всегда идут в обход!"
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.