Saturday, August 31, 2013

CPU: Виртуальная память не обязана быть сложной

Это третья статья на тему процессора. Все статьи по теме - тут: label-CPU

Современный процессор должен иметь встроенный MMU, иначе это будет микроконтроллер какой-то.
C MMU можно делать много всяких полезных штук - виртуализацию, защиту, можно запускать Linux и ворочать огромными объемами памяти имея небольшое количество RAM.



Вначале о доступе к памяти и шине. Вспомните навскидку хотя бы два применения восмибитных байтов.
Даже символы с появлением Unicode перестали быть однобайтовыми. Они и в два байта уже не помещаются. Комитет UTC в неизъяснимой мудрости своей выбрал для символов диапазон 0x0-0x10FFFF (про utf8 знаю, но это плохая отмазка).
Так зачем же с упорством, достойным лучшего применения мы 21-м веке делаем байтовый доступ к памяти? Все эти выровненные адреса на шине, чтение смежных блоков endianness...
Мой процессор будет адресовать 32-битные слова (а потом вообще переделаю его на 64 бита).

32-битовое адресное пространство позволяет адресовать 232 слов это 16 Гб. Неплохо.

Процессор будет работать в режиме пользователя или супервизора. В режиме пользователя трансляция адресов будет всегда включена, а в режиме супервизора - всегда отключена (но будет пара инструкций для чтения из памяти user-mode в режиме супервизора).

Размеры страниц.
4 килобайта - мало, 4 мегабайта много. А 216 32-битных слов - в самый раз.
Действительно 256 килобайт - хороший размер страницы.
Слишком мелкая страница создает большой оверхед при программировании дискового контроллера. Слишком большая - меньшую гибкость распределения памяти.

К тому же такой размер страницы позволяет обойтись простой схемой трансляции.
Адрес делится на две равные части по 16 бит. Младшая часть - смещение машинного слова внутри страницы. Старшие 16 бит задают номер страницы.

xZVBb4MgFMc/jccmAtOu13XddtmpS3a2+lQyBIO4aj/9sEItpU12aOyFwP/B4/3+vISArKvuXSZ1+SkyYAEOsy4grwHGz2Gox0HoL4RC0myUkBFamkHjSEoIpmjtiqngHFLlaLlgbrI6KcATtmnCfPWbZqo0xeF40j+AFqW9BsWrMdKo3ubIIE9aphZHCY/hLhxjdntv1ssnm5g7BRyEqBxBQkMPbpE5NVUY53ZCZiAdiVH+c+4S2QRkLYVQ46zq1sCGZ7GWj8febkRP5kjg6j8HDPxvwlpT+tF/HPK22ulSL53bl1TBtk7SYb3XfWPOg1TQ3axhItPNBqICJfvBcuOwscL0GbJ9tp+eF1m7yrOnJUZLjH/FKfMErCeG+To/8fhFnjeghi3cduMcJqDVA1148lwgyKPWbPrKl0ZzU158iVrLi0gr92+BZeSxkyvo+A7okYeO4lnRUfww9thnj+ZlXz2Mfemxh7Oi6+90JnS9nP6TY+zsvyebPw==

В процессоре будет полностью ассоциативный TLB-кеш на 8 36-разрядных дескрипторов.
Каждый дескриптор хранит 16 старших бит физического адреса страницы, 3 бита прав доступа (read|wtite|execute), dirty-бит, показывающий, что в страницу производилась запись, и 16 бит логического номера страницы, описываемой этим дескриптором.

32-битный логический адрес в user-mode проходит через блок трансляции адреса. При этом:
  • старшие 16 бит адреса сравниваются со всеми восьмью элементами TLB. Если нет совпадений, генерируется исключение tlb_fault.
  • при наличии совпадения (оно должно быть ровно одно) проверяются атрибуты доступа (RWX). Если страница не поддерживает нужных атрибут доступа, генерируется исключение page_fault.
  • если текущая операция write, в дескрипторе устанвливается бит dirty.
  • 16 бит физического ареса из дескриптора комбинируются с 16-ю младшими битами логического адреса для получения физического адреса, который появится на шине.


Алгоритм работы MMU

const int MODE_SUPERVISOR = 0;
const int MODE_USER = 1;

const int PAGE_ACCESS_READ = 1;
const int PAGE_ACCESS_WRITE = 2;
const int PAGE_ACCESS_EXECUTE = 4;
const int PAGE_DIRTY = 8;

int resolve_address(int v_addr, int mode, int acces) {
    if (mode == MODE_SUPERVISOR)
       return v_addr;
    int& descriptor = tlb.find((unsigned int)v_addr >> 16);
    if (descriptor == NOT_FOUND_VALUE)
       return generate_trap(TLB_FAULT, v_addr);
    if ((descriptor & access) == 0)
       return generate_trap(PAGE_FAULT, v_addr);
    if (access & PAGE_ACCESS_WRITE)
       descriptor |= PAGE_DIRTY;
    return (descriptor & 0xffffffff00000000) | (v_addr & 0xffffffff);
}

В режиме супервизора TLB доступен как 8 регистров ключей и 8 регистров с правами доступа и базовым физическим адресом.

Обработчик исключения TLB-fault делает следующие действия:

  • Выбирает дескриптор TLB для выгрузки. Как он это будет делать не важно. Это может быть или случайный дескриптор, или дескрипторы могут выгружаться по кругу, или будет организована какая-то LRU-очередь - не важно. Главное, чтобы один и тот же дескриптор не выгружался все время подряд или через один. Иначе процессор не сможет выполнить очередную инструкцию. Т.к. инструкции никогда не требуется больше двух разных адресов.
  • Проверяет бит dirty. В большинстве случаев все дескрипторы адресного пространства хранятся в каком-то страничном каталоге, и тогда бит dirty просто записывается в элемент этого каталога. Тут можно использовать оптимизацию и запоминать в неиспользуемом бите дескриптора, что страница уже грязная, и в этом случае игнорировать бит dirty.
  • Загружает выбранный дескриптор, например, из страничного каталога.
  • Выходит из исключения, перезапуская команду.
Поскольку генерация исключения переводит процессор в режим супервизора, виртуальная память при этом выключается. И обработчик искючения никак не зависит от состояния TLB и не может неявно влиять на него.

Обработчик исключения PAGE-fault может подргузить отсутствующую страницу виртуальной памяти или завершить процесс при ошибке защиты.

Резюме

  • 8 регистров TLB позволяет потоку иметь рабочий набор памяти объемом в 2 мегабайта (8 * 65536 * 4), доступ к которому будет производиться без оверхеда, полностью в регистрах процессора.
  • 8 * 2 = 16 регистров TLB могут быть частью контекста потока или инвалидироваться и загружаться по требованию.
  • Программно-управляемый TLB позволяет процессору оставаться в лимитах RISC-архитектуры и позволяет операционной системе гибко выбирать стратегии управления доступом к памяти.

1 comment:

  1. TODO:
    1. Добавить в key_16_bit еще 16 bit address space id чтобы не сбрасывать tlb при переклчениях между процессами (актуально для OS на микроядре)
    2. Добавить сетчики обращений и пирамиду из digital comparators, которая конвейерно вычисляет индекс самого ненужного входа tlb (с отставанием в три такта, что нерпинципиально, т.к. на вход в режим супервизора и активацию обработчика tlb_fault примерно стольно тактов и потратится).
    При каждом обращении все счетчики декрементируются, после чего счетчик совпавшего tlb-входа устанавливается в FF. Это позволит эффективно определять кандидата на вытеснение из TLB.

    ReplyDelete