Атомарні операції у

Про концепцію Атомарні операції

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

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

Це поширена схема під назвою читання-зміна-запис (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 використовує для інших інструкцій, про який ітиметься далі.

Префікс lock

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

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

lock працює лише з памʼяттю як приймачем і лише з інструкціями, які читають, змінюють і записують цю памʼять:

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

З будь-якою іншою інструкцією, як-от звичайний mov, цей префікс недійсний, і процесор спричиняє збій через недійсний код операції. Окреме завантаження чи окреме збереження не потребує префікса: природно вирівняний доступ і сам уже атомарний.

Атомарні бітові операції

Серед інструкцій, які можна блокувати, перевірки бітів природно поєднуються зі спінлоком у кінці цього документа. Кожна з bts, btr і btc копіює один вибраний біт у прапорець перенесення, а потім установлює, очищає або перемикає його. З префіксом lock це перетворюється на однобітове читання-зміну-запис: біт змінюється атомарно, а CF повідомляє, яким він був до того.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

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

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

Звичайний 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 це атомарне додавання з поверненням. Якщо його викликають багато потоків на тому самому лічильнику, кожен виклик повертає інше старе значення.

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

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

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

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

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

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

Акумулятор відповідає розміру операнда: al для байта, далі ax, eax і rax для ширших форм.

Зауважмо, що dest оновлюється лише тоді, коли він дорівнює очікуваному значенню, попередньо завантаженому в rax. Ця рівність гарантує, що dest усе ще містить значення, з якого обчислено нове, тож оновлення на основі застарілого читання ніколи не застосовується. Це робить cmpxchg будівельним блоком для атомарного оновлення, відомого також як порівняння з обміном (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

Цей цикл повторних спроб лежить в основі оновлень без блокувань. Інший потік може втрутитися саме в проміжку між читанням і порівнянням з обміном, і cmpxchg ловить це, відмовляючись зберігати значення, обчислене із застарілого читання.

Варто знати одну тонкість. cmpxchg перевіряє, що значення дорівнює прочитаному, а не те, що комірки ніхто не торкався. Якщо інший потік усередині цього проміжку переведе значення з A в B і назад у A, обмін все одно вдасться, хоч світ під ним і змінився.

Для звичайного лічильника це нешкідливо, бо однакова кількість годиться так само добре. Для адреси памʼяті на початку списку без блокувань це не так, бо та сама адреса тепер може вести в інше місце. Це проблема ABA.

Звично цю проблему розвʼязують так: значення поєднують із певною «позначкою», наприклад із лічильником, який лише зростає. Оскільки позначка лише просувається вперед, збіг позначок доводить, що комірки між тим не торкалися, а не лише те, що вона має такий самий вигляд.

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

Є інструкція подвійної ширини cmpxchg16b, семантично така сама, як cmpxchg, але працює одразу з 16 байтами й годиться для цієї ситуації. Вона не має операнда-джерела, а використовує rcx:rbx як значення-замінник. Її єдиний операнд має бути коміркою памʼяті, вирівняною на 16 байтів. Ця інструкція також використовує rdx:rax як акумулятор, а не лише rax.

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

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

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

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

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

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

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

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

Цього єдиного розриву досить, щоб зламати рукостискання, побудоване за схемою «запис, потім перевірка». Якщо два потоки записують кожен свій прапорець, а потім читають прапорець іншого, обидва читання можуть повернутися з невстановленим значенням, бо жодне із збережень ще не покинуло свій буфер запису. Інструкція mfence закриває цей розрив, спорожнюючи буфер запису: кожен запис перед нею стає видимим раніше за будь-яке читання після неї.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

Існують також два вужчі барʼєри:

• sfence упорядковує записи між собою й важливий переважно з потоковими, нетемпоральними збереженнями;
• lfence упорядковує читання.

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

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

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

Інструкції, які встановлюють прапорець і водночас повертають його попередній стан, називають перевіркою з установленням. На їхній основі будують спінлок, який гарантує ядру монопольний доступ до певної частини коду.

Ось загальний алгоритм, що використовує інструкцію 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 усе ще правильний, просто марнотратний.

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

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

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

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