FreeBSD, 04 лекция (от 23 октября)

Материал из eSyr's wiki.

Под управлением памятью мы понимаем вопросы аллокации.

Три задачи:

1. маллок приложений -- практически не коснемся
1. маллок внутри ядра, там же мы тоже хотим не вруную памятью заниматься
1. как ОС создает процессу виртуальное адресное пространство.

Еще одна тема -- как виртуальная память соотносится с физической.

В компьютере есть какая-то память в слотах, у неё есть физические адреса. Если мы переставим из одного слота другой образуются дырки, и программировать в таких условиях очень тяжело. Во всех процессорах,под которые пишутся ОС общего назначения есть MMU -- транслятор виртуальных адресов в физические.

Ядро процессора в какой-то момент переходит в режим, когда используются виртуальные адреса, а не физические.

Процессор постоянно обращается к MMU.

Какие то части виртуального пространства имеют отображение в физпамять, какие-то не имеют. Те которые не имеют вызовут у MMU трап.

Страница -- гранулярность того, как мы можем делать отображение виртуальной памяти в физическую. Отображение само хранится тоже в памяти. MMU надо сходить к физическому адресу, прописаному в регистре процессора.

У процессора есть дополнительный кэш, специально предназначенный для MMU.

Картинка виртуального пространства процесса.

Нулевой указатель никогда не замаплен.

дальше замаплен скомпилированный код -- program text

Дальше инициализированные данные.

Дальше идет heap -- память, которую процесс просит у ядра динамически.

Наверху есть конец памяти доступный процессу.

В FreeBSD есть утилита procstat, которая позволяет увидеть это все своими глазами.

Удобно смотреть на /rescue/cat , потому что для динамически слинкованных приложений оно выглядит слишком сложно.

Как растет стек?

Когда page fault происходит по следующей странице за концом стека, этот page fault не завершает программу, а ядро аллоцирует еще одну страничку и программа проолжает работать.

Важное замечание -- ядро никак не может узнать, что вы перестали стеком пользоваться, и никогда обратно их не освободит, в лучшем случае высвопит.

Как растет куча?

Исторически был вызов sbrk, который позволял руками уедличивать и уменьшать указатели конца кучи.

Старые маллоки на нем были основаны. Была проблема -- данные могли быть аллоцированы в конце, а до них все уже освободилось, получалась потеря пространства.

Современные маллоки основаны на mmap.

mmap можно делать не только для файлов, но и для просто регионов памяти.

Современные маллоки работают на mmap, и под каждое ядро процессора делают свою арену.

В FreeBSD всегда был очень хороший либцшный маллок. Сейчас jemalloc. Настолько эффективный, что яндекс с трудом переходит на линукс, потому что они запускают приложение на линуксе и оно жрет в полтора раза больше памяти.

Фейсбук поступил хитрее -- у них работает автор этого маллока и специально для них пишет версию под линуксом.

Пример карты памяти динамически слинкованной программы.

В прошлой лекции у нас был указатель на vm_space, которая состоит из vm_map, vm_pmap -- одна отвечает за виртуальную память, другая за реальную.

Начнем придумывать как vm_map будет выглядеть.

vm_map -- список многочисленных entry, начало и конец. Каждая map entry должна что-то иметь под собой, какой-то объект, который описывает то, что под ней лежит. Эта структура vm_object, она хранит уже реальные страницы, к которым можно доступиться. Также обжект хранит пейджер -- механизм, который позволяет загружать страницы, когда это требуется. vm_page появляются в vm_object по мере page fault.

Так как страниц может быть очень много, они реализованы в виде дерева, с помощью алгоритма радикс.

Раз уж мы дошли до страниц -- это структура, отображающая физическую страницу памяти. Они создаются при старте системы, и дальше могут быть отданы объектам. Страница может принадлежать только одному объекту.

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

Самый простой объект -- анонимный, за ним ничего не стоит.

у него есть дефолт пейджер -- пустой пейджер, который не умеет ни сбрасывать страницы, не аллоцировать.

Когда системе становится плохо и ей хочется свопится, все анонимные пейджи записываются в своп пейджи.

Более сложный обжект vnode object. Есть еще другие объекты. vnode object за собой скрывает файл. Если файл открывался, то в ядре для него есть vnode.

Когда мы делаем mmap любая страница из файла будет вычитываться и класться в память.

Сколько бы вы программ не открыли, они все будут обращаться к одному объекту.

После форка у потомка будет свое адресное пространство, но будет приходить в тот же vnode object. Но, как только процесс совершит запись, то создастся shadow обжект. В топе мы видимо сколько бы съел процесс, если бы он был совсем один.

Шэдоу обжекты порождают кучу неконсистентности.

Было бы здорово эту штуку оптимизировать.

Делаются локальные оптимизации.

Сам по себе маллок, который в файле kern_malloc.c, он очень простой и очень тонкий, всю работу за него выполняет другой слой. См блоксхему. Сначала смотрим, защищена ли память мемгардами, если используем, то уходим в cпециальный модуль. Аналогично в конце можем уйти в редзон.

В нормальном ядре все проще -- если размер больше пейджсайз, то вызываем uma_large_malloc

Если меньше, то ищем ближайшую степень двойки, и аллоцируем из ума_зон.

Чтоже такое uma?

Uma это зонный аллокатор.

Плиточный аллокатор, который нарезает очередную арену на кусочки и начинает их возвращать. Берет у ядра страницу, режет на кусочки. Держит информацию аллоцированы или нет, храня в конце страницы небольшую структуру с описанием.

Иногда может уносить эту структуру в отдельный слаб, но это хуже с точки зрения процессорного кэша.

В первую очередь зона представляет собой кег. Три списка -- список полных слабов, частично пустых, пустых. Если все слабы полны, то ума обращается к вм и просит еще одну страницу.

Зона реализует кэши.

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

Кэш представляет собой очень простую структуру -- два ведра -- пустое и полное. Как только одно из них заполняется или доходит до нуля, мы их меняем местами.

Ведро из себя представляет: сколько максимум записей, сколько текущее количество, и вектор из указателей в глубину слаба, и обеспечивают быструю аллокацию.

Когда у кега заканчиваются страницы, он их просто берет у вм.

Когда vm page аллоцируются, то они помечаются цветами -- это те страницы, которые гарантированно будут попадать в разные линии кэша. Когда процесс требует очередную страницу то вм старается выдать ему следующий цвет после того цвета, которые он брал последним, а если такого нет, то случайный. Если пропустили один цвет, то тоже какая-то оптимизация может получиться. (Обсуждение про то, что в современных процессорах это неактуально. См. ссылку на книжку в конце.)

Есть еще аллокатор из NetBSD vmem(9)

Универсальный аллокатор. Ему дается ресурс, он с ним может работать. В ядре FreeBSD он используется для vm map самого ядра. Потому что у ядра линейный список entry уже неудобен.

Процессы делают mmap доволно редко. Поэтому линейный список из vmmap entry вполне удовлетворителен.

Curt Schimmel UNIX systems for modern architectures