Логическая организация кэш-памяти процессора
На днях решил систематизировать знания, касающиеся принципов отображения оперативной памяти на кэш память процессора. В результате чего и родилась данная статья.
Кэш память процессора используется для уменьшения времени простоя процессора при обращении к RAM.
Основная идея кэширования опирается на свойство локальности данных и инструкций: если происходит обращение по некоторому адресу, то велика вероятность, что в ближайшее время произойдет обращение к памяти по тому же адресу либо по соседним адресам.
Логически кэш-память представляет собой набор кэш-линий. Каждая кэш-линия хранит блок данных определенного размера и дополнительную информацию. Под размером кэш-линии понимают обычно размер блока данных, который в ней хранится. Для архитектуры x86 размер кэш линии составляет 64 байта.
Так вот суть кэширования состоит в разбиении RAM на кэш-линии и отображении их на кэш-линии кэш-памяти. Возможно несколько вариантов такого отображения.
DIRECT MAPPING
Основная идея прямого отображения (direct mapping) RAM на кэш-память состоит в следующем: RAM делится на сегменты, причем размер каждого сегмента равен размеру кэша, а каждый сегмент в свою очередь делится на блоки, размер каждого блока равен размеру кэш-линии.
Блоки RAM из разных сегментов, но с одинаковыми номерами в этих сегментах, всегда будут отображаться на одну и ту же кэш-линию кэша:
Адрес каждого байта представляет собой сумму порядкового номера сегмента, порядкового номера кэш-линии внутри сегмента и порядкового номера байта внутри кэш-линии. Отсюда следует, что адреса байт различаются только старшими частями, представляющими собой порядковые номера сегментов, а порядковые номера кэш-линий внутри сегментов и порядковые номера байт внутри кэш-линий — повторяются.
Таким образом нет необходимости хранить полный адрес кэш-линии, достаточно сохранить только старшую часть адреса. Тэг (tag) каждой кэш-линии как раз и хранит старшую часть адреса первого байта в данной кэш-линии.
b — размер кэш-линии.
m — количество кэш-линий в кэше.
Для адресации b байт внутри каждой кэш-линии потребуется: log2b бит.
Для адресации m кэш-линий внутри каждого сегмента потребуется: log2m бит.
m = Объем кэш-памяти/Размер кэш линии.
Для адресации N сегментов RAM: log2N бит.
N = Объем RAM/Размер сегмента.
Для адресации байта потребуется: log2N + log2m + log2b бит.
Этапы поиска в кэше:
1. Извлекается средняя часть адреса (log2m), определяющая номер кэш-линии в кэше.
2. Тэг кэш-линии с данным номером сравнивается со старшей частью адреса (log2N).
Если было совпадение по одному из тэгов, то произошло кэш-попадание.
Если не было совпадение ни по одному из тэгов, то произошел кэш-промах.
FULLY ASSOCIATIVE MAPPING
Основная идея полностью ассоциативного отображения (fully associative mapping) RAM на кэш-память состоит в следующем: RAM делится на блоки, размер которых равен размеру кэш-линий, а каждый блок RAM может сохраняться в любой кэш-линии кэша:
Адрес каждого байта представляет собой сумму порядкового номера кэш-линии и порядкового номера байта внутри кэш-линии. Отсюда следует, что адреса байт различаются только старшими частями, представляющими собой порядковые номера кэш-линий. Порядковые номера байт внутри кэш-линий повторяются.
Тэг (tag) каждой кэш-линии хранит старшую часть адреса первого байта в данной кэш-линии.
b — размер кэш-линии.
m — количество кэш-линий, умещающихся в RAM.
Для адресации b байт внутри каждой кэш-линии потребуется: log2b бит.
Для адресации m кэш-линий: log2m бит.
m = Размер RAM/Размер кэш-линии.
Для адресации байта потребуется: log2m + log2b бит.
Этапы поиска в кэше:
1. Тэги всех кэш-линий сравниваются со старшей частью адреса одновременно.
Если было совпадение по одному из тэгов, то произошло кэш-попадание.
Если не было совпадение ни по одному из тэгов, то произошел кэш-промах.
SET ASSOCIATIVE MAPPING
Основная идея наборно ассоциативного отображения (set associative mapping) RAM на кэш-память состоит в следующем: RAM делится также как и в прямом отображении, а сам кэш состоит из k кэшей (k каналов), использующих прямое отображение.
Кэш-линии, имеющие одинаковые номера во всех каналах, образуют set (набор, сэт). Каждый set представляет собой кэш, в котором используется полностью ассоциативное отображение.
Блоки RAM из разных сегментов, но с одинаковыми номерами в этих сегментах, всегда будут отображаться на один и тот же set кэша. Если в данном сете есть свободные кэш-линии, то считываемый из RAM блок будет сохраняться в свободную кэш-линию, если же все кэш-линии сета заняты, то кэш-линия выбирается согласно используемому алгоритму замещения.
Структура адреса байта в точности такая же, как и в прямом отображении: log2N + log2m + log2b бит, но т.к. set представляет собой k различных кэш-линий, то поиск в кэше немного отличается.
Этапы поиска в кэше:
1. Извлекается средняя часть адреса (log2m), определяющая номер сэта в кэше.
2. Тэги всех кэш-линий данного сета сравниваются со старшей частью адреса (log2N) одновременно.
Если было совпадение по одному из тэгов, то произошло кэш-попадание.
Если не было совпадение ни по одному из тэгов, то произошел кэш-промах.
Т.о количество каналов кэша определяет количество одновременно сравниваемых тэгов.
Кэш в многопроцессорных системах. Когерентность кэша. Протокол MESI
В свое время это тема показалась мне очень интересной, поэтому я решил поделиться своими скромными знаниями с вами. Данная статья не претендует на полное детальное описание, скорее это краткий обзор.
Введение
Ни для кого не секрет, что в современных компьютерах доступ к памяти могут одновременно иметь несколько независимых процессоров (ядер, трэдов). Каждый из них имеет свои приватные кэши, в которых хранятся копии необходимых линий, а некоторые из них при этом локально модифицированы. Встает вопрос, а что если одна и та же линия одновременно понадобится нескольким процессорам. Не сложно сделать вывод, что для корректной работы системы необходимо обеспечить единое пространство памяти для всех процессоров.
Для обеспечения этого были придуманы специальные протоколы когерентности. Когерентность кэша — свойства кэш-памяти, означающее целостность данных, хранящихся в локальных кэшах, разделяемой системы. Каждая ячейка кэша имеет флаги, описывающие, как ее состояние соотносится с состоянием ячейки с таким же адресом в других процессорах системы.
При изменении состояния текущей ячейки необходимо каким-то образом сообщить об этом остальным кэшам. Например, генерируя широковещательных сообщения, доставляемые по внутренней сети многопроцессорной системы.
Было придумано множество протоколов когерентности, отличающиеся алгоритмами, количеством состояний и, как следствие скоростью работы и масштабируемостью. Большинство современных протоколов когерентности представляют вариации протокола MESI [1]. По этой причине мы его и рассмотрим.
В данной схеме каждая линию кэша может находиться в одном из четырех состояний:
Диаграмма переходов протокола MESI. Доступ являет местным, если он был инициирован процессоров данного кэша, удаленным — если его вызвал любой другой.
Также хочу рассмотреть одну из оптимизаций протокола MESI
MOESI
Для данного протокола флаги состояния были расширены еще одним значением «Владелец» (O) англ. owner. Данное состояние является комбинацией состояний «Модифицированная» и «Разделяемая». Такое состояние позволяет избежать необходимости записи измененной линии в память, тем самым снижая трафик направленный в память. Кэш линия в такой состоянии содержит наиболее свежие данные. Описанное состояние похоже на Shared тем, что и другие процессоры тоже могут иметь наиболее более свежие по отношению к ОЗУ данные у себя в кэш-памяти. Однако в отличие от него такое состояние обозначает, что данные в памяти устарели. Только одна линия с определенным адресом может иметь такое состояние, при этом на все запросы о чтении по данному адресу отвечать будет именно она, а не память.
Это все, про что я хотел рассказать сегодня, надеюсь, что моя статья окажется кому-нибудь интересна.
Дополнительную информацию на эту тему можно найти в источниках обозначенных ниже.
Что такое кэш в процессоре и зачем он нужен
Содержание
Содержание
Для многих пользователей основополагающими критериями выбора процессора являются его тактовая частота и количество вычислительных ядер. А вот параметры кэш-памяти многие просматривают поверхностно, а то и вовсе не уделяют им должного внимания. А зря!
В данном материале поговорим об устройстве и назначении сверхбыстрой памяти процессора, а также ее влиянии на общую скорость работы персонального компьютера.
Предпосылки создания кэш-памяти
Любому пользователю, мало-мальски знакомому с компьютером, известно, что в составе ПК работает сразу несколько типов памяти. Это медленная постоянная память (классические жесткие диски или более быстрые SSD-накопители), быстрая оперативная память и сверхбыстрая кэш-память самого процессора. Оперативная память энергозависимая, поэтому каждый раз, когда вы выключаете или перезагружаете компьютер, все хранящиеся в ней данные очищаются, в отличие от постоянной памяти, в которой данные сохраняются до тех пор, пока это нужно пользователю. Именно в постоянную память записаны все программы и файлы, необходимые как для работы компьютера, так и для комфортной работы за ним.
Каждый раз при запуске программы из постоянной памяти, ее наиболее часто используемые данные или вся программа целиком «подгружаются» в оперативную память. Это делается для ускорения обработки данных процессором. Считывать и обрабатывать данные из оперативной памяти процессор будет значительно быстрей, а, следовательно, и система будет работать значительно быстрее в сравнении с тем, если бы массивы данных поступали напрямую из не очень быстрых (по меркам процессорных вычислений) накопителей.
Если бы не было «оперативки», то процесс считывания напрямую с накопителя занимал бы непозволительно огромное, по меркам вычислительной мощности процессора, время.
Но вот незадача, какой бы быстрой ни была оперативная память, процессор всегда работает быстрее. Процессор — это настолько сверхмощный «калькулятор», что произвести самые сложные вычисления для него — это даже не доля секунды, а миллионные доли секунды.
Производительность процессора в любом компьютере всегда ограничена скоростью считывания из оперативной памяти.
Процессоры развиваются так же быстро, как память, поэтому несоответствие в их производительности и скорости сохраняется. Производство полупроводниковых изделий постоянно совершенствуется, поэтому на пластину процессора, которая сохраняет те же размеры, что и 10 лет назад, теперь можно поместить намного больше транзисторов. Как следствие, вычислительная мощность за это время увеличилась. Впрочем, не все производители используют новые технологии для увеличения именно вычислительной мощности. К примеру, производители оперативной памяти ставят во главу угла увеличение ее емкости: ведь потребитель намного больше ценит объем, нежели ее быстродействие. Когда на компьютере запущена программа и процессор обращается к ОЗУ, то с момента запроса до получения данных из оперативной памяти проходит несколько циклов процессора. А это неправильно — вычислительная мощность процессора простаивает, и относительно медленная «оперативка» тормозит его работу.
Такое положение дел, конечно же, мало кого устраивает. Одним из вариантов решения проблемы могло бы стать размещение блока сверхбыстрой памяти непосредственно на теле кристалла процессора и, как следствие, его слаженная работа с вычислительным ядром. Но проблема, мешающая реализации этой идеи, кроется не в уровне технологий, а в экономической плоскости. Такой подход увеличит размеры готового процессора и существенно повысит его итоговую стоимость.
Объяснить простому пользователю, голосующему своими кровными сбережениями, что такой процессор самый быстрый и самый лучший, но за него придется отдать значительно больше денег — довольно проблематично. К тому же существует множество стандартов, направленных на унификацию оборудования, которым следуют производители «железа». В общем, поместить оперативную память прямо на кристалл процессора не представляется возможным по ряду объективных причин.
Как работает кэш-память
Как стало понятно из постановки задачи, данные должны поступать в процессор достаточно быстро. По меркам человека — это миг, но для вычислительного ядра — достаточно большой промежуток времени, и его нужно как можно эффективнее минимизировать. Вот здесь на выручку и приходит технология, которая называется кэш-памятью. Кэш-память — это сверхбыстрая память, которую располагают прямо на кристалле процессора. Извлечение данных из этой памяти не занимает столько времени, сколько бы потребовалось для извлечения того же объема из оперативной памяти, следовательно, процессор молниеносно получает все необходимые данные и может тут же их обрабатывать.
Кэш-память — это, по сути, та же оперативная память, только более быстрая и дорогая. Она имеет небольшой объем и является одним из компонентов современного процессора.
На этом преимущества технологии кэширования не заканчиваются. Помимо своего основного параметра — скорости доступа к ячейкам кэш-памяти, т. е. своей аппаратной составляющей, кэш-память имеет еще и множество других крутых функций. Таких, к примеру, как предугадывание, какие именно данные и команды понадобятся пользователю в дальнейшей работе и заблаговременная загрузка их в свои ячейки. Но не стоит путать это со спекулятивным исполнением, в котором часть команд выполняется рандомно, дабы исключить простаивание вычислительных мощностей процессора.
Спекулятивное исполнение — метод оптимизации работы процессора, когда последний выполняет команды, которые могут и не понадобиться в дальнейшем. Использование метода в современных процессорах довольно существенно повышает их производительность.
Речь идет именно об анализе потока данных и предугадывании команд, которые могут понадобиться в скором будущем (попадании в кэш). Это так называемый идеальный кэш, способный предсказать ближайшие команды и заблаговременно выгрузить их из ОЗУ в ячейки сверхбыстрой памяти. В идеале их надо выбирать таким образом, чтобы конечный результат имел нулевой процент «промахов».
Но как процессор это делает? Процессор что, следит за пользователем? В некоторой степени да. Он выгружает данные из оперативной памяти в кэш-память для того, чтобы иметь к ним мгновенный доступ, и делает это на основе предыдущих данных, которые ранее были помещены в кэш в этом сеансе работы. Существует несколько способов, увеличивающих число «попаданий» (угадываний), а точнее, уменьшающих число «промахов». Это временная и пространственная локальность — два главных принципа кэш-памяти, благодаря которым процессор выбирает, какие данные нужно поместить из оперативной памяти в кэш.
Временная локальность
Процессор смотрит, какие данные недавно содержались в его кэше, и снова помещает их в кэш. Все просто: высока вероятность того, что выполняя какие-либо задачи, пользователь, скорее всего, повторит эти же действия. Процессор подгружает в ячейки сверхбыстрой памяти наиболее часто выполняемые задачи и сопутствующие команды, чтобы иметь к ним прямой доступ и мгновенно обрабатывать запросы.
Пространственная локальность
Принцип пространственной локальности несколько сложней. Когда пользователь выполняет какие-то действия, процессор помещает в кэш не только данные, которые находятся по одному адресу, но еще и данные, которые находятся в соседних адресах. Логика проста — если пользователь работает с какой-то программой, то ему, возможно, понадобятся не только те команды, которые уже использовались, но и сопутствующие «слова», которые располагаются рядом.
Набор таких адресов называется строкой (блоком) кэша, а количество считанных данных — длиной кэша.
При пространственной локации процессор сначала ищет данные, загруженные в кэш, и, если их там не находит, то обращается к оперативной памяти.
Иерархия кэш-памяти
Любой современный процессор имеет в своей структуре несколько уровней кэш-памяти. В спецификации процессора они обозначаются как L1, L2, L3 и т. д.
Если провести аналогию между устройством кэш-памяти процессора и рабочим местом, скажем столяра или представителя любой другой профессии, то можно увидеть интересную закономерность. Наиболее востребованный в работе инструмент находится под рукой, а тот, что используется реже, расположен дальше от рабочей зоны.
Так же организована и работа быстрых ячеек кэша. Ячейки памяти первого уровня (L1) располагаются на кристалле в непосредственной близости от вычислительного ядра. Эта память — самая быстрая, но и самая малая по объему. В нее помещаются наиболее востребованные данные и команды. Для передачи данных оттуда потребуется всего около 5 тактовых циклов. Как правило, кэш-память первого уровня состоит из двух блоков, каждый из которых имеет размер 32 КБ. Один из них — кэш данных первого уровня, второй — кэш инструкций первого уровня. Они отвечают за работу с блоками данных и молниеносное обращение к командам.
Кэш второго и третьего уровня больше по объему, но за счет того, что L2 и L3 удалены от вычислительного ядра, при обращении к ним будут более длительные временные интервалы. Более наглядно устройство кэш-памяти проиллюстрировано в следующем видео.
Кэш L2, который также содержит команды и данные, занимает уже до 512 КБ, чтобы обеспечить необходимый объем данных кэшу нижнего уровня. Но на обработку запросов уходит в два раза больше времени. Кэш третьего уровня имеет размеры уже от 2 до 32 МБ (и постоянно увеличивается вслед за развитием технологий), но и его скорость заметно ниже. Она превышает 30 тактовых циклов.
Процессор запрашивает команды и данные, обрабатывая их, что называется, параллельными курсами. За счет этого и достигается потрясающая скорость работы. В качестве примера рассмотрим процессоры Intel. Принцип работы таков: в кэше хранятся данные и их адрес (тэг кэша). Сначала процессор ищет их в L1. Если информация не найдена (возник промах кэша), то в L1 будет создан новый тэг, а поиск данных продолжится на других уровнях. Для того, чтобы освободить место под новый тэг, информация, не используемая в данный момент, переносится на уровень L2. В результате данные постоянно перемещаются с одного уровня на другой.
С кэшем связан термин «сет ассоциативности». В L1 блок данных привязан к строкам кэша в определенном сете (блоке кэша). Так, например, 8-way (8 уровень ассоциативности) означает, что один блок может быть привязан к 8 строкам кэша. Чем выше уровень, тем выше шанс на попадание кэша (процессор нашел требуемую информацию). Есть и недостатки. Главные — усложнение процесса и соответствующее снижение производительности.
Также при хранении одних и тех же данных могут задействоваться различные уровни кэша, например, L1 и L3. Это так называемые инклюзивные кэши. Использование лишнего объема памяти окупается скоростью поиска. Если процессор не нашел данные на нижнем уровне, ему не придется искать их на верхних уровнях кэша. В этом случае задействованы кэши-жертвы. Это полностью ассоциативный кэш, который используется для хранения блоков, вытесненных из кэша при замене. Он предназначен для уменьшения количества промахов. Например, кэши-жертвы L3 будут хранить информацию из L2. В то же время данные, которые хранятся в L2, остаются только там, что помогает сэкономить место в памяти, однако усложняет поиск данных: системе приходится искать необходимый тэг в L3, который заметно больше по размеру.
В некоторых политиках записи информация хранится в кэше и основной системной памяти. Современные процессоры работают следующим образом: когда данные пишутся в кэш, происходит задержка перед тем, как эта информация будет записана в системную память. Во время задержки данные остаются в кэше, после чего их «вытесняет» в ОЗУ.
Итак, кэш-память процессора — очень важный параметр современного процессора. От количества уровней кэша и объема ячеек сверхбыстрой памяти на каждом из уровней, во многом зависит скорость и производительность системы. Особенно хорошо это ощущается в компьютерах, ориентированных на гейминг или сложные вычисления.
Низкоуровневая модель памяти
Авторизуйтесь
Низкоуровневая модель памяти
В прошлой статье была рассмотрена высокоуровневая часть модели памяти. В этой статье подробно описано, что на самом деле происходит с памятью в компьютере на примере Intel x86_64.
Обзор
Схематично и очень упрощённо модель памяти выглядит так:
Статья детально описывает эту модель, а также принципы работы виртуальной памяти в защищённом режиме.
Регистры
Регистр процессора — блок памяти, расположенный прямо на кристалле процессора и образующий сверхбыструю оперативную память (СОЗУ). В x86_64 размеры регистра, за исключением векторных, варьируются от 8 до 64 бит.
Программа может быстро работать только с памятью, находящейся в регистрах процессора. Даже для простого инкремента ячейки памяти из RAM (Random Access Memory) необходимо выполнить 3 операции: сначала загрузить эту ячейку из RAM или кэша в регистр, затем инкрементировать и после выгрузить ячейку из регистра обратно в RAM или кэш.
Количество и специализация регистров зависит от архитектуры процессора, но типы регистров можно разделить на две группы: регистры общего назначения, необходимые для хранения и использования переменных, принадлежащих программам, и специализированные регистры, хранящие различную метаинформацию, которая может даже менять поведение процессора.
17–19 декабря, Онлайн, Беcплатно
Если с регистрами общего назначения всё понятно, то вот некоторые специализированные регистры в x86_64 и их назначение:
Также существуют векторные регистры общего назначения (ZMM0–ZMM31), необходимые для математических операций над несколькими числами (вектором) одновременно.
L1–L3 кэширование
Многогигабайтную память в процессор не засунуть, поэтому в нём есть относительно небольшое количество регистров и кэш, а остальная память хранится в RAM.
Но RAM имеет очень большую задержку (около 230 тактов процессора i7-4770), поэтому часть этой памяти кэшируется в самом процессоре. Кэширование многоуровневое, чем меньше память и непосредственно ближе к регистрам, тем проще её адресовать и тем она быстрее.
L1-кэш находится в каждом ядре процессора, кэширует как данные, так и инструкции (которые в свою очередь тоже являются данными; один и тот же набор двоичного кода может быть интерпретирован и как данные, и как инструкции). Задержка минимальна — 4 такта на i7-4770 и размер 64 КБ (32 КБ на данные и 32 КБ на инструкции) на каждое виртуальное ядро.
L2-кэш также находится в каждом ядре, но кэширует только данные — 12 тактов и 1 МБ на ядро.
L3-кэш — общий для всего процессора, кэширует только данные — 36 тактов и 8 МБ.
Задержка в тактах примерная и не отражает реального положения дел, цифры приведены на основе бенчмарков только для того, чтобы показать относительную разницу кэшей и RAM.
Детали кэширования на примере L1 и Haswell
Кэш L1 представляет собой таблицу из сетов, каждый из которых формируется из записей, состоящих из битов состояния, тега и кэш-линии. Вот урезанная версия такой записи:
Индекс — это номер сета в таблице, а также с 6-го по 11-й биты указателя на память в RAM. Поэтому от расположения в RAM (номер адреса) зависит то, в каком сете будет кэшироваться этот блок памяти размером в кэш-линию.
С 0-го по 5-й биты — это смещение внутри кэш-линии.
Сет состоит из нескольких записей, в случае с Haswell их 8.
Тег — это остальная часть указателя с 12-го бита для нахождения нужной записи в сете.
Биты состояния указывают на то, модифицировалась ли кэш-линия, а также актуальность кэш-линии. У каждого ядра свой L1- и L2-кэш, поэтому их нужно синхронизировать. Для этого и существуют биты состояния. Более подробно на Хабре.
Кэш-линия — это несколько физически подряд расположенных байтов из RAM, в нашем случае 64 байта.
В i7-4770 128 сетов в L1-кэше на одно виртуальное ядро — 64 на данные и 64 на инструкции. Поэтому для индексирования этих кэш-сетов необходимо 6 бит (2^6 = 64).
Всего выходит 1024 записи (128 сетов по 8 записей), в каждой из которых по 64 байта в кэш-линии. В сумме 64 КБ L1-кэша на ядро.
Здесь есть небольшая проблема: если произвести небольшие вычисления, можно понять, что каждые 64 КБ в памяти будут кэшироваться в одном и том же сете. Поэтому использование только каждых 64 КБ или бо́льшей степени двойки, полностью нивелирует профит от использования L1-кэша. Это доказывается многими бенчмарками, но в реальной работе никто так делать не будет. Кэши прочих уровней имеют эту же проблему, только для индекса используются больше бит.
Атомарность
При попытке двух ядер одновременно инкрементировать один и тот же байт RAM памяти, допустим, равный 0, в зависимости от «фазы луны» мы можем получить любое число от 0 до 2. Например, оба процессора прочитали из RAM 0, затем оба инкрементировали свои регистры до 1, затем оба записали 1 обратно в RAM.
Это одна из самых основных проблем многопоточных программ и разных программ с общей памятью.
Решается это добавлением префиксного байта LOCK в начало ассемблерной инструкции (например xaddl), что делает её атомарной. Данная операция посылает сигнал в другие ядра, запрещая использование данных, пока не будет завершена ассемблерная инструкция. Таким образом, пока одно ядро занято инкрементом, другое будет ждать.
Защищённый режим
Во времена DOS-систем процессоры работали в «реальном режиме», где используется сегментная адресация памяти, при которой любому процессу доступна вся память компьютера, и он может выполнить любую допустимую инструкцию процессора. Когда процесс работает в среде ОС монопольно, это очень выгодно с точки зрения производительности, но появляются проблемы при нескольких работающих одновременно процессах. Для того, чтобы один процесс не смог случайно или специально несогласованно использовать память другого процесса или исполнить привилегированную инструкцию, которая может повлиять на работу ОС и других процессов, и был придуман «Защищённый режим».
Для этого во все операции необходимо добавить проверку прав доступа. Права доступа на инструкции определяются через кольца защиты, а памяти — через виртуальную адресацию.
За исключением некоторых тонкостей, ненужных в этой статье, для переключения в защищённый режим x86_64 (есть ещё классический защищённый режим x86) необходимо установить биты PE (Разрешение защиты, бит 0) и PG (Страничный режим, бит 31), включающий MMU, в регистре CR0, а также указатель на таблицу PML4 в регистре CR3 (c 13 по 63 бит). Именно в таблице PML4 и хранится информация об адресах, правах доступа и прочем.
Кольца защиты
В процессорах x86 используется система колец защиты. Каждая инструкция имеет свои требования к правам процесса. Текущий уровень прав выполняющегося процесса указан в таблицах дескрипторов, указатели на которые лежат в соответствующих регистрах. В x86 существует 4 кольца защиты, от полных прав доступа (0) до пользовательских прав (3). Но для переносимости на другие платформы некоторые ОС используют только два кольца. Даже Windows NT, которая раньше была очень даже кроссплатформенной, сейчас имеет редакцию только для x86 и ARM-систем.
Виртуальная адресация
Виртуальная адресация — метод управления памятью компьютера, позволяющий выполнять программы, требующие больше оперативной памяти, чем имеется в компьютере, а также изолировать память процессов друг от друга.
Виртуальный указатель не соответствует физическому указателю на ячейку в RAM. Это сделано для того, чтобы виртуальная память могла быть больше реальной RAM-памяти, например для файла подкачки (физическая память + подкачка явно больше, чем просто физическая память) или поблочного отображения файлов и устройств в память.
А также для того, чтобы при разыменовании указателя проходил процесс проверки прав доступа к этой памяти при трансляции адреса из виртуального в физический, чтобы случайно или специально не залезть в чужую память.
Трансляция адресов
В защищённом режиме сам процессор и L1-кэш работают с виртуальным адресом, а L2, L3 и RAM — с физическим. Трансляцией адресов из виртуального в физический, а также проверкой прав доступа занимается MMU (Memory Management Unit) — блок управления памятью, использующий PML4.
Таблица выглядит следующим образом:
Виртуальный указатель делится на две части: с 12-го по 47-й бит — сдвиги внутри таблиц в PML4, с 0-го по 11-й бит — сдвиг внутри физического адреса для поддержки арифметики указателей.
Указатель на начало PML4-таблицы лежит в CR3 с 12-го по 51-й биты. С 39-го по 47-й бит виртуального указателя — номер страницы из PML4-таблицы, в которой лежит указатель на начало PDPT-таблицы. С 30-го по 38-й бит находится номер страницы из PDPT-таблицы, в которой лежит указатель на начало PD. Аналогично и с PT, но в ней уже лежит физический адрес, к которому добавляется сдвиг виртуального указателя — с 0-го по 11-й биты. В итоге получается физический адрес, по которому MMU и обращается к физической памяти.
Внимательный читатель мог заметить две сложности:
TLB-кэш внутренне схож с LX-кэшами, только служит для трансляции виртуальных адресов и представляет собой таблицу из сетов, внутри которых записи: «виртуальный адрес ↔ физический адрес». PML4 адресована только по физическим адресам, поэтому сама PML4 может кэшироваться только в L2-L3 кэшах.
Сдвиг внутри страницы — 12 бит, поэтому минимальный размер такой страницы — 4 КБ. Процессу очень редко нужны сразу 4 КБ памяти (а меньше выделить у ОС нельзя). Поэтому процессы используют аллокаторы, о которых было сказано в прошлой статье.
Для увеличения скорости трансляции виртуальных адресов можно убрать некоторые промежуточные таблицы, но в таком случае освободившиеся биты будут использованы для сдвига внутри страницы, что увеличивает размер таких страниц. В x86_64 размеры страниц бывают 4 КБ (12 бит), 2 МБ (12 + 9 бит вместо PT), 1 ГБ (12 + 9 + 9 бит вместо PD). Использование большого количества 4 КБ страниц может привести к сильному увеличению размера PML4, которая перестанет помещаться в L2-L3 кэши, что сильно увеличит время разыменования.
Подробнее о TLB на примере Haswell
TLB представляет собой схожую с LX-кэшами структуру. В процессоре Intel Haswell существует два TLB разного уровня. Индексация и тегирование производятся аналогично, но кэш-линия заменена на адрес физической таблицы и её атрибуты и права доступа из PML4, но не всегда полностью (об этом в разделе про Meltdown). TBL тоже многоуровневый и тоже отдельно кэширует указатели на данные и указатели на инструкции.
TLB первого уровня в Haswell делится на ITLB (instructions) и на DTLB (data). Минимальная задержка — 1 такт, размер сета — 4 записи, только для 4 КБ сегментов, либо только для 2 МБ сегментов (зависит от ОС и её настроек). Размер — 32 записи для 2 МБ сегментов и 64 — для 4 КБ.
TLB второго уровня (STLB) — только для данных, задержка — 22 такта, размер сета — 8 записей, размер — 1024 записи для 2 МБ и 4 КБ сегментов одновременно.
При смене контекста TLB приходится сбрасывать из-за возможного совпадения виртуальных адресов.
Ещё немного о кэшировании
По отношению к виртуальной адресации кэши данных и инструкций могут быть поделены на 3 используемых в реальных процессорах типа.
Physically indexed, physically tagged (PIPT) — физически индексируемые и физически тегируемые (тег и индекс берутся из физического адреса). Такие кэши просты и избегают проблем с наложением (aliasing), но они медленны, так как перед обращением в кэш требуется запрос физического адреса в TLB. Этот запрос может вызвать промах в TLB и дополнительное обращение в PML4.
L2 и L3 расположены после MMU, поэтому они могут использовать только этот тип. L1 остаётся либо каждый раз лезть в MMU, что слишком долго, либо использовать другой тип, что L1 и делает.
Virtually indexed, virtually tagged (VIVT) — виртуально индексируемые и виртуально тегируемые. И для тегирования, и для индекса используется виртуальный адрес. Благодаря этому проверки наличия данных в кэше проходят быстрее, не требуя обращения к MMU.
Однако возникает проблема наложения, когда несколько виртуальных адресов соответствуют одному и тому же физическому. В этом случае данные будут закэшированы дважды, что сильно усложняет поддержку когерентности. Другой проблемой являются омонимы, ситуации, когда один и тот же виртуальный адрес (например, в разных процессах) отображает различные физические адреса. Становится невозможно различить такие отображения исключительно по виртуальному индексу.
Возможные решения: сброс кэша при переключении между процессами, требование непересечения адресных пространств процессов, тегирование виртуальных адресов идентификатором адресного пространства (address space ID, ASID) или использование физических тегов. Также возникает проблема при изменении отображения виртуальных адресов в физические: требуется сброс кэш-линий, для которых изменилось отображение.
Virtually indexed, physically tagged (VIPT) — виртуально индексируемые и физически тегируемые. Для индекса используется виртуальный адрес, а для тега — физический. Преимуществом перед первым типом является меньшая задержка, поскольку можно искать кэш-линию одновременно с трансляцией адресов в TLB, однако сравнение тега задерживается до получения физического адреса. Преимуществом перед вторым типом является обнаружение омонимов (homonyms), так как тег содержит физический адрес. Для данного типа требуется больше бит для тега, поскольку индексные биты используют иной тип адресации.
Но даже у VIPT-кэша есть проблема: при изменении кэш-записи в кэше одного ядра или в RAM придётся искать эту же кэш-запись в кэшах других ядер для инвалидации. Но искать придётся по физическому адресу (два одинаковых виртуальных адреса у разных процессов могут указывать на разную физическую память), поэтому использование индексации по виртуальному адресу заставляет пробегать весь кэш и сравнивать каждый тег.
В процессорах Intel это решается индексацией и по виртуальному, и по физическому адресу. Из-за того, что биты с 0-го по 11-й — это смещение внутри страницы в таблице PML4, они совпадают у физического и виртуального адреса. Поэтому используемые для индекса с 6-го по 11-й биты указателя совпадают и у физического, и у виртуального адреса. Благодаря этому L1-кэш имеет тип как PIPT, так и VIPT, но его максимальный размер в процессорах Intel равен минимальному размеру страницы из таблицы PML4, умноженному на количество записей в сете кэша: 64 КБ * 8 = 512 КБ — L1-кэш на все ядра и 64 КБ — L1 на одно ядро. Но увеличение размера записей в сете увеличивает задержку. Поэтому в современных процессорах Intel L1-кэш особо не растёт, ибо это увеличит задержку.
Процесс трансляции
В защищённом режиме разыменование идёт следующим образом:
1. Идём параллельно в L1 и в TLB. Далее весь процесс делится на две части: поиск нужной кэш-линии (п. 2) и трансляция виртуального адреса (п. 3).
2.1. Берём индекс из виртуального указателя и ищем нужный сет. Далее ждём, пока закончится процесс трансляции виртуального адреса (п. 3).
2.2. После получения физического адреса сравниваем теги в записях внутри сета. Если нашлось совпадение, это нужная нам кэш-линия. Если нет, идём дальше в L2.
2.3 Производим аналогичные действия, но уже с кэшами L2 и L3. В них используются только физические адреса, благо такой мы уже получили, ведь процесс трансляции (п. 3) закончился до начала этапа (п. 2.2).
2.4 Если в кэшах не нашлось, идём в медленный RAM.
3.1 Идём в TLB и сравниваем индексы и теги по аналогии с кэшами. Если нашли совпадение, возвращаемся в этап 2.1.
3.2 Если нет (такая ситуация называется Page walk), берём физический адрес из регистра CR3 и повторяем этапы 2.3–2.4, но для поиска и чтения PML4. Если нашли совпадения в таблице, проверяем права доступа и возвращаемся на этап 2.1 с полученным физическим адресом.
3.3 Если совпадения в таблице нет, либо были нарушены права доступа, например, попытка произвести запись, когда доступно только чтение (такая ситуация называется Page fault), то генерируем прерывание. Далее вызывается обработчик прерываний ОС, который решает, что делать с этой ситуацией.
Роль ОС в виртуальной памяти на примере Linux
Вот тут мы плавно подходим к высокоуровневой памяти.
Запуск процесса
Перед запуском процесса ОС выделяет ему сегменты необходимого размера в PML4 (выбирая среди 4 КБ, 2 МБ, 1 ГБ) для стека и статической памяти. У каждого процесса своя таблица PML4. При смене контекста ОС выставит указатель в CR3 на нужную таблицу.
При необходимости процесс может запросить у ОС дополнительный сегмент, например, через системный вызов mmap. ОС при возможности добавит запись в PML4, а также в свои таблицы, и вернёт указатель на начало этой памяти процессу, иначе — вернёт нулевой указатель.
Получается, что на низком уровне автоматическая, статическая, динамическая память — это всё сегменты.
Виртуальная память в ОС
PML4 изначально была создана для виртуальной памяти, но ОС использует её и для других задач.
Файл подкачки
Часть памяти может находиться в файле подкачки. При нехватке памяти ОС может часть этой памяти перенести на диск. Вместе с этим ОС удаляет запись из PML4, чтобы при попытке обратиться к этой памяти был сгенерирован Page Fault. Это было сделано для того, чтобы при попытке обратиться к памяти, которая была отгружена на диск, вызвать ОС, которая загрузит память из диска обратно в ОС, вернёт запись в PML4 и передаст управление обратно процессу, который на сей раз благополучно повторит процесс разыменования.
Файл или устройство, отображённое в память
mmap можно использовать и для отображения файла (в *nix системах устройства — тоже файлы) в память. Для этого создаётся буфер в физической памяти, в которую записывается часть файла, и создаётся запись в PML4. Если процесс выйдет за границу виртуальной памяти в PML4, то ОС загрузит новый кусок файла в буфер и отредактирует PML4, сдвинув виртуальный указатель, но оставив физический.
В итоге для процесса внешне будет казаться, что весь файл загружен в память, когда на самом деле только часть этого файла в буфере.
COW-память и ленивая аллокация
При вызове mmap в некоторых ОС никакой памяти на самом деле не выделяется, только добавляется запись в структурах самой ОС. При первом обращении процесса к ещё не аллоцированной памяти будет Page Fault, во время которого ОС произведёт полную аллокацию. Это удобно в случае, когда процесс аллоцировал память, но никогда её не использовал. В таком случае пройдёт только первый, ленивый и относительно быстрый этап аллокации.
С COW дела обстоят схоже.
Copy On Write память — это память, общая для чтения у нескольких объектов в системе (под объектами имеется в виду что угодно, начиная от объектов в ООП и заканчивая процессами с разделяемой памятью). Если же один из объектов начинает писать в память, то перед этим такая память делится на две части: одна остаётся у всех остальных объектов, а другая становится памятью только для объекта, который хочет её изменить. В итоге мы получаем экономию памяти, а в случае необходимости записи в эту память, мы её копируем.
У всех процессов с COW-памятью в PML4 ставится флаг «только чтение» для того, чтобы при записи вызвать ОС через Page Fault для разделения памяти. Реальные же права доступа на запись ОС хранит в своих таблицах.
Это были несколько примеров того, как ОС по-хитрому использует PML4 для своих нужд.
Meltdown
Во многих современных процессорах обнаружили уязвимость в этой системе виртуальных адресов и кэшей. Её назвали Meltdown.
Ещё немного о PML4
Перед тем как продолжить, рассмотрим немного подробнее таблицу PML4. В ней и в каждой подтаблице есть не только адрес следующей таблицы, но и биты с метаинформацией этой таблицы. Рассмотрим некоторые из них.
Принцип работы
Наконец, перейдём к самому принципу работы уязвимости Metldown.
Ранее уже было написано о спекулятивном исполнении команд в статье об архитектуре процессора. Цитата из статьи: «Спекулятивное исполнение команд — это выполнение команды до того, как станет известно, понадобится эта команда или нет».
Суть атаки в том, что современные ОС всё своё адресное пространство отображают в адресном пространстве каждого пользователя (процесса). Другими словами добавляют в PML4-таблицу процесса указатели на подтаблицы ОС, но с флагом U/S, установленным в 0. Это сделано для того, чтобы при переключении контекста процесса уменьшить количество операций перезаписи CR3 и улучшить кэширование данных ОС с чистыми VIPT- или VIVP-кэшами (PML4 первого процесса → PML4 второго процесса вместо PML4 первого процесса → PML4 ОС → PML4 второго процесса), но эту защиту можно обойти в некоторых процессорах Intel и ARM (у AMD обнаружили только уязвимость Spectre, у которой другой принцип работы).
Некоторые ОС используют одну PML4-таблицу на всю систему, а при переключении контекста меняют только подтаблицы. Отсюда в той же Windows максимальный размер ОЗУ 256 ГБ — максимальный размер таблицы PDP.
При спекулятивном исполнении в уязвимых процессорах часть команд может выполниться до того, как будет проверено, стоит ли бит 0 в U/S флаге. Причём благодаря спекуляции код атаки может быть выполнен из недостижимого кода, например, в ветке else при всегда истинном условии в if, перед тем, как процессору станет известно, что этот код недостижим. После того, как процессор поймёт, что доступа к этой памяти нет, он обнулит результат команд доступа к памяти, сбросив соответствующие регистры, но TLB- и L1-кэш он сбрасывать не будет. А в них уже не хранится флаг U/S, поэтому процесс может получить полный доступ к успевшей закэшироваться закрытой памяти ядра ОС, ведь процессор, который нашёл нужную запись в L1 и TLB, не будет проверять её в PML4. Решается эта проблема либо аппаратно — добавлением флагов из PML4 в TLB, либо программно — удаление таблиц памяти ОС из PML4-процессов, что увеличит время смены контекста и системных вызовов.
Вывод
Это далеко не всё, что можно рассказать про низкоуровневую память и уж тем более про всю архитектуру ПК пусть даже одного x86_64. Это лишь некоторая часть базы, сильно привязанная к конкретной архитектуре, в других архитектурах используются схожие, но не одинаковые подходы.
Для более подробного изучения этой темы вы можете прочитать литературу, например, трёхтомник Э. С. Таненбаума или документы от Intel про x86_64 — благо они есть в свободном доступе — или другую микроархитектуру, а также посмотреть доклад с конференции C++ Russia 2018 для уточнения некоторых мелочей про кэши и виртуальную адресацию, не описанных в этой статье.
