Знание об управлении потоками, которое мы получили в прошлом топике, конечно, велико, но вопросов остаётся всё равно много. Например: «Как работает happens-before?», «Правда ли, что volatile
— это сброс кешей?», «Зачем вообще было городить какую-то модель памяти? Нормально же всё было, что началось-то такое?»
Как и прошлая статья, эта построена по принципу «сначала кратко опишем, что должно происходить в теории, а потом отправимся в исходники и посмотрим, как это происходит там». Таким образом, первая часть во многом применима не только к Java, а потому и разработчики под другие платформы могут найти для себя что-то полезное.
Теоретический минимум
Всё возрастающая производительность железа возрастает не просто так. Инженеры, которые разрабатывают, скажем, процессоры, придумывают множество разнообразных оптимизаций, позволяющих выжать из вашего кода ещё больше абстрактных попугаев. Однако бесплатной производительности не бывает, и в этом случае ценой оказывается возможная контринтуитивность того, как выполняется ваш код. Разнообразных особенностей железа, скрытых от нас абстракциями, очень много. Рекомендую тем, кто этого ещё не сделал, ознакомиться с докладом Сергея Walrus Куксенко, который называется «Quantum Performance Effects» и отлично демонстрирует, как неожиданно ваши абстракции могут протечь. Мы не будем далеко ходить за примером, и взглянем на кеши.
Устройство кешей
Запрос к «основной памяти» — операция дорогая, и даже на современных машинах может занимать сотни наносекунд. За это время процессор мог бы успеть выполнить уйму инструкций. Чтобы избежать непотребства в виде вечных простоев, используются кеши. Простыми словами, процессор хранит прямо рядом с собой копии часто используемого содержимого основной памяти. Более сложными словами о различных типах кешей и их иерархиях можно почитать тут тут, а нас больше интересует то, как гарантируется актуальность данных в кеше. И если в случае с одним процессором (или ядром, в дальнейшем будет использоваться термин процессор) никаких проблем, очевидно, нет, то при наличии нескольких ядер (YAY MULTITHREADING!) уже начинают возникать вопросы.
Как процессор A может знать, что процессор B поменял какое-то значение, если у A оно закешировано?
Или, иными словами, как обеспечить когерентность кешей?
Для того, чтобы различные процессоры имели согласованную картину мира, они должны некоторым образом общаться между собой. Правила, которым они в этом общении следуют, называют протоколом когерентности кешей.
Протоколы когерентности кешей
Разнообразных протоколов существует много, и варьируются они не только от производителя железа к производителю железа, но и постоянно развиваются даже в рамках одного вендора. Тем не менее, несмотря на обширность мира протоколов, у большинства из них есть некоторые общие моменты. Несколько умаляя общность, будем рассматривать протокол MESI. Конечно, есть и подходы, которые кардинальным образом от него отличаются: например, Directory Based. Однако, в рамках данной статьи они не рассматриваются.
В MESI же каждая ячейка в кеше может находиться в одном из четырёх состояний:
- Invalid: значения нет в кеше
- Exclusive: значение есть только в этом кеше, и оно пока не было изменено
- Modified: значение изменено этим процессором, и оно пока не находится ни в главной памяти, ни в кеше какого-либо другого процессора
- Shared: значение присутствует в кеше более чем у одного процессора
Для перехода из состояния происходит обмен сообщениями, формат которого так же является частью протокола. Кстати, довольно иронично, что на столь низком уровне смена состояний происходит именно через обмен сообщениями. Problem, Actor Model Haters?
В целях уменьшения объёма статьи и побуждения читателя к самостоятельному изучению, я не буду описывать обмен сообщениями в деталях. Желающие могут выудить эту информацию, например, в замечательной статье Memory Barriers: a Hardware View for Software Hackers. Традиционно, более глубокие размышления на тему от cheremin можно почитать в его блоге.
Ловко пропустив описание самих сообщений, сделаем относительно них два замечания. Во-первых, сообщения доставляются не моментально, в результате чего мы получаем latency на смену состояния. Во-вторых, некоторые сообщения требуют особой обработки, приводящей к простою процессора. Всё это приводит к различным проблемам масштабируемости и производительности.
Оптимизации для MESI и проблемы, которые они порождают
Store Buffers
Для того, чтобы что-то записать в ячейку памяти, находящуюся в состоянии Shared, необходимо отослать сообщение Invalidate и дождаться того, как все его подтвердят. Всё это время процессор будет простаивать, что невероятно печально, поскольку время, в течение которого дойдёт сообщение, как правило на несколько порядков выше, чем необходимо для выполнения простых инструкций. Чтобы избежать такой бессмысленной и беспощадной потери процессорного времени, придумали Store Buffers. Процессор помещает значения, которые хочет записать, в этот буфер и продолжает выполнять инструкции. А когда получены необходимые Invalidate Acknowledge, данные наконец отправляются в основную память.
Разумеется, тут есть несколько подводных граблей. Первые из них весьма очевидны: если до того, как значение покинет буфер, этот же процессор попытается его прочитать, он получит совсем не то, что только что записал. Это решается с помощью Store Forwarding: всегда проверяется, а не находится ли запрашиваемое значение в буфере; и если оно там, то значение берётся именно оттуда.
А вот вторые грабли уже куда более интересны. Никто не гарантирует, что если в store buffer ячейки были помещены в одном порядке, то и записаны они будут в том же порядке. Рассмотрим следующий кусочек псевдокода:
void executedOnCpu0() {
value = 10;
finished = true;
}
void executedOnCpu1() {
while(!finished);
assert value == 10;
}
Казалось бы, что может пойти не так? Вопреки тому, как можно подумать, многое. Например, если окажется так, что к началу выполнения кода finished
находится у Cpu0 в состоянии Exclusive, а value
— в состоянии, например, Invalid, то value
покинет буфер позже, чем finished
. И вполне возможно, что Cpu1 прочитает finished
как true
, а value
при этом окажется не равным 10. Такое явление называют reordering. Разумеется, reordering происходит не только в таком случае. Например, компилятор из каких-либо своих соображений вполне может поменять местами некоторые инструкции.
Invalidate Queues
Как можно легко догадаться, store buffers не бесконечны, и потому имеют тенденцию переполняться, в результате чего всё же приходится зачастую ждать Invalidate Acknowledge. А они иногда могут выполняться очень долго, если процессор и кеш заняты. Решить эту проблему можно, введя новую сущность: Invalidate Queue. Все запросы на инвалидацию ячеек памяти будут помещаться в эту очередь, а acknowledgement будет отправляться моментально. Фактически же значения будут инвалидированы тогда, когда процессору это будет удобно. При этом процессор обещает вести себя хорошо, и не будет отправлять никаких сообщений по этой ячейке до тех пор, пока её не инвалидирует. Чуете подвох? Вернёмся к нашему коду.
void executedOnCpu0() {
value = 10;
finished = true;
}
void executedOnCpu1() {
while(!finished);
assert value == 10;
}
Предположим, что нам повезло (или мы воспользовались неким тайным знанием), и Cpu0 записал ячейки памяти в нужном нам порядке. Гарантирует ли это то, что они попадут в кеш Cpu1 в том же порядке? Как вы уже могли понять, нет. Будем также считать, что сейчас ячейка value
находится в кеше Cpu1 в состоянии Exclusive. Порядок происходящих действий тогда может оказаться таким:
# | Cpu0 | Cpu0:value | Cpu0:finished | Cpu1 | Cpu1:value | Cpu1:finished |
0 | (...) | 0 (Shared) | false (Exclusive) | (...) | 0 (Shared) | (Invalid) |
1 |
|
0 (Shared) (10 in store buffer) |
false (Exclusive) | |||
2 |
|
0 (Shared) | (Invalid) | |||
3 |
|
0 (Shared) (10 in store buffer) |
true (Modified) | |||
4 |
|
0 (Shared) (in invalidation queue) |
(Invalid) | |||
5 |
|
0 (Shared) (10 in store buffer) |
true (Shared) | |||
6 |
|
0 (Shared) (in invalidation queue) |
true (Shared) | |||
7 |
|
0 (Shared) (in invalidation queue) |
true (Shared) | |||
Assertion fails | ||||||
N |
|
(Invalid) | true (Shared) |
Многопоточность это просто и понятно, не правда ли? Проблема находится на шагах (4) — (6). Получив invalidate
в (4), мы не выполняем его, а записываем в очередь. А в шаге (6) мы получаем read_response
на запрос read
, который был отправлен раньше того, в (2). Однако, это не заставляет нас инвалидировать value
, и потому assertion падает. Если бы операция (N) выполнилась раньше, то у нас бы ещё был шанс, но сейчас эта чёртова оптимизация нам всё сломала! Но с другой стороны, она такая быстрая и даёт нам ультралоулэйтенси™! Вот ведь дилемма. Разработчики железа не могут заранее магически знать, когда применение оптимизации допустимо, а когда она может что-то сломать. И поэтому они передают проблему нам, добавляя: «It's dangerous to go alone. Take this!»
Hardware Memory Model
Волшебный меч, которым снабжают разработчиков, отправившихся сражаться с драконами — на самом деле вовсе не меч, а скорее Правила Игры. В них описано, какие значения может увидеть процессор при выполнении им или другим процессором тех или иных действий. А вот Memory Barrier — это уже что-то, гораздо больше похожее на меч. В рассматриваемом нами примере MESI бывают такие мечи:
Store Memory Barrier (также ST, SMB, smp_wmb) — инструкция, заставляющая процессор выполнить все store, уже находящиеся в буфере, прежде чем выполнять те, что последуют после этой инструкции
Load Memory Barrier (также LD, RMB, smp_rmb) — инструкция, заставляющая процессор применить все invalidate, уже находящиеся в очереди, прежде чем выполнять какие-либо инструкции load
Имея в распоряжении новое оружие, мы с лёгкостью можем починить свой пример:
void executedOnCpu0() {
value = 10;
storeMemoryBarrier();
finished = true;
}
void executedOnCpu1() {
while(!finished);
loadMemoryBarrier();
assert value == 10;
}
Прекрасно, всё работает, мы довольны! Можно идти и писать классный производительный и корректный многопоточный код. Хотя стоп…
Казалось бы, причём здесь Java?
Write Once @ Run Anywhere
Все эти разнообразные протоколы когерентности кешей, мембары, сброшенные кеши и прочие специфичные для платформы вещи, по идее, не должны волновать тех, кто пишет код на Java. Java ведь платформо-независима, верно? И действительно, в Модели Памяти Java нет понятия reordering.
NB: Если эта фраза вас смущает, не продолжайте читать статью, пока не поймёте, почему. И читайте, например, это.
А вообще, звучит интересно. Понятия «reordering» нет, а сам reordering есть. Власти явно что-то скрывают! Но даже если отказаться от конспирологической оценки окружающей действительности, мы останемся с любопытством и желанием знать. Утолим же его! Возьмём простенький класс, иллюстрирующий наш недавний пример:[github]
public class TestSubject {
private volatile boolean finished;
private int value = 0;
void executedOnCpu0() {
value = 10;
finished = true;
}
void executedOnCpu1() {
while(!finished);
assert value == 10;
}
}
Традиционно, есть несколько подходов к тому, чтобы выяснить, что же там происходит. Можно развлечься с PrintAssembly
, можно поглядеть, что делает интерпретатор, можно отжать тайные знания у тех, кто уже знает. Можно с загадочным видом сказать, что там сбрасываются кеши и успокоиться.
В прошлый раз мы смотрели на сишный интерпретатор, который на самом деле не используется в production. В этот раз мы будем смотреть на то, как действует клиентский компилятор(C1). Я использовал для своих целей openjdk-7u40-fcs-src-b43-26_aug_2013.
Для человека, который раньше не открывал исходники OpenJDK (как, впрочем и для того, кто открывал), может оказаться непростой задачей найти, где в них производятся нужные действия. Один из простых способов это сделать — поглядеть в байт-код и узнать название нужной инструкции, а потом искать по нему.
$ javac TestSubject.java && javap -c TestSubject
void executedOnCpu0();
Code:
0: aload_0 // Толкаем в стек this
1: bipush 10 // Толкаем в стек 10
3: putfield #2 // Записываем во второе поле this (value) значение с вершины стека(10)
6: aload_0 // Толкаем в стек this
7: iconst_1 // Толкаем в стек 1
8: putfield #3 // Записываем в третье поле this (finished) значение с вершины стека(1)
11: return
void executedOnCpu1();
Code:
0: aload_0 // Толкаем в стек this
1: getfield #3 // Загружаем в стек третье поле this (finished)
4: ifne 10 // Если там не ноль, то переходим к метке 10(цикл завершён)
7: goto 0 // Переходим к началу цикла
10: getstatic #4 // Получаем статическое служебное поле $assertionsDisabled:Z
13: ifne 33 // Если assertions выключены, переходим к метке 33(конец)
16: aload_0 // Толкаем в стек this
17: getfield #2 // Загружаем в стек второе поле this (value)
20: bipush 10 // Толкаем в стек 10
22: if_icmpeq 33 // Если два верхних элемента стека равны, переходим к метке 33(конец)
25: new #5 // Создаём новый java/lang/AssertionError
28: dup // Дублируем значение на верхушке стека
29: invokespecial #6 // Вызываем конструктор (метод <init>)
32: athrow // Кидаем то, что лежит на верхушке стека
33: return
NB: Не стоит пытаться по байт-коду определить точное поведение программы в рантайме. После того, как JIT-компилятор сделает своё дело, всё может измениться очень сильно.
Что интересного мы здесь можем заметить? Первая мелочь, которую многие забывают — это то, что по умолчанию assertion-ы выключены. Включить их можно в рантайме с помощью ключика -ea
. Но это так, ерунда. То, за чем мы сюда пришли, — имена инструкций getfield
и putfield
. Вы думаете о том же, о чём и я? (Конечно, Глеб! Только как мы построим Сферу Дайсона из бекона, вантуза и двух бюстгальтеров?!)
Down the Rabbit Hole
Обратив внимание на то, что для обоих полей используются одни и те же инструкции, посмотрим, где содержится информация о том, что поле является volatile
. Для хранения данных о полях используется класс share/vm/ci/ciField.hpp
. Нас интересует метод
|
|
Для того, чтобы узнать, что C1 делает с доступом к volatile
полям, можно найти все использования этого метода. Немного побродив по подземельями и собрав несколько Свитков с Древними Знаниями, мы оказываемся в файле share/vm/c1/c1_LIRGenerator.cpp
. Как намекает нам его имя, он занимается генерацией низкоуровневого промежуточного представления (LIR, Low-Level Intermediate Representation) нашего кода.
C1 Intermediate Representation на примере putfield
При создании IR в C1 наша инструкция putfield
в итоге обрабатывается здесь. Рассмотрим особые действия, которые выполняются для volatile
полей и довольно быстро наткнёмся на знакомые слова:
|
|
Здесь __
— это макрос, который раскрывается в gen()->lir()->
. А метод membar_release
определён в share/vm/c1/c1_LIR.hpp
:
|
|
Фактически, эта строка добавила в промежуточное представление нашего кода инструкцию membar_release. После этого происходит следующее:
|
|
Реализация метода volatile_field_store
уже платформо-зависима. На x86 (cpu/x86/vm/c1_LIRGenerator_x86.cpp
), например, действия происходят довольно простые: проверяется, не является ли поле 64-битным, и если это так, то используется Чёрная Магия для того, чтобы гарантировать атомарность записи. Все же помнят, что в при отсутствии модификатора volatile
поля типа long
и double
могут быть записаны неатомарно?
И, наконец, в самом конце, ставится ещё один membar, на этот раз без release:
|
|
|
|
NB: Я, конечно, коварно скрыл некоторые происходящие действия. Например, манипуляции, связанные с GC. Изучить их предлагается читателю в качестве самостоятельного упражнения.
Преобразование IR в ассемблер
Мы проходили только ST и LD, а тут встречаются новые типы барьеров. Дело в том, что то, что мы видели раньше — это пример барьеров для низкоуровнего MESI. А мы уже перешли на более высокий уровень абстракции, и термины несколько изменились. Пусть у нас есть два типа операций с памятью: Store и Load. Тогда есть четыре упорядоченные комбинации из двух операций: Load и Load, Load и Store, Store и Load, Store и Store. Две категории мы рассмотрели: StoreStore и LoadLoad — и есть те самые барьеры, что мы видели, говоря о MESI. Остальные две тоже должны быть довольно легко усваиваемыми. Все load, произведённые до LoadStore, должны завершиться прежде, чем любой store после. Со StoreLoad, соответственно, наоборот. Более подробно об этом можно почитать, например, в JSR-133 Cookbook.
Кроме того, выделяют понятия операции с семантикой Acquire и операции с семантикой Release. Последняя применима к операциям записи, и гарантирует, что любые действия с памятью, идущие до этой операции, обязаны завершиться до её начала. Иными словами, операцию с семантикой write-release нельзя reorder-ить с любой операцией с памятью, идущей до неё в тексте программы. Такую семантику нам может обеспечить комбинация LoadStore + StoreStore memory barrier. Acquire же, как можно догадаться, имеет противоположную семантику, и может быть выражена с помощью комбинации LoadStore + LoadLoad.
Теперь мы понимаем, какие мембары расставляет JVM. Однако, пока мы видели это только в LIR, который, хоть и Low-level, но всё ещё не является нативным кодом, который должен сгенерировать нам JIT. Исследование того, как именно C1 пребразует LIR в нативный код, выходит за пределы этой статьи, потому мы без лишних оговорок отправимся прямиком в файлик share/vm/c1/c1_LIRAssembler.cpp
. Там и происходит всё превращение IR в ассемблерный код. Например, в очень зловещей строке рассматривается lir_membar_release
:
|
|
Вызываемый метод уже платформо-зависим, и исходный код для x86 лежит в cpu/x86/vm/c1_LIRAssembler_x86.cpp
:
|
|
Шикарно! Благодаря строгой модели памяти (в том числе, TSO — Total Store Order), на этой архитектуре все записи и так имеют семантику release. А вот со вторым membar всё немного сложнее:
|
|
Тут макрос __
разворачивается в _masm->
, а метод membar
лежит в cpu/x86/vm/assembler_x86.hpp
и выглядит так:
|
|
Выходит, на x86 на запись каждой volatile
переменной мы ставим дорогой StoreLoad барьер в виде lock addl $0x0,(%rsp)
. Операция дорогая, поскольку она заставляет нас выполнить все Store в буфере. Однако она даёт нам тот самый эффект, что мы ожидаем от volatile
— все остальные потоки увидят как минимум значение, бывшее актуальным на момент её исполнения.
Получается, что read на x86 должен быть самым обычным read. Беглый осмотр метода LIRGenerator::do_LoadField
говорит нам, что после чтения, как мы того и ожидали, выставляется membar_acquire, который на x86 выглядит так:
|
|
Это, конечно, ещё не значит, что volatile read
не привносит никакого оверхеда по сравнению с обычным read
. Например, хоть в нативный код ничего и не добавляется, наличие барьера в самой IR запрещает компилятору переставлять некоторые инструкции. (иначе можно поймать забавные баги). Есть и множество других эффектов от использования volatile. Почитать об этом можно, например, вот в этой статье.
Проверка на вшивость
PrintAssembly
Сидеть и гадать на исходниках — благородное занятие, достойное любого уважающего себя философа. Однако, на всякий случай мы всё же заглянем в PrintAssembly
. Для этого добавим в подопытного кролика много вызовов нужных методов в цикле, отключим инлайнинг (чтобы было легче ориентироваться в сгенерированном коде) и запустимся в клиентской VM, не забыв включить assertions:
$ java -client -ea -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:MaxInlineSize=0 TestSubject
...
# {method} 'executedOnCpu0' '()V' in 'TestSubject'
...
0x00007f6d1d07405c: movl $0xa,0xc(%rsi)
0x00007f6d1d074063: movb $0x1,0x10(%rsi)
0x00007f6d1d074067: lock addl $0x0,(%rsp) ;*putfield finished
; - TestSubject::executedOnCpu0@8 (line 15)
...
# {method} 'executedOnCpu1' '()V' in 'TestSubject'
...
0x00007f6d1d061126: movzbl 0x10(%rbx),%r11d ;*getfield finished
; - TestSubject::executedOnCpu1@1 (line 19)
0x00007f6d1d06112b: test %r11d,%r11d
...
Вот и славно, всё выглядит ровно так, как мы и предсказали. Осталось проверить, действительно ли при отсутствии volatile
что-то может пойти не так. Ранее в своей статье TheShade демонстрировал сломанный Double-Checked Locking, но мы тоже хотим немного поизвращаться, и потому попробуем сломать всё сами. Ну, или почти сами.
Демонстрация поломки без volatile
Проблема демонстрации такого реордеринга заключается в том, что вероятность его происхождения в общем случае не очень-то и велика, а на отдельных архитектурах HMM его и вовсе не позволит. Потому нам нужно либо разжиться альфой, либо положиться на реордеринг в компиляторе. И, кроме того, запустить всё много-много-много раз. Как хорошо, что нам не придётся изобретать для этого велосипед. Воспользуемся замечательной утилитой jсstress. Если говорить совсем просто, то она многократно выполняет некоторый код и собирает статистику по результату выполнения, делая всю грязную работу за нас. Включая и ту, о необходимости которой многие и не подозревают.
Более того, за нас уже написали и нужный тест. Точнее, чуть более усложнённый, но прекрасно демонстрирующий происходящее:
static class State {
int x;
int y; // acq/rel var
}
@Override
public void actor1(State s, IntResult2 r) {
s.x = 1;
s.x = 2;
s.y = 1;
s.x = 3;
}
@Override
public void actor2(State s, IntResult2 r) {
r.r1 = s.y;
r.r2 = s.x;
}
У нас есть два потока: один меняет состояние, а второй — читает состояние и сохраняет результат, который увидел. Фреймворк за нас агрегирует результаты, и проверяет их по некоторым правилам. Для нас интересны два результата, которые может увидеть второй поток: [1, 0]
и [1, 1]
. В этих случаях мы прочли y == 1
, но при этом мы либо не увидели вообще никаких записей в x
(x == 0
), либо увидели не самую последнюю на момент записи y
, то есть x == 1
. Согласно нашей теории, такие результаты должны встречаться. Проверим это:
$ java -jar tests-all/target/jcstress.jar -v -t ".*UnfencedAcquireReleaseTest.*"
...
Observed state Occurrence Expectation Interpretation
[0, 0] 32725135 ACCEPTABLE Before observing releasing write to, any value is OK for $x.
[0, 1] 15 ACCEPTABLE Before observing releasing write to, any value is OK for $x.
[0, 2] 36 ACCEPTABLE Before observing releasing write to, any value is OK for $x.
[0, 3] 10902 ACCEPTABLE Before observing releasing write to, any value is OK for $x.
[1, 0] 65960 ACCEPTABLE_INTERESTING Can read the default or old value for $x after $y is observed.
[1, 3] 50929785 ACCEPTABLE Can see a released value of $x if $y is observed.
[1, 2] 7 ACCEPTABLE Can see a released value of $x if $y is observed.
Тут мы можем видеть, что в 65960 случаях из 83731840 (примерно 0.07%) мы увидели y == 1 && x == 0
, что явно говорит о произошедшем реордеринге. Ура, можно завязывать.
У читателя теперь должно быть достаточно хорошее понимание происходящего, чтобы ответить на вопросы, заданные в начале статьи. Напомню:
- Как работает happens-before?
- Правда ли, что
volatile
— это сброс кешей? - Зачем вообще было городить какую-то модель памяти?
Ну что, всё встало на свои места? Если нет, то, стоит попробовать вникнуть в соответствующий раздел статьи ещё раз. Если это не помогает, добро пожаловать в комментарии!
And one more thing ©
Выполнять преобразования над исходным кодом может не только железо, но и вся среда исполнения. Для соблюдения требований JMM ограничения накладываются на все компоненты, где что-то может поменяться. Например, компилятор в общем случае может перестанавливать какие-то инструкции, однако многие оптимизации ему может запретить делать JMM.
Разумеется, серверный компилятор(С2) существенно умнее, чем С1, рассмотренный нами, и некоторые вещи в нём сильно отличаются. Например, семантика работы с памятью абсолютна иная.
В кишках многопоточности OpenJDK во многих местах используется проверка os::is_MP()
, что позволяет улучшить производительность на однопроцессорных машинах, не выполняя некоторые операции. Если с помощью Запрещённых Искусств заставить JVM думать во время старта, что она исполняется на одном процессоре, то проживёт она не долго.
Большое спасибо доблестным TheShade, cheremin и artyushov за то, что они (вы|про)читали статью перед публикацией, убедившись тем самым, что я не принесу в массы вместо света какую-то бредовню, наполненную тупыми шутками и очепатками.
Автор: gvsmirnov