Премʼєра

Атомарність

Одна інструкція може мати вигляд однієї неподільної дії, хоча насправді нею не є. Візьмімо додавання пʼяти до значення в памʼяті:

add qword [rel counter], 5

Під капотом процесор не має способу додавати безпосередньо до памʼяті. Він розбиває цю одну інструкцію на три менші кроки, які називають мікроопераціями:

1. читання поточного значення з памʼяті;
2. зміна цього значення в регістрі, додавання до нього пʼяти;
3. запис результату назад.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

Це поширений шаблон під назвою read-modify-write (RMW).

Зауважмо, що читання (або завантаження) і запис (або збереження) є окремими подіями, тож між ними є проміжок часу. Зазвичай ми цього не помічаємо, бо на одному ядрі кожна інструкція гарантовано справляє свій ефект повністю, перш ніж почнеться наступна. Тому цей проміжок невидимий, і add поводиться як єдине ціле.

Однак сучасні процесори рідко бувають одноядерними, і застосунки часто працюють одразу на багатьох ядрах, без жодного впорядкування між ними. Коли кілька ядер працюють в один і той самий момент, інше ядро може прочитати або записати counter усередині цього проміжку, після завантаження цим ядром і перед його збереженням. Два потоки завантажують те саме старе значення, кожен додає пʼять і кожен зберігає свій результат. Відбулося два додавання, але значення зросло лише на пʼять. Одне оновлення було тихо втрачено.

Це гонка даних, поширена проблема в багатопотоковому коді.

Не кожне значення піддається такій небезпеці. Кожен потік має власні регістри й власний стек, тож значення, що зберігається в регістрі, або локальна змінна у стеку потоку, належить лише цьому потоку й не може зазнати гонки. Захисту потребує лише памʼять, яку потоки спільно використовують, як-от counter вище.

x86-64 пропонує набір інструкцій, які розвʼязують цю проблему, роблячи інструкцію неподільною. Вона поводиться як єдине ціле не лише для ядра, яке її виконує, а й для кожного іншого ядра. Операція, яка тримається як одне ціле, яку жодне інше ядро не може розділити, називається атомарною.

Атомарний обмін

Інструкція xchg міняє місцями два операнди. Операнд-призначення набуває попереднього значення операнда-джерела, а операнд-джерело набуває попереднього значення операнда-призначення. Концептуально це можна уявити як дві інструкції mov, що виконуються одночасно.

Як завжди, її можна застосувати з двома операндами-регістрами або з одним операндом у памʼяті та одним операндом-регістром:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

Коли xchg використовують з операндом у памʼяті, вона завжди атомарна.

Префікс lock

Найпоширеніший спосіб зробити інструкцію атомарною в x86-64 - додати префікс lock. Він зливає читання, зміну й запис в один неподільний крок. Це означає, що ядро утримує памʼять монопольно протягом усього процесу, тож жодне інше ядро не може прочитати чи записати це місце в проміжку.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock працює лише тоді, коли призначення розташоване в памʼяті, і лише з інструкціями, які виконують read-modify-write цієї памʼяті:

1. арифметичні операції, як-от add, sub, inc, dec, neg;
2. порозрядні операції, як-от and, or, xor, not;
3. бітові операції bts, btr, btc;
4. деякі інші спеціальні інструкції, як-от xadd і cmpxchg, описані нижче.

Обмін і додавання

Звичайна lock add оновлює памʼять, але відкидає старе значення. Часто саме старе значення й потрібне, наприклад, щоб видати кожному потоку окремий номер.

Інструкція xadd (x від exchange) повертає попереднє значення разом із додаванням. Вона записує суму в призначення, а початкове значення призначення залишає в регістрі-джерелі.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

Із префіксом lock така операція стає атомарним fetch-and-add. Коли її виконують багато потоків над одним лічильником, кожен виклик повертає різне старе значення.

Як і з lock add, лічильник зрештою дорівнює точній кількості викликів. Однак, на відміну від lock add, кожне проміжне значення теж повертається, по одному кожному виклику.

Порівняння й обмін

