пятница, 26 апреля 2013 г.

Атомарные операции

Буквально на днях ко мне обратились с вопросом.

А зачем нужен префикс LOCK, или его аналог InterlockedDecrement при вызове процедуры _LStrClr из модуля System. Данная процедура декрементирует счетчик ссылок строки и при его обнулении освобождает память, ранее занятую строкой.

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

В принципе предпосылка интересная, но...


Но ведь мы передаем строку в класс нити.
Это как минимум приводит к увеличению refCnt, а стало быть мы можем "попасть" на MemLeak в том случае, если бы не использовались атомарные операции при декременте счетчика ссылок.

Это демонстрирует нам код _LStrClr

procedure _LStrClr(var S);
{$IFDEF PUREPASCAL}
var
  P: PStrRec;
begin
  if Pointer(S) <> nil then
  begin
    P := Pointer(Integer(S) - Sizeof(StrRec));
    Pointer(S) := nil;
    if P.refCnt > 0 then
      if InterlockedDecrement(P.refCnt) = 0 then
        FreeMem(P);
  end;
end;
{$ELSE}
asm
        { ->    EAX pointer to str      }

        MOV     EDX,[EAX]                       { fetch str                     }
        TEST    EDX,EDX                         { if nil, nothing to do         }
        JE      @@done
        MOV     dword ptr [EAX],0               { clear str                     }
        MOV     ECX,[EDX-skew].StrRec.refCnt    { fetch refCnt                  }
        DEC     ECX                             { if < 0: literal str           }
        JL      @@done
   LOCK DEC     [EDX-skew].StrRec.refCnt        { threadsafe dec refCount       }
        JNE     @@done
        PUSH    EAX
        LEA     EAX,[EDX-skew].StrRec.refCnt    { if refCnt now zero, deallocate}
        CALL    _FreeMem
        POP     EAX
@@done:
end;
{$ENDIF}

В случае использования неатомарного декремента инструкция JNE  @@done имеет огромный шанс выполниться не верно. (И она действительно выполнится не верно, если убрать LOCK префикс).

Я конечно пробовал объяснить данную ситуацию примерами из интеловского мануала, где объясняется работа, но в итоге решил реализовать следующий пример (которым и смог убедить автора вопроса):

program interlocked;

{$APPTYPE CONSOLE}

uses
  Windows;

const
  Limit = 1000000;
  DoubleLimit = Limit shl 1;

var
  SameGlobalVariable: Integer;

function Test1(lpParam: Pointer): DWORD; stdcall;
var
  I: Integer;
begin
  for I := 0 to Limit - 1 do
  asm
    lea eax, SameGlobalVariable
    inc [eax] // обычный инкремент
  end;
end;

function Test2(lpParam: Pointer): DWORD; stdcall;
var
  I: Integer;
begin
  for I := 0 to Limit - 1 do
  asm
    lea eax, SameGlobalVariable
    lock inc [eax] // атомарный инкремент
  end;
end;

var
  I: Integer;
  hThread: THandle;
  ThreadID: DWORD;
begin
  // Неатомарное увеличение значения переменной SameGlobalVariable
  SameGlobalVariable := 0;
  hThread := CreateThread(nil, 0, @Test1, nil, 0, ThreadID);
  for I := 0 to Limit - 1 do
  asm
    lea eax, SameGlobalVariable
    inc [eax] // обычный инкремент
  end;
  WaitForSingleObject(hThread, INFINITE);
  CloseHandle(hThread);
  if SameGlobalVariable <> DoubleLimit then
    Writeln('Step one failed. Expected: ', DoubleLimit, ' but current: ', SameGlobalVariable);

  // Атомарное увеличение значения переменной SameGlobalVariable
  SameGlobalVariable := 0;
  hThread := CreateThread(nil, 0, @Test2, nil, 0, ThreadID);
  for I := 0 to Limit - 1 do
  asm
    lea eax, SameGlobalVariable
    lock inc [eax] // атомарный инкремент
  end;
  WaitForSingleObject(hThread, INFINITE);
  CloseHandle(hThread);
  if SameGlobalVariable <> DoubleLimit then
    Writeln('Step two failed. Expected: ', DoubleLimit, ' but current: ', SameGlobalVariable);

  Readln;
