Прежде чем мы закончим наше исследование виртуализации памяти, давайте подробнее рассмотрим, как объединяются целые системы виртуальной памяти. Мы видели ключевые элементы таких систем, включая многочисленные виды таблиц страниц, взаимодействие с TLB (иногда даже обрабатываемое самой операционной системой) и стратегии для принятия решения о том, какие страницы следует сохранить в памяти, а какие выбросить. Однако существует множество других функций, которые включают в себя полную систему виртуальной памяти, включая многочисленные функции для повышения производительности, функциональности и безопасности. И таким образом, суть главы:
КАК СОЗДАТЬ ПОЛНОЦЕННУЮ ВИРТУАЛЬНУЮ СИСТЕМУ
Какие функции необходимы для реализации полной системы виртуальной памяти? Как они повышают производительность, повышают безопасность или иным образом улучшают систему?
Мы сделаем это, охватив две системы. Первый - один из самых ранних примеров “современного” менеджера виртуальной памяти, который был найден в операционной системе VAX / VMS [LL82], разработанной в 1970-х и начале 1980-х годов; удивительное количество методов и подходов из этой системы сохранилось до наших дней, и поэтому его стоит изучить. Некоторые идеи, даже те, которым 50 лет, все еще заслуживают внимания, мысль, которая хорошо известна тем, кто работает в большинстве других областей (например, физика), но должна быть изложена в технологически ориентированных дисциплинах (например, информатика).
Второе - это Linux, по причинам, которые должны быть очевидны. Linux является широко используемой системой и эффективно работает на таких небольших и маломощных системах, как телефоны, и в наиболее масштабируемых многоядерных системах, имеющихся в современных центрах обработки данных. Таким образом, его виртуальная машина должна быть достаточно гибкой, чтобы успешно работать во всех этих сценариях. Мы обсудим каждую систему, чтобы проиллюстрировать, как концепции, изложенные в предыдущих главах, объединяются в полноценном менеджере памяти.
23.1 VAX/VMS Virtual Memory
Архитектура миникомпьютера VAX-11 была представлена в конце 1970-х годов Digital Equipment Corporation (DEC). DEC была крупным игроком в компьютерной индустрии в эпоху мини-компьютеров; к сожалению, ряд неверных решений и появление ПК медленно (но верно) привели к их гибели [C03]. Архитектура была воплощена в ряде реализаций, включая VAX-11/780 и менее мощный VAX-11/750.
Операционная система для этих компьютеров была известна как VAX/VMS (или просто VMS), одним из основных архитекторов которой был Дейв Катлер (Dave Cutler), который позже возглавил усилия по разработке Microsoft Windows NT [C93]. У VMS была общая проблема, заключающаяся в том, что они будут работать на широком спектре машин, включая очень недорогие VAXen (да, это правильное множественное число) и чрезвычайно высокопроизводительные и мощные машины в одном семействе архитектуры. Таким образом, ОС должна была иметь механизмы и политики, которые бы работали (и работали бы хорошо) в этом огромном диапазоне систем. В качестве дополнительной проблемы VMS являются отличным примером программных инноваций, используемых для сокрытия некоторых присущих архитектуре недостатков. Хотя ОС часто полагается на аппаратное обеспечение для создания эффективных абстракций и иллюзий, иногда разработчики аппаратного обеспечения не совсем всё понимают правильно; в аппаратном обеспечении VAX мы увидим несколько примеров этого и то, что операционная система VMS делает для создания эффективной, работающей системы, несмотря на эти аппаратные недостатки.
Оборудование для управления памятью
VAX-11 предоставлял 32-разрядное виртуальное адресное пространство для каждого процесса, разделенное на 512-байтовые страницы. Таким образом, виртуальный адрес состоял из 23-битной VPN и 9-битного смещения. Кроме того, два верхних бита VPN использовались для определения того, в каком сегменте находится страница; таким образом, система представляла собой гибрид используя paging и segmentation, как мы видели ранее.
Нижняя половина адресного пространства была известна как “пространство процесса” и уникальна для каждого процесса. В первой половине пространства процесса (известной как P0) находится пользовательская программа, а также куча, которая растет вниз. Во второй половине пространства процесса (P1) мы находим стек, который растет вверх. Верхняя половина адресного пространства известна как system space (S), хотя используется только половина этого пространства. Защищенный код и данные ОС находятся здесь, и таким образом ОС может предоставлять общий доступ к этим участкам для всех процессов.
Одной из основных проблем разработчиков VMS был невероятно малый размер страниц в аппаратном обеспечении VAX (512 байт). Этот размер, выбранный по историческим причинам, приводит к фундаментальной проблеме чрезмерного увеличения простых линейных таблиц страниц. Таким образом, одной из первых целей разработчиков VMS было обеспечить, чтобы VMS не перегружали память таблицами страниц.
Система уменьшила нагрузку таблиц страниц на память двумя способами. Во-первых, разделяя адресное пространство пользователя на два, VAX-11 предоставляет таблицу страниц для каждой из этих областей (P0 и P1) для каждого процесса; таким образом, пространство таблицы страниц не требуется для неиспользуемой части адресного пространства между стеком и кучей. Регистры base и bounds используются, как и следовало ожидать; base регистр содержит адрес таблицы страниц для этого сегмента, а bounds содержит его размер (т.е. количество записей таблицы страниц).
ОФФТОП: ПРОКЛЯТИЕ УНИВЕРСАЛЬНОСТИ
Операционные системы часто сталкиваются с проблемой, известной как проклятие универсальности, когда на них возлагается задача общей поддержки широкого класса приложений и систем. Фундаментальным результатом проклятия является то, что ОС вряд ли будет поддерживать какую-либо одну установку очень хорошо. В случае VMS проклятие было очень реальным, так как архитектура VAX-11 была реализована в ряде различных реализаций. Это не менее реально сегодня, когда ожидается, что Linux будет хорошо работать на вашем телефоне, телевизионной приставке, ноутбуке, настольном компьютере и высокопроизводительном сервере, на котором выполняются тысячи процессов в облачном центре обработки данных.
Во-вторых, ОС еще больше снижает нагрузку на память, размещая таблицы пользовательских страниц (для P0 и P1, по две на процесс) в виртуальной памяти ядра. Таким образом, при выделении или увеличении таблицы страниц ядро выделяет пространство из своей собственной виртуальной памяти в сегменте S. Если память испытывает сильное давление, ядро может перенести страницы этих таблиц на диск, тем самым делая физическую память доступной для других целей.
Размещение таблиц страниц в виртуальной памяти ядра означает, что преобразование адресов еще более усложняется. Например, чтобы перевести виртуальный адрес в P0 или P1, аппаратное обеспечение должно сначала попытаться найти запись таблицы страниц для этой страницы в своей таблице страниц (таблица страниц P0 или P1 для этого процесса); при этом, однако, аппаратное обеспечение может сначала обратиться к системной таблице страниц (которая находится в физической памяти); после завершения этого перевода аппаратное обеспечение может узнать адрес страницы таблицы страниц, а затем, наконец, узнать адрес желаемого доступа к памяти. Все это, к счастью, выполняется быстрее с помощью аппаратно-управляемых TLB VAX, которые обычно (надеюсь) обходят этот трудоемкий поиск.
Реальное Адресное Пространство
Одним из важных аспектов изучения VMS является то, что мы можем видеть, как строится реальное адресное пространство (рис. 23.1.) До сих пор мы предполагали простое адресное пространство, состоящее только из кода пользователя, пользовательских данных и кучи, но, как мы можем видеть, реальное адресное пространство заметно сложнее.
Например, сегмент кода никогда не начинается со страницы 0. Вместо этого эта страница помечена как недоступная, чтобы обеспечить некоторую поддержку для обнаружения обращений с нулевым указателем (null-pointer accesses). Таким образом, одной из проблем при проектировании адресного пространства является поддержка отладки, которую недоступная нулевая страница предоставляет здесь в той или иной форме.
Возможно более важно то, что виртуальное адресное пространство ядра (т.е. его структуры данных и код) является частью адресного пространства каждого пользователя. При переключении контекста ОС изменяет регистры P0 и P1, указывая на соответствующие таблицы страниц процесса, который скоро будет запущен; однако это не изменяет регистры base и bounds сегмента S, и в результате “одинаковые” структуры ядра отображаются в адресное пространство каждого пользователя.
Ядро отображается в каждое адресное пространство по ряду причин. Эта конструкция облегчает жизнь ядру; когда, например, ОС получает указатель из пользовательской программы (например, при системном вызове write()), легко скопировать данные из этого указателя в свои собственные структуры. ОС естественно пишется и компилируется, не беспокоясь о том, откуда берутся данные, к которым она обращается. Если бы, напротив, ядро было полностью размещено в физической памяти, было бы довольно сложно выполнять такие действия, как сброс (подкачка) страниц таблицы страниц на диск; если бы ядру было предоставлено собственное адресное пространство, перемещение данных между пользовательскими приложениями и ядром снова было бы сложным и болезненным. При такой конструкции (в настоящее время широко используемой) ядро выглядит почти как библиотека для приложений, хотя и защищенная.
Последний момент, касающийся этого адресного пространства, касается защиты. Очевидно, что ОС не хочет, чтобы пользовательские приложения читали или записывали данные или код ОС. Таким образом, аппаратное обеспечение должно поддерживать различные уровни защиты страниц памяти, чтобы обеспечить безопасность. VAX реализует это, указывая в битах защиты в таблице страниц, на каком уровне привилегий должен находиться процессор, чтобы получить доступ к определенной странице. Таким образом, системные данные и код настроены на более высокий уровень защиты, чем пользовательские данные и код; попытка доступа к такой информации из пользовательского кода приведет к срабатыванию специального trap на уровне ОС и (как вы уже догадались) вероятному завершению процесса нарушителя.
Замена страницы
Запись таблицы страниц (PTE) в VAX содержит следующие биты:
- valid бит
- protection field (4 бита)
- бит изменения (или dirty)
- поле, зарезервированное для использования операционной системой (5 бит)
- и, наконец, номер физического кадра (PFN) для хранения местоположения страницы в физической памяти
Проницательный читатель может заметить: нет reference бита! Таким образом, алгоритм замены VMS должен обходиться без аппаратной поддержки для определения того, какие страницы активны.
Разработчики также были обеспокоены memory hogs, программами, которые используют много памяти и затрудняют запуск других программ. Большинство политик, которые мы рассмотрели до сих пор, подвержены такому засорению; например, LRU - это глобальная политика, которая несправедливо распределяет память между процессами.
ОФФТОП: ЭМУЛЯЦИЯ ОПОРНЫХ БИТОВ
Как оказалось, вам не нужен reference бит в аппаратном обеспечении, чтобы получить некоторое представление о том, какие страницы используются в системе. Фактически, в начале 1980-х годов Бабаоглу и Джой показали, что protection биты на VAX могут использоваться для эмуляции reference битов [BJ81]. Основная идея: если вы хотите получить некоторое представление о том, какие страницы активно используются в системе, отметьте все страницы в таблице страниц как недоступные (но сохраняйте информацию о том, какие страницы действительно доступны в процессе, возможно, в области “зарезервированное поле ОС” записи таблицы страниц). Когда процесс обратиться к странице, это вызовет соответствующий trap ОС; затем ОС проверит, действительно ли страница должна быть доступна, и если да, вернет страницу к ее обычной защите (например, только для чтения или для чтения-записи). Во время замены ОС может проверить, какие страницы остаются помеченными как недоступные, и, таким образом, получить представление о том, какие страницы в последнее время не использовались. Ключом к этой “эмуляции” reference битов является сокращение накладных расходов при сохранении хорошего представления об использовании страниц. Операционная система не должна быть слишком агрессивной в маркировке недоступных страниц, иначе накладные расходы будут слишком высокими. ОС также не должна быть слишком пассивной в такой разметке, иначе на все страницы будeт ссылаться какой-то процесс; ОС снова не будет иметь представления, какую страницу удалить.
Для решения этих двух проблем разработчики разработали сегментированную политику замены FIFO (segmented FIFO replacement policy) [RL81]. Идея проста: у каждого процесса есть максимальное количество страниц, которые он может хранить в памяти, известное как размер его резидентного набора (resident set size - RSS). Каждая из этих страниц хранится в списке FIFO; когда процесс превышает свой RSS, страница которая попала в очередь первой, удаляется. FIFO не нуждается в какой-либо поддержке со стороны аппаратного обеспечения, и поэтому его легко реализовать.
Конечно, чистый FIFO работает не особенно хорошо, как мы видели ранее. Чтобы повысить производительность FIFO, VMS представили два списка secondchance, в которых страницы размещаются перед удалением из памяти, в частности глобальный cleanpage free list и dirty-page list. Когда процесс P превышает свой RSS, страница удаляется из очереди FIFO процесса; если она clean (не изменена), она помещается в конец списка чистых страниц; если dirty (изменена), она помещается в конец списка грязных страниц.
Если другому процессу Q нужна свободная страница, он забирает первую свободную страницу из глобального списка свободных страниц (global cleanpage free list). Однако, если исходный процесс P хочет получить доступ к этой странице (faults) до того как другой процесс запросил к ней доступ, P удаляет ее из списка свободных (или загрязненных), что позволяет избежать дорогостоящего доступа к диску. Чем больше эти глобальные списки second-chance, тем ближе производительность сегментированного алгоритма FIFO к LRU [RL81].
Другая оптимизация, используемая в VMS, также помогает преодолеть небольшой размер её страниц. В частности, с такими маленькими страницами дисковый ввод-вывод во время обмена может быть крайне неэффективным, поскольку диски лучше справляются с большими передачами. Чтобы повысить эффективность операций ввода-вывода при подкачке, VMS добавляют ряд оптимизаций, но наиболее важной является кластеризация. С помощью кластеризации VMS группируют большие пакеты страниц из глобального грязного списка и записывают их на диск одним махом (таким образом, делая их чистыми). Кластеризация используется в большинстве современных систем, так как свобода размещения страниц в любом месте пространства подкачки позволяет ОС группировать страницы, выполнять меньшее и большее количество операций записи и, таким образом, повышать производительность.
Другие Изящные Трюки
У VMS было два других стандартных трюка: обнуление требований (demand zeroing) и копирование при записи (copy-on-write). Теперь мы опишем эти lazy (ленивые) оптимизации. Одной из форм laziness в VMS (и большинстве современных систем) является требование обнуления страниц (demand zeroing). Чтобы лучше понять это, давайте рассмотрим пример добавления страницы в ваше адресное пространство, скажем, в вашу кучу. В наивной реализации ОС отвечает на запрос о добавлении страницы в вашу кучу, находя страницу в физической памяти, обнуляя ее (требуется для обеспечения безопасности; в противном случае вы могли бы видеть, что было на странице, когда ее использовал какой-либо другой процесс!), а затем сопоставляя ее с вашим адресным пространством (т.e. настраивая таблицу страниц для ссылки на эту физическую страницу по желанию). Но наивная реализация может быть дорогостоящей, особенно если страница не используется процессом.
При demand zeroing ОС вместо этого выполняет очень мало работы при добавлении страницы в ваше адресное пространство; она помещает запись в таблицу страниц, которая помечает страницу недоступной. Если затем процесс считывает или записывает страницу, в ОС срабатывает trap. При обработке trap ОС замечает (обычно через некоторые биты, отмеченные в сегменте “зарезервировано для ОС” записи таблицы страниц), что на самом деле это страница с нулевым запросом; на этом этапе ОС выполняет необходимую работу по поиску физической страницы, ее обнулению и отображению в адресное пространство процесса. Если процесс никогда не обращается к странице, вся такая работа исключается, что является преимуществом политики demand zeroing.
Еще одна интересная оптимизация, найденная в VMS (и, опять же, практически в каждой современной ОС), - это копирование при записи (copy-on-write, сокращенно COW). Идея, которая, по крайней мере, восходит к операционной системе TENEX [BB +72], проста: когда ОС нужно скопировать страницу из одного адресного пространства в другое, вместо того, чтобы копировать ее, она может отобразить ее в целевое адресное пространство и пометить ее только для чтения в обоих адресных пространствах. Если оба адресных пространства только читают страницу, никаких дальнейших действий не предпринимается, и, таким образом, ОС реализовала быстрое копирование без фактического перемещения каких-либо данных. Однако, если одно из адресных пространств действительно попытается выполнить запись на страницу, сработает trap в ОС. Затем ОС заметит, что страница является страницей COW, и, таким образом (лениво) выделит новую страницу, заполнит ее данными и отобразит эту новую страницу в адресном пространстве процесса. Затем процесс продолжается, и теперь у вас есть собственная личная копия страницы.
COW полезен по ряду причин. Применяя copy-on-write, любая общая библиотека может быть отображена в адресные пространства многих процессов, экономя ценное пространство памяти. В системах UNIX COW еще более важен из-за семантики fork() и exec(). Как вы, возможно, помните, fork() создает точную копию адресного пространства вызывающего его процесса; при большом адресном пространстве создание такой копии происходит медленно и требует больших затрат данных. Что еще хуже, большая часть адресного пространства немедленно перезаписывается последующим вызовом exec(), который накладывает адресное пространство вызывающего процесса на адресное пространство программы, которая скоро будет выполнена. Вместо этого выполняя copy-on-write в fork(), ОС избегает большей части ненужного копирования и, таким образом, сохраняет правильную семантику при одновременном повышении производительности.
СОВЕТ: БУДЬТЕ ЛЕНИВЫ
Лень может быть достоинством как в жизни, так и в операционных системах. Лень может отложить работу на потом, что выгодно в операционной системе по ряду причин. Во-первых, откладывание работы может уменьшить задержку текущей операции, тем самым повышая скорость реагирования; например, операционные системы часто сообщают, что запись в файл выполнена немедленно, и только позже записывают их на диск в фоновом режиме. Во-вторых, и что более важно, лень иногда устраняет необходимость вообще выполнять работу; например, задержка записи до тех пор, пока файл не будет удален, устраняет необходимость вообще выполнять запись. Лень также хороша в жизни: например, отложив свой проект ОС, вы можете обнаружить, что ошибки в спецификации проекта были устранены вашими одноклассниками; однако проект класса вряд ли будет отменен, поэтому быть слишком ленивым может быть проблематичным, что приведет к позднему проекту, плохой оценке и грустному профессору. Не расстраивай профессоров!
23.2 Система Виртуальной Памяти Linux
Теперь мы обсудим некоторые из наиболее интересных аспектов системы виртуальной памяти (VM) Linux. Разработка Linux продвигалась настоящими инженерами, решающими реальные проблемы, возникающие в процессе производства, и, таким образом, большое количество функций постепенно было включено в то, что теперь является полностью функциональной, наполненной функциями системой виртуальной памяти. Хотя мы не сможем обсудить все аспекты VM Linux, мы коснемся наиболее важных из них, особенно тех, где они выходят за рамки того, что можно найти в классических виртуальных системах, таких как VAX/VMS. Мы также попытаемся выделить общие черты между Linux и более старыми системами.
Для этого обсуждения мы сосредоточимся на Linux для Intel x86. В то время как Linux может работать и работает на многих различных процессорных архитектурах, Linux на x86 является его наиболее доминирующим и важным развертыванием и, следовательно, в центре нашего внимания.
Адресное пространство Linux
Как и в других современных операционных системах, а также как VAX/VMS, виртуальное адресное пространство Linux состоит из пользовательской части* (где находятся код пользовательской программы, стек, куча и другие части) и части ядра (где находятся код ядра, стеки, куча и другие части).
*То есть до недавних изменений, вызванных угрозами безопасности. Прочитайте подразделы ниже о безопасности Linux для получения подробной информации об этой модификации
Как и в других системах, при переключении контекста пользовательская часть текущего адресного пространства изменяется; часть ядра одинакова для всех процессов. Как и в других системах, программа, работающая в пользовательском режиме, не может получить доступ к виртуальным страницам ядра; доступ к такой памяти возможен только путем trapping'a ядра и перехода в привилегированный режим.
В классическом 32-разрядном Linux (т.е. Linux с 32-разрядным виртуальным адресным пространством) разделение между пользовательской и привилегированной частями адресного пространства происходит по адресу 0xC0000000, или на третьей четверти адресного пространства. Таким образом, виртуальные адреса от 0 до 0xBFFFFFFF являются виртуальными адресами пользователей; остальные виртуальные адреса (от 0xC0000000 до 0xFFFFFFFF) находятся в виртуальном адресном пространстве ядра. 64-разрядный Linux имеет аналогичное разделение, но в немного других точках. На рисунке 23.2 показано изображение типичного (упрощенного) адресного пространства.
Один интересный аспект Linux заключается в том, что он содержит два типа виртуальных адресов ядра. Первые известны как kernel logical addresses [O16]. Это то, что вы бы сочли обычным виртуальным адресным пространством ядра; чтобы получить больше памяти такого типа, коду ядра просто нужно вызвать kmalloc. Здесь находится большинство структур данных ядра, таких как таблицы страниц, стеки ядра для каждого процесса и так далее. В отличие от большинства других видов памяти в системе, логическую память ядра нельзя перенести на диск.
Наиболее интересным аспектом логических адресов ядра является их связь с физической памятью. В частности, существует прямое сопоставление между логическими адресами ядра и первой частью физической памяти. Таким образом, логический адрес ядра 0xC0000000 преобразуется в физический адрес 0x00000000, 0xC0000FFF в 0x00000FFF и так далее. Это прямое сопоставление имеет два следствия. Во-первых, легко проводить трансляцию между логическими и физическими адресами ядра; в результате эти адреса часто обрабатываются так, как если бы они действительно были физическими. Во-вторых, если фрагмент памяти является непрерывным в логическом адресном пространстве ядра, он также является непрерывным в физической памяти. Это делает память, выделенную в этой части адресного пространства ядра, подходящей для операций, правильная работа которых требует непрерывной физической памяти, например, для передачи ввода-вывода на устройства и с устройств через доступ к памяти каталогов (directory memory access DMA) (о чем мы узнаем в третьей части этой книги).
Другой тип адреса ядра - это kernel virtual address. Чтобы получить память этого типа, код ядра вызывает другой аллокатор, vmalloc, который возвращает указатель на практически непрерывную область нужного размера. В отличие от логической памяти ядра, виртуальная память ядра обычно не является непрерывной; каждая виртуальная страница ядра может отображаться на несмежные физические страницы (и, следовательно, не подходит для DMA). Однако в результате такую память легче выделить, и поэтому она используется для больших буферов, где было бы сложно найти непрерывный большой кусок физической памяти.
В 32-разрядной версии Linux еще одна причина существования виртуальных адресов ядра заключается в том, что они позволяют ядру адресовать более (грубо) 1 ГБ памяти. Много лет назад у машин было гораздо меньше памяти, чем сейчас, и предоставление доступа к более чем 1 ГБ не было нужно. Однако технологии развивались, и вскоре возникла необходимость позволить ядру использовать больший объем памяти. Виртуальные адреса ядра и их отключение от строгого однозначного сопоставления с физической памятью делают это возможным. Однако с переходом на 64-разрядную версию Linux необходимость становится менее острой, поскольку ядро не ограничивается только 1 ГБ виртуального адресного пространства.
Структура таблицы страниц
Поскольку мы сосредоточены на Linux для x86, наше обсуждение будет сосредоточено на типе структуры таблиц страниц, предоставляемой x86, поскольку она определяет, что Linux может и не может делать. Как упоминалось ранее, x86 предоставляет аппаратно-управляемую многоуровневую структуру таблиц страниц с одной таблицей страниц на процесс; ОС просто настраивает сопоставления в своей памяти, указывает привилегированный регистр в начале каталога страниц, а аппаратное обеспечение обрабатывает остальное. Операционная система, как и ожидалось, участвует в процессе создания, удаления и при переключении контекста, в каждом случае проверяя, что аппаратный MMU использует правильную таблицу страниц для выполнения переводов.
Вероятно, самым большим изменением за последние годы является переход с 32-разрядной x86 на 64-разрядную x86, как кратко упоминалось выше. Как видно из системы VAX / VMS, 32-разрядные адресные пространства существуют уже давно, и по мере изменения технологий они, наконец, начали становиться реальным ограничением для программ. Виртуальная память упрощает программирование систем, но в современных системах, содержащих много ГБ памяти, 32 бит уже недостаточно для обращения к каждой из них. Таким образом, следующий скачок стал необходимым.
Переход на 64-разрядную адресацию влияет на структуру таблицы страниц в x86 ожидаемым образом. Поскольку x86 использует многоуровневую таблицу страниц, в современных 64-разрядных системах используется четырехуровневая таблица. Однако полная 64-разрядная природа виртуального адресного пространства еще не используется, а используются только нижние 48 бит. Таким образом, виртуальный адрес можно изобразить следующим образом:
Как вы можете видеть на рисунке, верхние 16 бит виртуального адреса не используются (и, следовательно, не играют никакой роли в переводе адресов), нижние 12 бит (из-за размера страницы 4 КБ) используются в качестве смещения (и, следовательно, просто используются напрямую, а не переводятся), оставляя средние 36 бит виртуального адреса для участия в переводе адресов. Часть адреса P1 используется для индексирования в самый верхний каталог страниц, и перевод выполняется оттуда по одному уровню за раз, пока фактическая страница таблицы страниц не будет проиндексирована P4, что приведет к нужной записи таблицы страниц.
По мере увеличения объема системной памяти будет включаться все больше частей этого объемного адресного пространства, что приведет к пятиуровневым и, в конечном счете, шестиуровневым древовидным структурам таблиц страниц. Только представьте: простой поиск в таблице страниц, требующий шести уровней перевода, просто для того, чтобы выяснить, где в памяти находится определенный фрагмент данных.
Поддержка Больших Страниц
Intel x86 позволяет использовать страницы разных размеров, не только стандартные 4Кб. В частности, последние разработки поддерживают аппаратные страницы объемом 2 МБ и даже 1 ГБ. Таким образом, со временем Linux эволюционировал, позволяя приложениям использовать эти огромные страницы (huge pages как их называют в мире Linux).
Использование огромных страниц, как указывалось ранее, приводит к многочисленным преимуществам. Как видно из VAX/VMS, это уменьшает количество сопоставлений, необходимых в таблице страниц; чем больше страницы, тем меньше сопоставлений.
Однако меньшее количество записей в таблице страниц это не то, что делает huge pages эффективными; эффект, скорее, от лучшей работы TLB и связанного с этим прироста производительности.
Когда процесс активно использует большой объем памяти, он быстро заполняет TLB переводами адресов. Если эти переводы предназначены для страниц объемом 4 КБ, то можно получить доступ только к небольшому объему общей памяти, не вызывая срабатывания TLB miss. Результатом для современных рабочих нагрузок с “большой памятью”, выполняемых на машинах с большим количеством ГБ памяти, является заметная стоимость производительности; недавние исследования показывают, что некоторые приложения тратят 10% своих циклов на обслуживание пропусков TLB [B+13].
Huge pages позволяют процессу получать доступ к большому объему памяти без срабатывания TLB miss, используя меньшее количество слотов в TLB, и, таким образом, являются главным преимуществом. Однако у huge pages есть и другие преимущества: существует более короткий путь TLB miss, что означает, что, когда происходит TLB miss, он обслуживается быстрее. Кроме того, распределение может быть довольно быстрым (в определенных сценариях), что является небольшим, но иногда важным преимуществом.
СОВЕТ: РАССМОТРИТЕ ИНКРЕМЕНТАЛИЗМ
Много раз в жизни вас поощряют быть революционером. “Мыслите масштабно!” - говорят они. “Измени мир!” - кричат они. И вы можете понять, почему это привлекательно; в некоторых случаях необходимы большие перемены, и поэтому настойчивое стремление к ним имеет большой смысл. И, если вы попробуете сделать это таким образом, по крайней мере, они, возможно, перестанут кричать на вас.
Однако во многих случаях более медленный, постепенный подход может оказаться правильным. Пример с huge page в Linux в этой главе является примером инженерного инкрементализма; вместо того, чтобы занимать позицию фундаменталиста и настаивать на том, что большие страницы - это путь в будущее, разработчики приняли взвешенный подход, сначала внедрив специализированную поддержку для ИТ, узнав больше о ее плюсах и минусах и, только когда для этого была реальная причина, добавив более общую поддержку для всех приложений.
Инкрементализм, хотя иногда и презираемый, часто приводит к медленному, вдумчивому и разумному прогрессу. При построении систем такой подход может быть как раз тем, что вам нужно. Также это может быть верно и в жизни.
Одним из интересных аспектов поддержки Linux для огромных страниц является то, как это делалось постепенно. Сначала разработчики Linux знали, что такая поддержка важна только для нескольких приложений, таких как большие базы данных с жесткими требованиями к производительности. Таким образом, было принято решение разрешить приложениям явно запрашивать выделение памяти с большими страницами (либо с помощью вызовов mmap(), либо shmget()). Таким образом, большинство приложений не пострадают (и будут продолжать использовать только страницы объемом 4 КБ); несколько требовательных приложений придется изменить, чтобы использовать эти интерфейсы, но для них это будет стоить усилий. В последнее время, поскольку необходимость улучшения поведения TLB чаще встречается среди многих приложений, разработчики Linux добавили прозрачную поддержку огромных страниц. Когда эта функция включена, операционная система автоматически ищет возможности для выделения огромных страниц (обычно 2 МБ, но в некоторых системах 1 ГБ) без необходимости модификации приложения.
Огромные страницы не обходятся без своих затрат. Самая большая потенциальная стоимость - это внутренняя фрагментация, то есть большая, но редко используемая страница. Эта форма мусора может заполнить память большими, но малоиспользуемыми страницами. Подкачка, если она включена, также плохо работает с огромными страницами, иногда значительно увеличивая объем операций ввода-вывода, выполняемых системой. Накладные расходы на выделение памяти также могут быть выше (в некоторых других случаях). В целом, ясно одно: размер страницы в 4 КБ, который так хорошо служил системам в течение стольких лет, не является универсальным решением, каким он был когда-то; растущие размеры памяти требуют, чтобы мы рассматривали большие страницы и другие решения как часть необходимой эволюции виртуальных систем. Медленное внедрение Linux этой аппаратной технологии свидетельствует о грядущих изменениях.
Кэш Страниц
Чтобы снизить затраты на доступ к постоянному хранилищу (основное внимание в третьей части этой книги), большинство систем используют агрессивные подсистемы кэширования для хранения популярных элементов данных в памяти. Linux в этом отношении ничем не отличается от традиционных операционных систем.
Кэш страниц Linux унифицирован, сохраняя страницы в памяти из трех основных источников: файлы с отображением в памяти, данные файлов и метаданные с устройств (обычно доступ осуществляется путем направления вызовов read() и write() в файловую систему), а также страницы кучи и стека, которые составляют каждый процесс (иногда называемый анонимной памятью, потому что под ним нет именованного файла, а есть пространство подкачки). Эти сущности хранятся в хэш-таблице кэша страниц, что позволяет быстро искать, когда требуются указанные данные. Кэш страниц отслеживает, являются ли записи чистыми (прочитанными, но не обновленными) или грязными (т.е. измененными). Грязные данные периодически записываются в резервное хранилище (т.е. в определенный файл для файловых данных или для подкачки пространства для анонимных областей) фоновыми потоками (называемыми pdflush), что гарантирует, что измененные данные в конечном итоге будут записаны обратно в постоянное хранилище. Это фоновое действие либо выполняется через определенный промежуток времени, либо если слишком много страниц считаются грязными (оба параметра настраиваются).
В некоторых случаях в системе не хватает памяти, и Linux приходится решать, какие страницы удалить из памяти, чтобы освободить место. Для этого Linux использует модифицированную форму замены 2Q [JS94], которую мы описываем здесь.
Основная идея проста: стандартная замена LRU эффективна, но может быть нарушена некоторыми общими шаблонами доступа. Например, если процесс повторно обращается к большому файлу (особенно к файлу размером почти с память или больше), LRU удалит все остальные файлы из памяти. Еще хуже: сохранение частей этого файла в памяти бесполезно, так как на них никогда не ссылаются повторно, прежде чем их удалят из памяти.
Linux-версия алгоритма замены 2Q решает эту проблему, сохраняя два списка и разделяя память между ними. При первом доступе страница помещается в одну очередь (в оригинальной статье она называется A1, но в расположена в inactive list в Linux); при повторной ссылке на нее страница перемещается в другую очередь (в оригинале она называется Aq, но находится в active list в Linux). Когда необходимо произвести замену, кандидат на замену берется из неактивного списка. Linux также периодически перемещает страницы из нижней части активного списка в неактивный список, сохраняя активный список примерно на две трети от общего размера кэша страниц [G04].
Linux в управлял бы этими списками в идеальном порядке LRU, но, как обсуждалось в предыдущих главах, это дорого. Таким образом, как и во многих операционных системах, используется аппроксимация LRU (аналогично замене на основе политики clock).
Этот подход 2Q, как правило, ведет себя довольно похоже на LRU, но, в частности, обрабатывает случай, когда происходит циклический доступ к большим файлам, ограничивая страницы этого циклического доступа списком неактивных. Поскольку на указанные страницы никогда не ссылаются повторно перед удалением из памяти, они не удаляют другие полезные страницы, найденные в активном списке.
ОФФТОП: ПОВСЕМЕСТНОЕ РАСПРОСТРАНЕНИЕ ОТОБРАЖЕНИЯ ПАМЯТИ
Сопоставление памяти появилось на несколько лет раньше Linux и используется во многих местах в Linux и других современных системах. Идея проста: вызывая mmap() для уже открытого файлового дескриптора, процесс возвращает указатель на начало области виртуальной памяти, где, по-видимому, находится содержимое файла. Затем, используя этот указатель, процесс может получить доступ к любой части файла с помощью простого разыменования указателя.
Доступ к частям файла, сопоставленного с памятью, которые еще не были перенесены в память, вызывает сбои страниц, после чего операционная система выводит соответствующие данные на страницу и делает их доступными, соответствующим образом обновляя таблицу страниц процесса (т.е. требует подкачки).
Каждый обычный процесс Linux использует файлы, сопоставленные с памятью, даже код в main() не вызывает mmap() напрямую из-за того, как Linux загружает код из исполняемого файла и кода общей библиотеки в память. Ниже приведен (сильно сокращенный) вывод инструмента командной строки pmap, который показывает, какие различные сопоставления составляют виртуальное адресное пространство запущенной программы (оболочка, в данном примере, tcsh). Выходные данные показывают четыре столбца: виртуальный адрес сопоставления, его размер, биты защиты региона и источник сопоставления:
Как вы можете видеть из этого вывода, код из двоичного файла tcsh, а также код из libc, libcrypt, libtinfo и код из самого динамического компоновщика (ld.so ) все отображаются в адресное пространство. Также присутствуют две анонимные области: куча (вторая запись, помеченная как anon) и стек (помеченный как стек). Файлы, сопоставленные с памятью, обеспечивают простой и эффективный способ создания ОС современного адресного пространства.
Безопасность И Переполнение Буфера
Вероятно, самое большое различие между современными виртуальными системами (Linux, Solaris или одним из вариантов BSD) и древними (VAX / VMS) заключается в акценте на безопасность в современную эпоху. Защита всегда была серьезной проблемой для операционных систем, но с машинами, более взаимосвязанными, чем когда-либо, неудивительно, что разработчики внедрили различные защитные контрмеры, чтобы помешать этим коварным хакерам получить контроль над системами.
Одна из основных угроз заключается в атаках* на переполнение буфера, которые могут быть использованы против обычных пользовательских программ и даже самого ядра. Идея этих атак состоит в том, чтобы найти ошибку в целевой системе, которая позволяет злоумышленнику вводить произвольные данные в адресное пространство цели. Такие уязвимости иногда возникают из-за того, что разработчик предполагает (ошибочно), что входные данные не будут слишком длинными, и, таким образом, (доверчиво) копирует входные данные в буфер; поскольку входные данные на самом деле слишком длинные, они переполняют буфер, тем самым перезаписывая память цели. Такой невинный код, как приведенный ниже, может быть источником проблемы:
Во многих случаях такое переполнение не является катастрофическим, например, неверный ввод, невинно предоставленный пользовательской программе или даже операционной системе, вероятно, приведет к ее сбою, но не хуже. Однако злонамеренные программисты могут тщательно обработать входные данные, которые переполняют буфер, чтобы внедрить свой собственный код в целевую систему, что, по сути, позволяет им перехватить его и выполнять свои собственные требования. В случае успеха в пользовательской программе, подключенной к сети, злоумышленники могут выполнять произвольные вычисления или даже сдавать в аренду велосипеды в скомпрометированной системе; в случае успеха в самой операционной системе атака может получить доступ к еще большему количеству ресурсов и является формой так называемого повышения привилегий (т.е. пользовательский код получает права доступа к ядру). Если вы ещё не догадались - это все Плохие Вещи.
*Смотри https://en.wikipedia.org/wiki/Buffer_overflow для получения некоторых подробностей и ссылок по этой теме, включая ссылку на знаменитую статью хакера по безопасности Элиаса Леви, также известного как “Алеф Один".
Первая и наиболее простая защита от переполнения буфера заключается в предотвращении выполнения любого кода, найденного в определенных областях адресного пространства (например, в стеке). Бит NX (No-eXecute), введенный AMD в их версию x86 (аналогичный бит XD теперь доступен на Intel), является одной из таких защит; он просто предотвращает выполнение с любой страницы, на которой этот бит установлен в соответствующей записи таблицы страниц. Этот подход предотвращает выполнение кода, введенного злоумышленником в стек цели, и, таким образом, устраняет проблему.
Однако умные нападающие ... умны, и даже когда злоумышленник не может явно добавить введенный код, вредоносный код может выполнять произвольные последовательности кода. Идея известна в ее самой общей форме как ориентированное на возврат программирование (return-oriented programming ROP) [S07], и на самом деле она довольно блестящая. Наблюдение, лежащее в основе ROP, заключается в том, что в адресном пространстве любой программы содержится множество битов кода (гаджетов, в терминологии ROP), особенно программ на языке Си, которые связаны с обширной библиотекой Си. Таким образом, злоумышленник может перезаписать стек таким образом, чтобы адрес возврата в выполняемой в данный момент функции указывал на желаемую вредоносную инструкцию (или серию инструкций), за которой следует инструкция возврата. Связывая вместе большое количество гаджетов (т.е. обеспечивая переход каждого возврата к следующему гаджету), злоумышленник может выполнить произвольный код. Потрясающе!
Чтобы защититься от ROP (включая ее более раннюю форму, return-to-libc attack [S+04]), Linux (и другие системы) добавляют другую защиту, известную как рандомизация компоновки адресного пространства (address space layout randomization ASLR). Вместо размещения кода, стека и кучи в фиксированных местах в виртуальном адресном пространстве ОС рандомизирует их размещение, что делает довольно сложной задачу создания сложной последовательности кода, необходимой для реализации этого класса атак. Таким образом, большинство атак на уязвимые пользовательские программы приведут к сбоям, но не смогут получить контроль над запущенной программой.
Интересно, что вы можете довольно легко наблюдать эту случайность на практике. Вот фрагмент кода, который демонстрирует это в современной системе Linux:
Этот код просто выводит (виртуальный) адрес переменной в стеке. В старых системах, отличных от ASLR, это значение будет одинаковым каждый раз. Но, как вы можете видеть ниже, значение меняется с каждым запуском:
ASLR является настолько полезной защитой для программ пользовательского уровня, что она также была включена в ядро в функции, которая невообразимо называется рандомизацией компоновки адресного пространства ядра (kernel address space layout randomization KASLR). Однако, как мы обсудим далее, оказывается, что у ядра могут быть еще более серьезные проблемы.
Другие Проблемы С Безопасностью: Meltdown And Spectre
Когда мы пишем эти слова (август 2018 г.), мир системной безопасности перевернулся с ног на голову в результате двух новых и связанных с ними атак. Первая называется Meltdown, а вторая Spectre. Они были обнаружены примерно в одно и то же время четырьмя различными группами исследователей / инженеров и привели к глубокому сомнению в фундаментальной защите, обеспечиваемой компьютерным оборудованием и вышеупомянутой операционной системой. Посетите meltdownattack.com и spectreattack.com для изучения документов, подробно описывающих каждую атаку. Спектр считается более проблематичным из двух.
Общая слабость, используемая в каждой из этих атак, заключается в том, что процессоры, используемые в современных системах, выполняют всевозможные сумасшедшие трюки для повышения производительности. Один из классов методов, лежащих в основе проблемы, называется спекулятивным выполнением (speculative execution), при котором центральный процессор угадывает, какие инструкции скоро будут выполнены в будущем, и начинает выполнять их заранее. Если предположения верны, программа работает быстрее; если нет, процессор отменяет их влияние на состояние архитектуры (например, регистры), повторяет попытку, на этот раз идя по правильному пути.
Проблема со спекуляцией заключается в том, что она имеет тенденцию оставлять следы своего выполнения в различных частях системы, таких как кэш процессора, предсказатели ветвей и т.д. И, следовательно, проблема: как показывают авторы атак, такое состояние может сделать уязвимым содержимое памяти, даже память, которая, как мы думали, была защищена MMU.
Таким образом, одним из путей повышения защиты ядра было удаление как можно большей части адресного пространства ядра из каждого пользовательского процесса и вместо этого создание отдельной таблицы страниц ядра для большинства данных ядра (называемой изоляцией таблицы страниц ядра или KPTI) [G+17]. Таким образом, вместо отображения кода ядра и структур данных в каждый процесс в нем сохраняется только самый минимальный минимум; при переключении в ядро теперь требуется переключение на таблицу страниц ядра. Это повышает безопасность и позволяет избежать некоторых векторов атак, но за счет производительности. Переключение таблиц страниц обходится дорого. Ах, издержки безопасности: удобство и производительность.
К сожалению, KPTI не решает все проблемы безопасности, изложенные выше, только некоторые из них. И простые решения, такие как отключение спекуляций, имели бы мало смысла, потому что системы работали бы в тысячи раз медленнее. Таким образом, это интересное время для жизни, если безопасность систем - это ваша область интересов.
Чтобы по-настоящему понять эти атаки, вам (скорее всего) придется сначала узнать гораздо больше. Начните с понимания современной компьютерной архитектуры, как описано в передовых книгах по этой теме, сосредоточив внимание на предположениях и всех механизмах, необходимых для ее реализации. Определенно читайте об атаках Meltdown и Spectre на сайтах, упомянутых выше; на самом деле они также включают полезный учебник по спекуляциям, так что, возможно, это неплохое место для начала. И изучите операционную систему на предмет дальнейших уязвимостей. Кто знает, какие проблемы еще остаются?
23.3 Выводы
Теперь вы видели подробный обзор двух систем виртуальной памяти. Надеюсь, что большинство деталей было легко проследить, так как вы уже должны были хорошо понимать основные механизмы и политику. Более подробная информация о VAX / VMS доступна в превосходной (и короткой) статье Леви и Липмана [LL 82]. Мы рекомендуем вам прочитать его, так как это отличный способ увидеть, на что похож исходный материал, лежащий в основе этих глав.
Вы также немного узнали о Linux. Будучи большой и сложной системой, она унаследовала много хороших идей из прошлого, многие из которых у нас не было возможности обсудить подробно. Например, Linux выполняет отложенное копирование страниц при записи с помощью функции fork(), тем самым снижая накладные расходы, избегая ненужного копирования. Linux также реализует стратегию demand zeroe для страниц (используя сопоставление памяти устройства / dev / zero) и имеет демон фоновой подкачки (swapd), который сбрасывает страницы на диск, чтобы уменьшить нагрузку на память. Действительно, виртуальная машина наполнена хорошими идеями, заимствованными из прошлого, а также включает в себя множество собственных инноваций.
Чтобы узнать больше, ознакомьтесь с этими разумными (но, увы, устаревшими) книгами [BC05,G04]. Мы рекомендуем вам прочитать их самостоятельно, так как мы можем предоставить лишь самую малую каплю из того океана сложности. Но вы должны с чего-то начать. Что такое любой океан, как не множество капель? [M04]
Ссылки
[B+13] “Efficient Virtual Memory for Big Memory Servers” by A. Basu, J. Gandhi, J. Chang, M. D. Hill, M. M. Swift. ISCA ’13, June 2013, Tel-Aviv, Israel. A recent work showing that TLBs matter, consuming 10% of cycles for large-memory workloads. The solution: one massive segment to hold large data sets. We go backward, so that we can go forward!
[BB+72] “TENEX, A Paged Time Sharing System for the PDP-10” by D. G. Bobrow, J. D. Burchfiel, D. L. Murphy, R. S. Tomlinson. CACM, Volume 15, March 1972. An early time-sharing OS where a number of good ideas came from. Copy-on-write was just one of those; also an inspiration for other aspects of modern systems, including process management, virtual memory, and file systems.
[BJ81] “Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits” by O. Babaoglu, W. N. Joy. SOSP ’81, Pacific Grove, California, December 1981. How to exploit existing protection machinery to emulate reference bits, from a group at Berkeley working on their own version of UNIX: the Berkeley Systems Distribution (BSD). The group was influential in the development of virtual memory, file systems, and networking.
[BC05] “Understanding the Linux Kernel” by D. P. Bovet, M. Cesati. O’Reilly Media, November 2005. One of the many books you can find on Linux, which are out of date, but still worthwhile.
[C03] “The Innovator’s Dilemma” by Clayton M. Christenson. Harper Paperbacks, January 2003. A fantastic book about the disk-drive industry and how new innovations disrupt existing ones. A good read for business majors and computer scientists alike. Provides insight on how large and successful companies completely fail.
[C93] “Inside Windows NT” by H. Custer, D. Solomon. Microsoft Press, 1993. The book about Windows NT that explains the system top to bottom, in more detail than you might like. But seriously, a pretty good book.
[G04] “Understanding the Linux Virtual Memory Manager” by M. Gorman. Prentice Hall, 2004. An in-depth look at Linux VM, but alas a little out of date.
[G+17] “KASLR is Dead: Long Live KASLR” by D. Gruss, M. Lipp, M. Schwarz, R. Fellner, C. Maurice, S. Mangard. Engineering Secure Software and Systems, 2017. Available: https://gruss.cc/files/kaiser.pdf Excellent info on KASLR, KPTI, and beyond.
[JS94] “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm” by T. Johnson, D. Shasha. VLDB ’94, Santiago, Chile. A simple but effective approach to building page replacement.
[LL82] “Virtual Memory Management in the VAX/VMS Operating System” by H. Levy, P. Lipman. IEEE Computer, Volume 15:3, March 1982. Read the original source of most of this material. Particularly important if you wish to go to graduate school, where all you do is read papers, work, read some more papers, work more, eventually write a paper, and then work some more.
[M04] “Cloud Atlas” by D. Mitchell. Random House, 2004. It’s hard to pick a favorite book. There are too many! Each is great in its own unique way. But it’d be hard for these authors not to pick “Cloud Atlas”, a fantastic, sprawling epic about the human condition, from where the the last quote of this chapter is lifted. If you are smart – and we think you are – you should stop reading obscure commentary in the references and instead read “Cloud Atlas”; you’ll thank us later.
[O16] “Virtual Memory and Linux” by A. Ott. Embedded Linux Conference, April 2016. https://events.static.linuxfound.org/sites/events/files/slides/elc 2016 mem.pdf . A useful set of slides which gives an overview of the Linux VM.
[RL81] “Segmented FIFO Page Replacement” by R. Turner, H. Levy. SIGMETRICS ’81, Las Vegas, Nevada, September 1981. A short paper that shows for some workloads, segmented FIFO can approach the performance of LRU.
[S07] “The Geometry of Innocent Flesh on the Bone: Return-into-libc without Function Calls (on the x86)” by H. Shacham. CCS ’07, October 2007. A generalization of return-to-libc. Dr. Beth Garner said in Basic Instinct, “She’s crazy! She’s brilliant!” We might say the same about ROP
[S+04] “On the Effectiveness of Address-space Randomization” by H. Shacham, M. Page, B. Pfaff, E. J. Goh, N. Modadugu, D. Boneh. CCS ’04, October 2004. A description of the return-tolibc attack and its limits. Start reading, but be wary: the rabbit hole of systems security is deep...