xadd додає, а xchg перезаписує, але жодна з них не може зробити так, щоб нове значення залежало від поточного й застосовувалося лише тоді, коли під ним нічого не змінилося. Саме це умовне оновлення й надає cmpxchg, compare-and-exchange, і воно є найзагальнішим із цих примітивів.

cmpxchg dest, src використовує rax як неявний акумулятор і порівнює його з dest:

• Якщо dest == rax, то dest = src і ZF = 1.
• Якщо dest != rax, то rax = dest і ZF = 0.

Зауважмо, що dest оновлюється лише тоді, коли дорівнює очікуваному значенню, попередньо завантаженому в rax. Ця рівність гарантує, що dest досі містить значення, з якого обчислено нове, тож оновлення на основі застарілого читання ніколи не застосовується. Саме тому cmpxchg є будівельним блоком для атомарного оновлення, яке також називають compare-and-swap (CAS):

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

Цей цикл повторів є серцем оновлень без блокувань. Проміжок між читанням і compare-and-exchange - це саме той момент, коли може втрутитися інший потік, і cmpxchg ловить це, відмовляючись зберігати значення, обчислене із застарілого читання.

Упорядкування памʼяті

Досі кожна операція торкалася однієї ділянки. Коли потоки узгоджують роботу через більш ніж одну ділянку, постає нове питання: у якому порядку записи одного потоку стають видимими іншому. Відповідь на це питання дають правила упорядкування памʼяті процесора.

У концепції коду без розгалужень ішлося про те, що сучасне ядро не перебирає інструкції по одній. Воно тримає в роботі багато інструкцій одночасно і забігає наперед там, де може. Це означає, що запис може стати видимим для інших ядер пізніше, ніж припускає програма, тоді як інструкції після нього вже виконалися наперед.

x86-64 підтримує сильне впорядкування памʼяті між звичайними завантаженнями й збереженнями, так що на кожному ядрі:

1. завантаження ніколи не переставляється після пізнішого завантаження;
2. збереження ніколи не переставляється після пізнішого збереження;
3. завантаження ніколи не переставляється після пізнішого збереження.

Єдине можливе переставляння - це коли збереження начебто завершується після пізнішого завантаження з іншої адреси.

Інструкція з префіксом lock або xchg з операндом у памʼяті є повним барʼєром: ніщо не переміщується через нього в жодному напрямку. Саме тому їх достатньо, щоб забезпечити повне впорядкування в більшості ситуацій.

Активне очікування та pause

Інструкції, які встановлюють прапорець і водночас повертають його попередній стан, називаються test-and-set. Їх можна використати як основу спінлока, щоб ядро мало монопольний доступ до якоїсь частини коду.

Ось загальний алгоритм, який використовує інструкцію xchg із двійковим прапорцем:

1. Прапорець починається зі значення 0.
2. Щоб захопити блокування, ядро міняє значення прапорця на 1.
3. Якщо повернене значення дорівнює 1, це означає, що блокування утримує інше ядро. Тоді поточне ядро чекає й намагається захопити блокування знову.
4. Якщо повернене значення дорівнює 0, це означає, що блокування було вільним. Тепер xchg встановила його в 1, і інші ядра чекатимуть, доки поточне ядро його не звільнить.
5. Коли поточне ядро завершує роботу, оновлення прапорця значенням 0 звільняє блокування.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

Інструкція pause у циклі очікування не змінює того, що обчислює код. Вона підказує процесору, що це активне очікування. Тоді процесор може зменшити споживання енергії для потоку, що чекає, і поступитися сусідньому потоку, який ділить із ним те саме ядро. Цикл активного очікування без pause усе одно правильний, просто марнотратний.

Коли потік завершує роботу, він може звільнити блокування звичайним збереженням 0 за допомогою mov. Більше нічого, крім mov, не потрібно, бо в x86-64 завантаження й збереження ніколи не переставляються після пізнішого збереження. Про збереження, яке ніколи не обганяє попередні звернення, кажуть, що воно має release ordering, і на x86 кожне звичайне збереження його має.