end.

Суть примера - есть некая глобальная переменная SameGlobalVariable (она выступает в роли счетчика ссылок строки из изначальной постановки задачи) и выполняются изменения ее значения в обычном и атомарном режимах с использованием нити.

Здесь наглядно видно различия между двумя режимами работы.
В консоли вы увидите примерно следующее:
Step one failed. Expected: 2000000 but current: 1018924
Ошибки по второму варианту реализации вы не увидите никогда :)

Кстати первый вариант может использоваться в качестве достаточно хорошего рандомизатора (о котором я говорил в предыдущих статьях).

Резюмируя:

Анализ исходного кода системных модулей Delphi и VCL в частности, иногда может вам дать гораздо больше информации, чем предположения о том как оно работает на самом деле и это факт, но...



 Нет, это не факт, это больше чем факт — так оно и было на самом деле ©

---

© Александр (Rouse_) Багель
Апрель, 2013

8 комментариев:

  1. Как интересно, всегда казалось что булевы и интежер переменные потокобезопасны для кода типа inc SameGlobalVariable, потому что занимают одну команду процессора. Пошел вычитывать старый код. Спасибо.

    ОтветитьУдалить
    Ответы
    1. По всей видимости имелась ввиду не "одна команда", а "один такт процессора". На самом деле это не совсем так, данное поведение присуще инструкции "rw INC r16" или "rd INC r32" (опкод 0х40), а здесь мы имеем на руках INC r/m32 (опкод 0xFF), которая выполняется за три такта (чтение, модификация, запись), о чем нам и говорят интеловские мануалы :)

      Удалить
    2. Да, понятно что несколько тактов, просто сам факт что процессор будет переключать контекст между потоками на середине выполнения инструкции оказался неожидан. Всегда думал что инструкции выполняются атомарно, т.е. если на нее треба 3 такта, то пока они все не пройдут контекст меняться не будет. Глупое заблуждение, ведь если подумать, то приходится переключаться постоянно, хотя бы что бы подгрузить страницу из свопа если она не доступна, или откопировать память в другое место если она copy on write (а она именно такая для глобальных переменных). Два мне за матчасть)

      Удалить
    3. Ну здесь бОльшую роль играет кэш процессора.
      А вообще есть штатная инструкция для переключения контекста - NOP :)
      Правда это не сильно документированно, но в кратце упоминается в документации, а так-же пару раз было озучено на "Intel Developer Forum".

      Удалить
    4. Любопытно. Погонял этот тест на одном ядре, никаких нарушений. Похоже только на многопроцессорных системах не атомарно выполняется данная команда. На виртуалках с одним ядром и двумя можно наглядно поиграться. Практической пользы это знание не несет, все равно надо везде через локеры работать. Собственно, наверно я когда-то давно тестировал многопоточное инкрементирование, делал это на старом одноядерном p4, и так и запомнилось что атомарная она, и локеры не обязательно использовать. Чудо просто что я на этот баг в своей памяти ни разу не напоролся)

      Удалить
    5. >> Любопытно. Погонял этот тест на одном ядре, никаких нарушений.
      Ну так оно и понятно :) Доступ к данным, на одном ядре, в любом случае последовательный идет, а работа нити "эмулируется" (не знаю как правильно это назвать) :)

      Удалить
  2. А что за параметр skew в ассемблерной части?
    И есть ли ещё в ассемблере Delphi7 какие-то малоизвестные (псевдо-)константы?

    ОтветитьУдалить
    Ответы
    1. Это константа.
      skew = SizeOf(StrRec);
      Все такие вещи можно подглядеть в system.pas

      Удалить