Идея статьи родилась после прочтения многочисленных источников в интернете по барьерам и моделям памяти.Так же, был просмотрены соответствующие видео с разъяснением. Много где в целом всё достаточно хорошо разжевано. Статья не претендует на исчерпывающий материал. Скорее, это обзорное описание на тему модели памяти в связке с RISC-V. Не рассчитана на entry level, рекомендуется сперва почитать что нибудь вводное.
Навряд ли кому то необходимо детальное знание внутренней архитектуры процессора на уровне RTL (register-transfer level), как и глубокого понимания принципов модели памяти, согласованности. Да и обычно вся эта информация берется из соответствующей литературе от производителя, других книгах по оптимизации. Предполагаю, что авторы в том или ином виде могу знать более глубокие вещи, чем представлены в открытых источниках. Возможно, они работали в компании производителя (Intel, например), общение, конференции, сообщества.
Но может ли быть источник лучший, чем исходники CPU? Навряд ли. Вы не найдете в открытом доступе исходники процессоров Intel, AMD и любых других. ARM за это денежки получает, продавая права на архитектуру и готовые спроектированные блоки. А вот для RISC-V такой источник есть - исходники полноценного суперскалярного out-of-order процессора от Berkley.
Не так давно был разработан язык Chisel на замену Verilog и аналогов. Он на базе Scala. А, так как это Scala, мы можем использовать IDE и внятную навигацию по исходникам. Но в исходники просто так не пойдешь, сперва надо приобрести необходимые фундаментальные знания, чтобы понимать в целом что такое разработка на уровне RTL. Неплохо бы разобраться с Verilog и с базовыми понятиями - всякие там защелки, регистры, мультиплексоры и тп. Это я и решил сделать и начал с книги “Паттерсон, Хеннесси: Архитектура компьютера и проектирование компьютерных систем”. Она безумно крутая и очень понятная. Затем прочитал несколько книг по FPGA и Verilog и даже купил учебную FPGA плату, но руки до неё так и не дошли. Это позволило сформировать для себя какую то необходимую картину того, как функционирует CPU, как происходит проектирование микроконтроллеров.
Вернемся к Chisel. На этом языке есть написанные ядра процессора с архитектурой RISC-V. Их несколько.
Это учебный проект самой базовой реализации системы команд RISC-V.
Исходники действительно простые, можно достаточно быстро разобраться и понять общие принципы построения архитектуры CPU.
Там есть реализация без конвейера и реализация с простым конвейером в несколько стадий.
Далее, есть так называемый Rocket
https://github.com/chipsalliance/rocket-chip
https://chipyard.readthedocs.io/en/stable/Generators/Rocket.html
Это реализация in-order 5 ступенчатого конвейера процессора с кэшем L1. Так же, есть доп модуль L2 cache типа directory based
https://github.com/chipsalliance/rocket-chip-inclusive-cache
Ну и вишенка на торте - полноценная out-of-order реализация от Berkeley с барьерами памяти, атомиками, механизмом когерентности кэшей.
The Berkeley Out-of-Order RISC-V Processor
https://github.com/riscv-boom/riscv-boom
https://chipyard.readthedocs.io/en/latest/Generators/BOOM.html
Там представлены несколько версий ядра с разной длиной конвейера (7ми и 12ти стадийные).
Для желающих побродить по исходникам ссылки оставил внизу. Названия файлов и структура таблицы команд плюс-минус одинаковая во всех проектах (Sodor, Rocket, BooM)
Boom и Rocket включают в себя L1 Cache (раздельный для инструкций и данных) и возможность многоядерной реализации. Для взаимодействия с внешним миром используется протокол TileLink (ссылку на спеку оставил ниже). По нему ходят запросы в ОЗУ, в кэши верхнего уровня, в MMIO и реализуется когерентность кэшей. Он используется вместо MESI и аналогов.
Схема шины TileLink из спеки:
А общая схема нашего 2х ядерного CPU выглядит так: TileBus это и есть тот самый TileLink
Итак, начнём с самого базового. Представим, что у нас одноядерный процессор. Есть кэш, есть кэши верхнего уровня и основная память. В дальнейшем будем это называть внешней память - всё то, что выше L1. Когда он читает данные, сперва он подгружает кэш линию целиком (64-128 байт), затем получает оттуда необходимый кусочек данных. Если же он хочет записать данные, то ему необходимо подгрузить всю кэш линию, после чего записать в неё данные. В результате она станет грязной (dirty) и должна будет в будущем синхронизирована с основной памятью. Других механизмов работы с памятью, можно считать, нет. Если данных в кэше нет, мы ждём достаточно большое количество времени. Для этого, в том числе, и нужен всяческий реордеринг и сложный конвейер, чтобы, во первых, мы могли спекулятивно читать данные, а во вторых, пока одни инструкции обрабатываются, другие могли параллельно исполняться.
А теперь представим ситуацию, когда у нас есть 2 ядра, у каждого есть свой кэш данных. В этом случае нам необходимо знать, существует ли данная линия только в кэше одного ядра, или они существуют в нескольких и одновременно шарятся между ними. Так же необходимо знать, если данные были изменены в локальном кэше одним из ядер. Допустим, ядро 1 хочет прочитать какой-то участок памяти, оно подгружает эту кэш линию, работает с ней. В процессе загрузки этой же кэш линии другим ядром, оно узнает, что данная кэш линия находится в ядре другого процессора. Реализовать это можно по разному. Если у нас есть кэш верхнего уровня, то в нём может храниться метаинформация, между какими ядрами она шарится. Так релизован модуль кэша L2 в текущей архитектуре RISC-V от Беркли (https://github.com/chipsalliance/rocket-chip-inclusive-cache). А можно просто через сообщения по шине, проверяя, есть ли данная линия в другом ядре. И даже получить данные по шине, не ходя во внешнюю память, как вариант. Протокол TileLink это позволяет. В данном случае, если мы только читаем данные, то нам не важно вообще, шарятся они между кэшами или нет, мы их не меняем. Они всегда как бы консистентны в разных ядрах, здесь никаких проблем и не возникает. Основная проблема появляется только тогда, когда мы начинаем эти данные изменять. Как только мы меняем данные в одном из ядер, то мы должны каким-то образом сообщить другому ядру о том, что его копия данных уже не актуальна. В протоколе TileLink для RISC-V это реализовано через уровень владения данными. Это может быть read-only узел, может быть read-write (далее r/o и r/w). При подгрузке кэш линии мы запрашиваем её с необходимым уровнем владения. Владеть данными с возможностью записи допустимо только одному узлу в один момент времени. Если у нас текущий уровень владения r/o, то мы сперва должны запросить пермишны на r/w и только потом записывать. Ядро отправляет сообщение на шину с запросом изменения уровня владения. В случае же, если у другого ядра на данный момент есть права r/w на эту линию, то мы должны отозвать их и заставить записать dirty данные во внешнюю память если они были изменены. После того, как мы изменили данные в кэш-линии, на шину уходит сообщение о том, что её надо инвалидировать во всех других ядрах, где она присутствует (с правами владения r/o). В терминологии TileLink это сообщение называется Probe. Invalidation queue в случае RISC-V и протокола TileLink будем называть Probe Queue. Другие ядра получают это сообщение и инвалидируют у себя эту кэш линию. Но это совершенно не означает, что они сразу пойдут подгружать свежие данные. Также, это не означает, что ядро, которое испачкало эту линию, должно её сбросить в основную память сразу после отправки сообщения об инвалидации. Эта кэш линия просто висит dirty в ядре процессора, пока не закончится место в кэше, и надо будет вытеснить эту строку. Или пока другие ядра не захотят тоже прочитать эту кэш линию. В таком случае к нашему ядру по шине придет запрос об отзыве уровня привилегий r/w с необходимостью сбросить её во внешнюю память - сделать write-back.
Все эти транзакции отправки сообщений занимают достаточно большое время. На шине есть арбитры, которые кладут эти запросы в очередь. И часто необходимо обязательно дождаться ответа от другого узла. Соответственно, это десятки или сотни тактов, все зависит от скорости работы шины и от её загруженности. Запрос также встанет в probe queue в ядре, на которое он пришёл. Ответ же мы отправим до начала обработки этого запроса.
Конкретно этот момент во всех статьях по модели памяти привлекает много внимания, потому что в invalidation queue (probe queue в нашем случае) висит запись, но ядро ещё не успело её обработать и начинает спекулятивно исполнять код используя закешированные ранее данные, а они уже не консистентны.
В случае RISC-V Boom это не совсем так. Когда у нас пришёл запрос на инвалидацию, и мы положили его probe queue, то он обрабатывается не сразу. И пока команда на инвалидацию отработает, пройдет много тактов. В текущей реализации RISC-V Boom даже без барьеров памяти при чтении данных из кэша проверяется присутствие адреса на инвалидацию в probe queue. Но сам по себе барьер памяти запрещает спекулятивно читать данные и однозначно заставляет при чтении увидеть сообщение в probe. Грубо говоря, если probe пришел, после него инструкция чтения это увидит.
Один из важнейших вопросов здесь - как быстро вообще изменения данных конкретным ядром доходят до другого ядра или до основной памяти? Если этими данными владели только мы (одно конкретное ядро) и меняли только мы, то после изменения они просто лежат в нашем кэше, пока мы их не сбросим в основную память. Произойти это может когда угодно. Но, как только данные необходимы другому ядру, они сбрасываются в память и отправляются в кэш другого процессора, либо по внутренней шине, либо через основную память (или общий кэш), а происходит это не быстро. Так же, сбросить данные из кэша заставляет алгоритм вытеснения при подгрузке новых кэш линий при нехватке свободного места.
На примере false sharing мы можем это проанализировать.
Напомню, что false-sharing это когда у нас две (или более) переменные располагаются в памяти рядом и занимают общую кэш линию. Об этом потоки могут совершенно не подозревать, потому что логически данные не связаны. Первая переменная используется только первым потоком, вторая использует только вторым. Но, из-за того, что оба потока постоянно и пишут и читают только свои переменные, у нас возникает избыточный трафик на шине, так как есть пересечение по линии кэша.
//переменные лежат рядом на одной кэш линии
long a;
long b;
thread 1:
while (true) {
a++;
}
thread 2:
while (true) {
b++;
}Исходное состояние - данных нет в кэшах.
-
поток 1 читает переменную a.
-
на шину уходит запрос о подгрузке кэш линии с правами r/w.
-
загружается кэш линия.
-
поток 1 изменяет эту линию меняя её состояние на dirty.
-
поток 2 читает переменную b с правами r/w.
-
по шине в ядро 1 приходит сообщение об отзыве прав владения r/w
-
ядро 1 сбрасывает данные во внешнюю память и очищает кэш линию
-
загружается кэш линия в кэш ядра 2
-
поток 2 изменяет эту линию и меняет её состояние на dirty
-
поток 1 читает переменную a с правами r/w.
-
по шине в ядро 2 приходит сообщение об отзыве прав владения r/w
-
ядро 2 сбрасывает данные во внешнюю память и очищает кэш линию
-
загружается кэш линия в кэш ядра 1
-
поток 1 изменяет эту линию и меняет её состояние на dirty
-
И по новой …
В случае же, когда в обоих ядрах находится кэш линия с правами r/o, и один из потоков хочет изменить её, на шину уходит запрос с изменением уровня владения на r/w, что заставляет другой в свою очередь сразу инвалидировать у себя эту кэш линию. Сам процесс записи в кэш линию как раз и провоцирует отправку запроса повышения привилегий с инвалидацией копии.
Отправка сообщения на шину происходит в два этапа - сперва сообщение уходит арбитру шины, затем он связывается с всеми необходимыми узлами и пересылает им исходное дожидаясь ответа и возвращает итоговый ответ. Шина медленная, отправка сообщений занимает десятки тактов. Сброс кэш линии в память с последующей загрузкой её же другим ядром тоже не быстрая операция. В итоге, каждая итерация чтения переменных потоками 1 и 2 будет замедлять наш алгоритм в десятки (а то и сотни) раз. Прикинуть по этой же аналогии другие алгоритмы не сложно. Например, алгоритм Деккера в свете данной информации выглядит совсем недружелюбно по отношению к шине и кэшам процессора. Там у вас уже не false sharing, там явное использование одних и тех же переменных разными потоками. И это мы не говорим про барьеры памяти. Если они используются, то всё может быть еще медленнее из за принудительного сброса очередей, очистки префетчей и тп.
Теперь можно перейти к более детальному рассмотрению устройства CPU и барьерам памяти. В RISC-V инструкция барьера памяти называется FENCE (как и во многих других архитектурах). Из спеки:
“The FENCE instruction is used to order device I/O and memory accesses as viewed by other RISC-V harts and external devices or coprocessors. Any combination of device input (I), device output (O), memory reads (R), and memory writes (W) may be ordered with respect to any combination of the same. Informally, no other RISC-V hart or external device can observe any operation in the successor set following a FENCE before any operation in the predecessor set preceding the FENCE”.
К тому же, у FENCE есть параметры вида барьера памяти - LoadLoad, StoreStore, LoadStore, StoreLoad и TSO. В текущей реализации RISC-V Boom они не используются. Да и в целом команды FENCE, атомики и Load Reserved/Store Conditional достаточно хорошо согласуются с интерфейсом реализации модели памяти С++, а теперь практически и с Java через varhandle.. Ну и сами атомики. В спеке на RISC-V есть очень хорошее описание модели памяти RVWMO - RISC-V Weak Memory Ordering. Сама инструкция FENCE, атомики и LR/SC содержат дополнительные параметры требуемого уровня сериализуемости.
Из спеки - Load and store operations may also carry one or more ordering annotations from the following set: “acquire-RCpc”, “acquire-RCsc”, “release-RCpc”, and “release-RCsc”. An AMO or LR instruction with aq set has an “acquire-RCsc” annotation. An AMO or SC instruction with rl set has a “release-RCsc” annotation. An AMO, LR, or SC instruction with both aq and rl set has both “acquire-RCsc” and “release-RCsc” annotations.
Вот для затравочки схема ядра RISC-V BooM
Execution Unit довольно сложная штука, он делает всю магию реордеринга, в том числе. С LSU (load store unit) он взаимодействует с двумя очередями - Load Queue (LDQ) и Store Queue (STQ). Вот что есть в комментариях к коду
// Load/Store Unit is made up of the Load-Address Queue, the Store-Address
// Queue, and the Store-Data queue (LAQ, SAQ, and SDQ).
//// Stores are sent to memory at (well, after) commit, loads are executed
// optimistically ASAP. If a LoadAddr and StoreAddr match,
// the Load can receive its data by forwarding data out of the Store-Data Queue.
// Currently, loads are sent to memory immediately, and in parallel do an
// associative search of the SAQ, on entering the LSU. If a hit on the SAQ
Cторы исполняются, как только они будут закомичены реордер буффером out-of-order. Если присутствует FENCE, он заставляет делать всё в program order - как реордер буффер в execution unit, так и store/load queue. То же самое и с префетчами. FENCE не позволяет поздним запросам на чтение выполниться раньше, чем нужно и инвалидирует спекулятивное чтение кэш линий. TLB оставим за скобками. Это отдельная история.
В LSU есть несколько блоков, между ними находятся арбитры, которые кладут в очередь запросы. Нарисуем более детальную схему LSU с кэшем L1$D
Что у нас тут есть.
Exec unit - ядро процессора
Load Queue и Store Queue - LDQ, STQ – очереди загрузки данных и записи в память.
DATA - массив данных кэша
META - массив тегов (адресов в памяти) к ним. + всякие флаги типа грязной кэш линии, прав на владение.
TileLink это как раз шина протокола, через которую идет связь с внешним миром.
Probe - это блок, куда приходят запросы на инвалидацию кэш линии и изменения прав владения.
WriteBack Unit (WB на схеме) - через него происходит запись данных в память из кэша.
MSHRs - miss status holding register file. (несколько регистров - в текущей спеке 8)
Сюда попадают запросы при промахе кэша (как на чтение, так и на запись). В этом блоке реализована подгрузка линий кэша. Так же там реализована логика вытеснения при переполнении кэша. Ровно за этим он ходит в WriteBack Unit, если хочет сбросить в память грязную кэш линию.
Все блоки по необходимости ходят либо за данными, либо за тегами. Например, чтобы понять, если ли линия в кэше и грязная ли она, достаточно только тегов. Поэтому, модуль Probe ходит только в теги. А WriteBack при записи в память читает как данные, так и теги.
Вернемся к барьерам памяти. Пусть у нас есть такой код
изначально f = 0, x = 0
Поток 1
x = 42;
// Memory fence required here
f = 1;
Поток 2
if (f == 1);
// Memory fence required here
print x; // должно быть 42Если мы увидели в одном потоке f == 1, после этого мы подразумеваем, что и x == 42, так как запись переменных была сделана в нужном нам порядке. Самое важное при использовании барьеров памяти, чтобы внешний мир увидел порядок появления данных в конкретном ядре таким же, каков он был в program order. Это касается как отправки данных напрямую в память (например, MMIO), так и записей в кэш линии. Отправки разного рода сообщений на шину - чтения, повышения уровня владения, инвалидации в других ядрах и тп.
В реальности это может быть не так, если не использовать барьеры памяти. Компилятор или процессор могут переставить инструкции местами. Это не запрещается, так как логически они связаны только в нашей голове (но не в CPU). Пока примем как факт то, что наш компилятор не переставляет инструкции местами и ничего не оптимизирует. В терминологии процессора взаимосвязь по данным, адресам, регистрам называется hazard. Мы не должны её сломать, сделав что то в другом порядке, или параллельно не дождавшись завершения предыдущей инструкции. За этим следит Execution Unit. Логическую связь разных данных он никак отследить не может. Поэтому, наши данные, когда пишутся в память, могут уйти в разном порядке в очередь записи. Могут зайти в разном порядке по шине синхронизации кэшей. Ну и в том ядре, в котором мы эти данные читаются, инвалидация этих адресов пойдет в другом порядке. В итоге, мы можем увидеть в x 0, даже после прочтения 1 в f.
Если мы посмотрим на реализацию BooM то увидим там некий ReOrder Buffer / Rename. Это именно то самое, что все называют реордерингом инструкций. Когда процессор начинает разгребать код многопоточным декодером, он производит переименование регистров в случае, когда инструкции используют один и тот же регистр по очереди, но связи по причинно следственности нет. Для этого у процессора есть много теневых регистров, где всё это проворачивается в произвольном порядке, закидывается в Reorder Buffer, а потом приводится уже к фактическим результатам в нужных регистрах, которые были указаны в программе. В RISC-V BooM их больше 100.
И, что самое важное, из Reorder Buffer все коммиты инструкций (записи в память) могут идти out-of-order по готовности. FENCE же задерживает ранние инструкции от попадания в Reorder Buffer. Соответственно, они не будут зареордерены и попадут в store queue в program order. Из в store queue данные сливаются в кэш тоже в прямом порядке, в каком туда пришли. Все запрошенные адреса попадают в Load Queue (это такая очередь, куда просто складывают то, что мы хотим прочитать из памяти). Она может работать тоже out-of-order в результате попадания туда записей из reorder buffer и в результате спекулятивных префетчей. Fence заставляет делать это в program order. Более того, из store queue мы можем выхватить данные, которые туда ушли, но еще не долетели до кэша, если они читаются где то дальше в программе. Это называется store forwarding. Если данных нет в кэше, адрес попадает в так называемый MSHR (miss status holder register), которые уже ходят в память по протоколу TileLink, подгружают кэш линию. Не важно, запись это или чтение. Сперва мы должны подгрузить кэш линию. За исключением MMIO или некэшируемых регионов памяти. В этом случае данные просто пишутся по нужному адресу или читаются оттуда без кэширования.
В RISC-V BooM барьеры не являются No-Op - они действительно реализованы из за присутствия многочисленных оптимизаций. Разработчики вдохновлялись архитектурой Alpha, как никак.
Вот что еще важно понять применительно к volatile в Java.
Представим такой код
volatile int f;
int x;
....
x = 42;
f = 1;Вы по факту создаете барьер НЕ ДЛЯ переменной f, а для всего, что ДО f. ТО есть, для x. Да, volatile так же гарантирует атомарную запись и чтение переменных типа long независимо от разрядности архитектуры процессоры, где он не может атомарно работать с такими размерностями операндов. В данном контексте это не рассматриваем. В случае барьеров мы всегда подразумеваем созависимость переменных. В примере выше мы сделали volatile именно f, так как x у нас зависима от неё.
И в другом потоке мы её читаем после f, а пишем перед f.
if (f == 1) {
print x;
}Не важно пишем ли мы одну дополнительную переменную и читаем.
Или много, как в случае, когда у нас volatile является объект c внутренними членами класса или массива, а не простой тип. Нам это нужно, чтобы при получении указателя на этот объект читать сам объект в консистентном состоянии.
Теперь об атомиках в RISC-V.
Очень интересно, что реализация атомиков существует как в Load-Store Unit, так и в протоколе TileLink. Она вынесена из основного ALU. Первая используется для кэшируемой памяти, вторая для некешируемой. Например, в случае атомарного инкремента для кэшируемой памяти мы сперва получаем строку с пермишнами read-write, затем делаем это, используя ALU в Load-Store Unit, а не основной ALU процессора. Затем эта строка так и лежит в кеше, пока другие cpu не захотят её получить для чтения или изменения. Я не увидел в коде, чтобы она принудительно после инкремента скидывалась в основную память, что интересно. Для некэшируемой памяти по шине уходит сообщение со всеми необходимыми данными, какую операцию совершить с каким операндами и по какому адресу. Узел получает это сообщение и выполняет команду. В TileLink есть реализация логики атомиков прям на уровне протокола узла шины.
Тут еще может возникнуть вот какой вопрос - как у нас ломается логика без атомика, если мы, вроде бы при чтении кэш линии с правами на запись изменяем получаем их уникально для нашего ядра, изменяем, а другое ядро должно перед подобным запросом заставить текущее ядро синхронизировать кэш линию с памятью, а потом прочитать актуальное значение в свой кэш. Выглядит так, будто между ядрами в кэш всегда будет уходить последнее обновленное значение. Да, но только в случае атомиков в виде единой инструкции. Всё потому, что в случае RISC-V это можно реализовать через 3 инструкции процессора, отдельных инструкций типа инкремента значения по адресу памяти не существует. RISC-V представляет так называемую load-store архитектуру - мы сперва загружаем в регистр, проделываем некую логику, потом обновляем в памяти.
li t0, 48
lw t1, 0(t6)
//тут у нас что то произошло - смена контекста или инвалидация кэш линии
addi t1, t0, 1
//к этому моменту значение уже поменялось в памяти, мы перезапишем его
sw t0, 0(t6)
amoadd.w a2, a1, (a0) – а вот простой атомик в форме одной инструкцииЛогика атомика для кэшируемой памяти реализована в Load-Store Unit, как я уже писал выше. Сперва данные подгружаются с правами владения r/w, потом производится операция напрямую в Load-Store Unit с обновлением значения в линии кэша. И если нам придет запрос на отзыв прав владения, мы сделаем это либо ДО команды атомика, либо после того, как значение будет обновлено. В память сбросится измененное значение и уедет в кэш другого ядра. Там будет проделано то же самое атомарно. Атомики, кстати, в реализации RISC-V BooM не имеют никаких атрибутов барьеров памяти, но местами они требуют дополнительных ограничений на оптимизации. Поэтому, в коде ядра CPU их можно увидеть в логике рядом с обработкой FENCE.
Ну и самое интересное, что для RISC-V выбрал именно подход Load Reserved/Store Conditional, тк он не подвержен проблеме ABA. В спеке RISC-V есть огромная портянка с объяснением почему это так. Вот, пожалуй, главное оттуда
“Both compare-and-swap (CAS) and LR/SC can be used to build lock-free data structures. After extensive discussion, we opted for LR/SC for several reasons:
1) CAS suffers from the ABA problem, which LR/SC avoids because it monitors all accesses to the address rather than only checking for changes in the data value;
2) CAS would also require a new integer instruction format to support three source operands (address, compare value, swap value) as well as a different memory system message format, which would complicate microarchitectures;
3) Furthermore, to avoid the ABA problem, other systems provide a double-wide CAS (DW-CAS) to allow a counter to be tested and incremented along with a data word. This requires reading five registers and writing two in one instruction, and also a new larger memory system message type, further complicating implementations;
4) LR/SC provides a more efficient implementation of many primitives as it only requires one load as opposed to two with CAS (one load before the CAS instruction to obtain a value for speculative computation, then a second load as part of the CAS instruction to check if value is unchanged before updating).
The main disadvantage of LR/SC over CAS is livelock, which we avoid, under certain circumstances, with an architected guarantee of eventual forward progress as described below. Another concern is whether the influence of the current x86 architecture, with its DW-CAS, will complicate porting of synchronization libraries and other software that assumes DW-CAS is the basic machine primitive. A possible mitigating factor is the recent addition of transactional memory instructions to x86, which might cause a move away from DW-CAS.
More generally, a multi-word atomic primitive is desirable, but there is still considerable debate about what form this should take, and guaranteeing forward progress adds complexity to a system. Our current thoughts are to include a small limited-capacity transactional memory buffer along the lines of the original transactional memory proposals as an optional standard extension “T”.
Load Reserved/Store Conditional работает не так, как CAS.
Сперва мы резервируем адрес памяти с помощью Load Reserved. Нам дается некоторое количество тактов, в которые мы должны уложиться с нашей логикой - 16 в случае RISC-V. Затем мы обновляем значение в памяти через Store Conditional, сравнивая его с предыдущим, как и в случае с классическим CAS.
Но, помимо сравнения значения, LR зафейлится, если кто то его перезаписывал даже на то же самое значение.
CAS используя lr/sc
cas:
lr.w t0, (a0) //загружаем значение с резервированием адреса
//некая логика изменения данных
sc.w t0, a2, (a0) //пытаемся обновить
bnez t0, cas //повторяем в случае неудачиСамое интересное, если данных нет в кэше, то мы и не успеем их подгрузить за 16 тактов (вероятнее всего). Поэтому SC зафейлится, и мы будем крутиться в цикле cas, пока строка не подсосется в кэш (с правами R/W, конечно же). После обновления она останется в кэше до момента очистки либо до момента прихода по шине запроса на эту кэш линию. Так же, SC зафейлится при переключении контекста в процессе. Интересно, что в текущей реализации RISC-V Boom не происходит сравнения значений при исполнении инструкции SC - оно не имеет смысла, так как мы всё равно определим факт изменения данных в памяти. Но эта возможность заложена в архитектуру системы команд для более строгих гарантий.
Главный вопрос - а как же ядро узнает о том, что данные были перезаписаны в промежутке между LR - SC? Через сообщение от шины, связанное с инвалидацией/отзывом прав владения на кэш линию. Так это реализовано в RISC-V Boom и архитектурно других возможностей для этого нет. LR/SC, кстати, самый базовый вариант поддержки программной транзакционной памяти.
Предупреждаю, если материал заинтересует, и вы захотите углубиться в детали - увязнете на пол года. ) Дико интересно и настолько же сложно.
Дополнительно почитать рекомендую тут - Memory Barriers: a Hardware View for Software Hackers. Очень крутой материал.
На Хабр эта статья переведена в рамках цикла постов у автора
По lock-free и модели памяти имхо лучшее из русскоязычного на просторах нашего интернета.
https://en.wikipedia.org/wiki/Chisel_(programming_language)
С чего начать ковырять исходники:
https://riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf
Автор: Openminder
