Стало интересно, как же именно достигается атомарность операций. Кому интересно — добро пожаловать под кат.
Атомарные операции — операции, выполняющиеся как единое целое либо не выполняющиеся вовсе. Т. е. это операция, во время исполнения которой данные, читаемые/изменяемые этой операцией не могут быть изменены другой операцией. Есть специальные ассемблерные команды, которые указывают процессору, что операция будет атомарной. Есть несколько типов команд, с помощью которых можно добиться атомарности: load-link and store-conditional (LL/SC), compare-and-swap (CAS) и другие.
Примеры команд LL/SC:
ldl_l/stl_c и ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM version 6 and above).
Команды даны парами, т. к. первая загружает текущее значение операнда в регистр или другое контролируемое место, вторая сохраняет новое значение в операнд, если операнд за промежуток между 1-ой и 2-ой не изменился. Вместе они гарантируют, что все команды между ними работают с одной версией операнда, которая была загружена с помощью LL. Для примера возьмем пару lwarx/stwcx (PowerPC):
Код взят отсюда.
В 6-ой регистр загружаются данные из операнда и он(операнд) резервируется. Потом в 6-ом регистре получаем сумму операнда и incr. В конце выгружаем из регистра полученную сумму в операнд и отпускаем его. Если в промежуток между резервированием и освобождением операнда его значение будет изменено где-то еще помимо текущей операции(даже если было присвоено тоже самое значение, которое уже хранилось в операнде), то мы получим ошибку. Это проверяет 5-я строка, запускающая операцию снова в случае ошибки.
Принцип работы простой — смотрим, какое значение хранится в операнде. Если оно то, какое мы ожидаем, то меняем его на новое.
Алгоритм:
Расширение CAS — Double Compare And Swap (CAS2). Даются указатели на две независимые переменные вместо одной, соответственно, два ожидаемых значения и два новых значения для каждой переменной соответственно.
Но эта группа команд более «слабая», чем LL/SC, т. к. возможна ситуация:
начальные условия: compare_and_swap( reg, 5, 7 ) и *reg = 5;
1) int old_reg_val = *reg; (old_reg_val = 5)
2) другая операция делает *reg = 42; funny_stuff; *reg = 5;
3) if (old_reg_val == oldval) — утверждение верно, хотя произошло два изменения значения переменной. Т. е. произошло изменение, но наша операция об этом не знает. Эта ситуация называется ABA problem.
Есть много методов обхода этой проблемы. Мне показался интересным метод с использованием Double-Word Compare-And-Swap (часто путается с Double Compare And Swap).
Пример:
Код взят отсюда.
Префикс «lock;» означает, что шина доступа к памяти может быть использована только следующей за ней командой.
В передаваемом слове содержится указатель на память с требуемым значением и ABA номер, который изменяется с каждой операцией (увидел это в одном из патентов).
Обычно это сложение или инкрементация.
Примеры команд: addl(i386), xaddl(x86).
Вот реализация атомарного сложения из википедии:
На некоторых архитектурах префикс «lock;» не нужна. Пример — инкрементирование на Итаниуме (взят отсюда):
Кстати, инкремент, декремент, +=, -= в С++ атомарные (по крайней мере на х86 и х86_64). Префикса «lock;» нет, так что атомарности тоже нет. Атомарные операции появились в С++11.
компилируется в
Для декремента будет subl.
Q: Это известно каждому школьнику! Зачем об этом писать?
A: Мне было интересно, как же оно работает. Представлял только, что там есть какие-то lock'и. Надеюсь, это было интересно еще кому-то.
Q: В статье куча ошибок и неточностей.
A: Пишите, с радостью исправлю.
Q: Что? Уже заключение? Где сама статья? Где MSI, Cache Coherence и %еще_куча_умных_слов%?
A: Я не копал глубоко. Надеюсь, об этом напишут люди, которые знают эти темы.
UPD: За исправления спасибо lesha_penguin и TheShade.
Атомарные операции — операции, выполняющиеся как единое целое либо не выполняющиеся вовсе. Т. е. это операция, во время исполнения которой данные, читаемые/изменяемые этой операцией не могут быть изменены другой операцией. Есть специальные ассемблерные команды, которые указывают процессору, что операция будет атомарной. Есть несколько типов команд, с помощью которых можно добиться атомарности: load-link and store-conditional (LL/SC), compare-and-swap (CAS) и другие.
1. LL/SC
Примеры команд LL/SC:
ldl_l/stl_c и ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM version 6 and above).
Команды даны парами, т. к. первая загружает текущее значение операнда в регистр или другое контролируемое место, вторая сохраняет новое значение в операнд, если операнд за промежуток между 1-ой и 2-ой не изменился. Вместе они гарантируют, что все команды между ними работают с одной версией операнда, которая была загружена с помощью LL. Для примера возьмем пару lwarx/stwcx (PowerPC):
void atomic_incr(int * operand, int incr)
{
asm volatile (
"loop:\n\t" /* repeat until this succeeds */
"lwarx 6,0,%0\n\t" /* reserve the operand */
"add 6,6,%1\n\t" /* add incr to it */
"stwcx. 6,0,%0\n\t" /* put the sum back, and release it */
"bne- loop" /* start-over on failure */
:
: "r" (operand), "r" (incr)
: "r6"
);
}Код взят отсюда.
В 6-ой регистр загружаются данные из операнда и он(операнд) резервируется. Потом в 6-ом регистре получаем сумму операнда и incr. В конце выгружаем из регистра полученную сумму в операнд и отпускаем его. Если в промежуток между резервированием и освобождением операнда его значение будет изменено где-то еще помимо текущей операции(даже если было присвоено тоже самое значение, которое уже хранилось в операнде), то мы получим ошибку. Это проверяет 5-я строка, запускающая операцию снова в случае ошибки.
Ассемблерные параметры gcc
Пример:
: "=r" (val), "=m" (*mem)
: «0» (val), «m» (*mem)
: «memory», «cc»);
Первая строка — выходные параметры.
"=r" (val) — %0 является константой или операндом. gcc должен использовать любой регистр для %0.
"=m" (*mem) — %1 является переменной в памяти, которую gcc должен использовать для записи результата (mem — указатель на эту переменную).
Вторая строка — входные параметры.
«0» (val) — 0 означает, что должен использоваться такой же регистр, что и в выходных параметрах и в него должно быть загружено значение из переменной.
«m» (*mem) — «m» означает то же, что и "=m", только отсутствие знака "=" говорит, что происходит чтение.
Третья строка — что будет изменено инструкциями.
«memory» — будет изменена память.
«cc» — «condition code register». Это означает, что будут изменены флаги процессора.
Подробнее можно прочитать здесь.
: "=r" (val), "=m" (*mem)
: «0» (val), «m» (*mem)
: «memory», «cc»);
Первая строка — выходные параметры.
"=r" (val) — %0 является константой или операндом. gcc должен использовать любой регистр для %0.
"=m" (*mem) — %1 является переменной в памяти, которую gcc должен использовать для записи результата (mem — указатель на эту переменную).
Вторая строка — входные параметры.
«0» (val) — 0 означает, что должен использоваться такой же регистр, что и в выходных параметрах и в него должно быть загружено значение из переменной.
«m» (*mem) — «m» означает то же, что и "=m", только отсутствие знака "=" говорит, что происходит чтение.
Третья строка — что будет изменено инструкциями.
«memory» — будет изменена память.
«cc» — «condition code register». Это означает, что будут изменены флаги процессора.
Подробнее можно прочитать здесь.
2. CAS
Принцип работы простой — смотрим, какое значение хранится в операнде. Если оно то, какое мы ожидаем, то меняем его на новое.
Алгоритм:
int compare_and_swap (int* reg, int oldval, int newval)
{
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
return old_reg_val;
}Расширение CAS — Double Compare And Swap (CAS2). Даются указатели на две независимые переменные вместо одной, соответственно, два ожидаемых значения и два новых значения для каждой переменной соответственно.
Но эта группа команд более «слабая», чем LL/SC, т. к. возможна ситуация:
начальные условия: compare_and_swap( reg, 5, 7 ) и *reg = 5;
1) int old_reg_val = *reg; (old_reg_val = 5)
2) другая операция делает *reg = 42; funny_stuff; *reg = 5;
3) if (old_reg_val == oldval) — утверждение верно, хотя произошло два изменения значения переменной. Т. е. произошло изменение, но наша операция об этом не знает. Эта ситуация называется ABA problem.
Есть много методов обхода этой проблемы. Мне показался интересным метод с использованием Double-Word Compare-And-Swap (часто путается с Double Compare And Swap).
Пример:
/* double-compare-and-swap: atomically sets the two-word data at address @mem
* to the two-word value of @new if value at @mem
* equals @old
* @mem: pointer to value
* @old: old value
* @new: new value
*
* returns: 0 on failure, non-zero on success */
static inline
char DWCAS(volatile DWORD *mem, DWORD old, DWORD new)
{
char r = 0;
unsigned long old_h = old >> SHIFT, old_l = old;
unsigned long new_h = new >> SHIFT, new_l = new;
__asm__ __volatile__("lock; " CMPXCHGxB " (%6);"
"setz %7; "
: "=a" (old_l),
"=d" (old_h)
: "0" (old_l),
"1" (old_h),
"b" (new_l),
"c" (new_h),
"r" (mem),
"m" (r)
: "cc", "memory");
return r;
}Код взят отсюда.
Префикс «lock;» означает, что шина доступа к памяти может быть использована только следующей за ней командой.
В передаваемом слове содержится указатель на память с требуемым значением и ABA номер, который изменяется с каждой операцией (увидел это в одном из патентов).
3. Простые атомарные операции.
Обычно это сложение или инкрементация.
Примеры команд: addl(i386), xaddl(x86).
Вот реализация атомарного сложения из википедии:
void atomic_add(int * operand, int incr)
{
asm volatile (
"lock; xaddl %1, (%0)\n" // add incr to operand
: // no output
: "r" (operand), "r" (incr)
);
}На некоторых архитектурах префикс «lock;» не нужна. Пример — инкрементирование на Итаниуме (взят отсюда):
void atomic_oneup(int * operand)
{
uint64_t res; // this MUST be 64 bits
asm volatile (
"fetchadd4.rel %0=%1,%2"
: "=r" (res)
: "m" (*operand), "i" (1)
: "memory"
);
}int a =0;
++a;компилируется в
c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp)
83 45 fc 01 addl $0x1,-0x4(%rbp)Для декремента будет subl.
Заключение
Q: Это известно каждому школьнику! Зачем об этом писать?
A: Мне было интересно, как же оно работает. Представлял только, что там есть какие-то lock'и. Надеюсь, это было интересно еще кому-то.
Q: В статье куча ошибок и неточностей.
A: Пишите, с радостью исправлю.
Q: Что? Уже заключение? Где сама статья? Где MSI, Cache Coherence и %еще_куча_умных_слов%?
A: Я не копал глубоко. Надеюсь, об этом напишут люди, которые знают эти темы.
UPD: За исправления спасибо lesha_penguin и TheShade.