ТАБЛИЦЫ ТЕНЕВЫХ СТРАНИЦ ДЛЯ УПРАВЛЕНИЯ ПРЕОБРАЗОВАНИЕМ АДРЕСОВ
TABLES OF SHADOW PAGES FOR CONTROL OF ADDRESS MAPPING

Область техники, к которой относится изобретение
Настоящее изобретение относится к области управления памятью в компьютере и более конкретно к управлению таблицами преобразования адресов в системе виртуальной адресации.
Предшествующий уровень техники
Современные компьютерные системы обычно обеспечивают некоторый вид механизма виртуальной адресации. Как известно в данной области техники, каждый индивидуально доступный модуль памяти, связанный с компьютерной системой, имеет физический адрес, который однозначно идентифицирует этот модуль памяти. Однако в компьютерной системе, которая поддерживает виртуальную адресацию, возможно назначить виртуальные адреса физическим местоположениям. Система виртуальной адресации использует схему преобразования, чтобы преобразовать виртуальный адрес в физический адрес.
Одной из особенностей системы виртуальной адресации является та, что можно сконфигурировать схемы преобразования адресов таким образом, что некоторые наборы физических адресов (например, страницы физической памяти) не имеют никакого виртуального адреса. В типичной схеме управления памятью на основе страниц схема (карта) преобразования адресов преобразует дескрипторы виртуальных страниц в номера блоков физических страниц. Таким образом, все местоположения в заданном блоке физических страниц могут быть отклоняемыми виртуальными адресами, гарантируя, что схема преобразования адресов не указывает на этот блок страниц. В более общем смысле многие схемы виртуальной адресации помечают виртуальные адреса типами доступа, которые могут быть выполнены посредством использования виртуального адреса (например, считывание, считывание/запись); выбранные (типы) доступа к странице (например, запись), могут быть предотвращены, гарантируя, что никакое преобразование виртуального адреса в страницу не позволяет отклонить доступ. Этот аспект схемы преобразования адресов может использоваться для того, чтобы осуществить форму защиты памяти. Таким образом, программный объект (например, операционная система, процесс прикладного уровня или любой другой тип программного объекта) могут быть лишены доступа к странице физического адресного пространства, гарантируя то, что любая схема (карта), доступная этому программному объекту, находится в таком состоянии, что никакое преобразование виртуального адреса в рассматриваемую страницу не разрешает доступ. Этот тип схемы защиты памяти особенно полезен в семействе процессоров IA32 (например, процессоры INTEL x86), потому что архитектура процессоров INTEL x86 такова, что при работе в защищенном режиме (нормальное состояние работы процессора) все запросы доступа к памяти подвергаются преобразованию виртуальных адресов. Схема защиты памяти, которая при работе предотвращает программы привилегированного режима от изменения таблиц преобразования способом, который может разрешить некоторый тип доступа к некоторым физическим адресам, называется "управление преобразованием адресов" или ATC (УПА).
В типичных архитектурах (подобно x86) преобразование из виртуальных в физические адреса задается содержимым обычных страниц памяти (так называемых страниц "карты страниц"). Это удобно для записывающих операционных систем, потому что карты виртуальной адресации могут быть созданы и модифицированы обычными операциями с памятью. Если операционная система должна быть ограничена использованием УПА, то УПА должен предотвратить операционную систему от наличия отображения, которое позволяет ей осуществлять запись непосредственно в страницы "карты страниц", так как операционная система может использовать записи в такие страницы, чтобы создать отображения, дающие ей произвольный доступ к произвольным физическим страницам памяти. Таким образом, в дополнение к предотвращению преобразования отображений считывания-записи в страницы, в которые программному объекту не разрешено записывать, УПА должен предотвратить "небезопасные" преобразования, которые включают в себя преобразования считывания - записи в страницы карты страниц.
В то время как изоляция (локализация) памяти посредством УПА является эффективной, одной из возникающих при этом проблем является та, как обращаться с запросами на запись, которые создают небезопасные преобразования, но сами не нарушают политику управления доступом. Один из способов обращения с таким запросом на запись представляет для простого запроса - просто отказ; однако, это может требовать существенного пересмотра операционной системы. Таким образом, некоторые современные алгоритмы УПА модифицируют или записанное значение (например, чтобы изменить преобразование считывание-запись в страницу карты страниц в преобразование только чтения) или модифицируют другие страницы карты страниц, чтобы сделать карту безопасной. Проблема, связанная с этим способом, состоит в том, что программный объект выполняет запрос на запись, полагая, что указанное значение записывается в целевое местоположение, когда, фактически, конечное местоположение содержит отличное значение. Это несоответствие может отражаться различными способами, например программный объект может генерировать контрольную сумму, основанную на значениях, которые программное обеспечение считает сохраненными, и эти контрольные суммы не будут подтверждать правильность изменяемого значения, сгенерированного системой УПА.
Выгода использования одного варианта осуществления настоящего изобретения должно обеспечить среду, в которой (операции) записи, которые создают ненадежные преобразования (но придерживаются политики защиты), проявляются как успешно не модифицированные (с точки зрения программного объекта), но при этом результирующие карты не могут эксплуатироваться так, чтобы обойти политику, таким образом преодолевая недостатки предшествующего уровня техники.
Сущность изобретения
Настоящее изобретение обеспечивает использование теневых страниц для поддержки управления преобразованием адресов. В типичной системе виртуальной адресации заданная страница может быть страницей преобразования (содержащей данные, которые являются частью карты) или страницей данных (адресат некоторого виртуального адреса) или обоими. К страницам преобразования и страницам данных обращаются в различных контекстах: записи в страницах данных являются адресатами (местом назначения) нижележащих запросов считывания или записи; записи в страницах преобразования, с другой стороны, являются разыменованными (со снятыми ссылками) для того, чтобы определить местоположение других страниц. Изобретение поддерживает множественные копии страниц, соответствующих различным контекстам, в которых страница может использоваться (например, как каталог, таблица, или страница данных, как объяснено ниже). Изобретение использует подходящую копию страницы в зависимости от контекста, в соответствии с которым обращаются к странице.
Некоторые системы виртуальной адресации (такие как наиболее общий режим виртуальной адресации, используемый в семействе процессоров INTEL x86) имеют два типа страниц преобразования: каталоги и таблицы. Каталоги содержат ссылки на таблицы и большие страницы данных, а таблицы содержат ссылки на маленькие страницы данных ("Большие" и "маленькие" страницы более подробно описаны ниже). Таким образом, с точки зрения процесса преобразования адресов имеется до трех различных контекстов, в которых к данной странице можно обращаться как к каталогу, как к таблице или как к целевым данным (данным-адресатам). В предпочтительном варианте воплощения поддерживаются до трех версий заданной страницы: версия каталога, версия таблицы и версия данных. Когда к данной странице обращаются, эти относящиеся к странице каталог, таблица или версия данных используются в зависимости от контекста, в котором обращаются к странице.
При УПА содержимое страницы может вызывать нарушение политики доступа к памяти, только если страница используется как каталог или таблица. Например, страница может содержать ссылку на запрещенную страницу. Однако опасность, заключающаяся в том, что эта страница будет использоваться для обращения к запрещенной странице, присутствует, только если транслятор (преобразователь) адресов фактически использует страницу как часть карты (преобразования); если к странице вместо этого обращаются как к странице данных, то это не "открывает" виртуальный адрес для запрещенной страницы. Таким образом, копия данных этой страницы может содержать фактические данные, которые, как полагает программный объект, записаны в страницу, в то время как копии каталога и таблицы этой страницы могут содержать изменeнные версии, которые представляют безопасную карту.
Другие признаки изобретения описаны ниже.
Краткое описание чертежей
Описанная выше сущность изобретения, так же как и подробное описание предпочтительных вариантов осуществления, станет более понятной из нижеследующего описания вместе с прилагаемыми чертежами. С целью иллюстрации изобретения на чертежах иллюстрируются примерные конструкции изобретения; однако изобретение не ограничено конкретными раскрытыми способами и средствами.
Фиг.1 - блок-схема примерной вычислительной среды, в которой могут быть осуществлены аспекты изобретения;
фиг.2 - блок-схема примерной системы виртуальной адресации;
фиг.3 - блок-схема примерной записи (элемента) в карте преобразования адресов;
фиг.4 - диаграмма состояния примерного условия инварианта для управления доступом к памяти посредством управления преобразованием адресов;
фиг.5 - диаграмма страниц, которая существует во множестве версий, где различная версия страницы используется в зависимости от контекста, в котором используется страница;
фиг.6 - блок-схема последовательности операций примерного процесса для получения версии каталога для страницы; и
фиг.7 - блок-схема последовательности операций примерного процесса для получения версии таблицы для страницы.
Подробное описание предпочтительного варианта осуществления настоящего изобретения
Краткий обзор
Управление преобразованием адресов может использоваться для осуществления политики управления доступом к памяти посредством эффективного отрицания преобразований виртуальных адресов, которые могут быть использованы, чтобы нарушить политику. В общем случае управление преобразованием адресов выполняется посредством наложения существенных ограничений на попытки редактировать карту преобразования адресов, так что карта всегда остается безопасной (в том смысле, что карта "не открывает" данному программному объекту ссылки (или перезаписываемые ссылки) на страницы, которые являются запрещенными (или не перезаписываемыми) для этого объекта, и не позволяет недоверенному объекту осуществлять запись в карту). Как правило, эти существенные ограничения налагаются посредством оценки запросов на редактирование карты для того, чтобы определить, переведет ли выполнение запроса карту в нежелательное состояние; если нежелательное состояние может иметь место, то запрос изменяется так, чтобы выполнение желательного запроса поддерживало желательное состояние. (Например, запрос на редактирование карты, который может привести к ссылке для чтения/записи на страницу, которая является считываемой, но не перезаписываемой, в соответствии с политикой, может быть изменен так, чтобы пометить ссылку как только для чтения). Проблема, связанная с этим способом, заключается в том, что иногда корректное поведение программного обеспечения зависит от памяти, содержащей значения, которые программное обеспечение полагает, что оно записало в память - например, в случае верификации контрольной суммы - и модификация запроса заставит память содержать отличное значение, чем то, которое программное обеспечение предполагает, что уже записано. Настоящее изобретение решает эту проблему, поддерживая различные версии страниц, используемых в качестве страниц карты страниц: версия данных, которая "открыта" программному объекту, и одна или более версий карты, которые могут использоваться как часть процесса преобразования адресов без нарушения безопасности (надежности) карты. Преобразования к версии данных такой страницы сделаны только для чтения так, чтобы записи в страницу могут быть прерваны посредством УПА, которое может редактировать страницы так, чтобы сохранить отличную версию синхронизированной.
Пример компьютерной структуры
На фиг.1 показан пример вычислительной среды, в которой могут быть осуществлены аспекты изобретения. Вычислительная системная среда 100 является только примером подходящей вычислительной среды и не предназначена для того, чтобы задавать какое-либо ограничение относительно возможностей использования или функциональных возможностей изобретения. Ни одна вычислительная среда 100 не должна интерпретироваться как имеющая какую-либо зависимость или требования, относящиеся к любому компоненту или комбинации компонентов, показанных в примерной среде 100.
Изобретение может оперировать с множеством других универсальных или специализированных вычислительных системных сред или конфигураций. Примеры хорошо известных вычислительных систем, сред и/или конфигураций, которые могут быть подходящими для использования с изобретением, включают в себя, но не ограничиваются ими, персональные компьютеры, серверные компьютеры, карманные или портативные компьютеры, многопроцессорные системы, основанные на микропроцессорах системы, телевизионные приставки, программируемую бытовую электронику, сетевые персональные компьютеры, миникомпьютеры, универсальные компьютеры, внедренные системы, распределенные вычислительные среды, которые включают в себя любую из вышеупомянутых систем или устройств, и т.п.
Изобретение может быть описано в общем контексте выполнимых компьютером команд, таких как программные модули, выполняемые компьютером. В общем случае программные модули включают в себя подпрограммы, программы, объекты, компоненты, структуры данных и т.д., которые исполняют конкретные задачи или реализуют специфические абстрактные типы данных. Изобретение может также быть применено в распределенных вычислительных средах, в которых задачи выполняются удаленными устройствами обработки, которые связаны через систему коммуникаций или другую среду передачи данных. В распределенной вычислительной среде программные модули и другие данные могут быть расположены в локальных и удаленных компьютерных носителях данных, включая запоминающие устройства памяти.
Согласно фиг.1 для осуществления изобретения примерная система включает в себя универсальное вычислительное устройство в форме компьютера 110. Компоненты компьютера 110 могут включать в себя, но не ограничиваются ими, процессор 120, системную память 130 и системную шину 121, которая соединяет различные системные компоненты, включая системную память, с процессором 120. Процессор 120 может представлять собой множество логических обрабатывающих блоков, которые поддерживаются на многопоточном процессоре. Системная шина 121 может быть любой из нескольких типов шинных структур, включая в себя шину памяти или контроллер памяти, шину периферийных устройств и локальную шину, использующую любую из множества шинных архитектур. В качестве примера, и не ограничиваясь ими, такая архитектура включает в себя архитектуру промышленного стандарта (ISA) шину, шину микроканальной архитектуры (МСА), усовершенствованную шину ISA (EISA) (Расширенная Стандартная Архитектура для Промышленного Применения), локальную шину VESA (Ассоциация по Стандартам в Области Видеоэлектроники), и Шину Соединения Периферийных Устройств (PCI) (также известную как шина Mezzaninne). Системная шина 121 может также быть реализована как двухточечное подключение, структура коммутации или подобная среди обменивающихся устройств.
Компьютер 110 обычно включает в себя множество считываемых компьютером носителей. Считываемые компьютером носители могут быть любой доступной средой, к которой можно обращаться компьютером 110, и включают в себя и энергозависимые и энергонезависимые носители, сменные и не сменные носители. В качестве примера и без ограничения, считываемый компьютером носитель может включать в себя компьютерный носитель данных и среду связи. Компьютерные носители данных включают в себя и энергозависимые и энергонезависимые, сменные и несменные носители, реализованные любым способом или технологией для хранения информации, такой как считываемые компьютером команды, структуры данных, программные модули или другие данные. Компьютерные носители данных включают в себя, но не ограничиваются ими, оперативную память (ОЗУ, RAM), ROM (постоянное запоминающее устройство, ПЗУ), электрически стираемое перепрограммируемое постоянное запоминающее устройство - ЭСППЗУ, флэш-память или память другой технологии, CD-ROM (постоянное запоминающее устройство на компакт-диске), цифровые универсальные диски (DVD) или другую оптическую память на диске, магнитные кассеты, магнитную ленту, магнитную память на диске или другие магнитные запоминающие устройства, или любую другую среду, которая может использоваться для хранения требуемой информации и к которой может обращаться компьютер 110. Среда связи обычно реализует считываемые компьютером команды, структуры данных, программные модули или другие данные в модулируемом сигнале данных типа сигнала несущей или другом транспортном механизме и включают в себя любую среду доставки информации. Термин "модулированный сигнал данных" означает сигнал, который имеет одну или более своих характеристик установленных или измененных таким образом, чтобы кодировать информацию в сигнале. В качестве примера, и без ограничения среда связи включает в себя проводную среду типа проводной сети или непосредственного проводного соединения и беспроводную среду типа акустической, РЧ, инфракрасной и другой беспроводной среды. Комбинации любых из вышеупомянутых также должны быть включены в рамки считываемых компьютером носителей.
Системная память 130 включает в себя компьютерные носители данных в форме энергозависимой и/или энергонезависимой памяти типа постоянного запоминающего устройства (ROM) 131 и оперативной памяти (RАM) 132. Базовая система ввода/вывода 133 (BIOS), содержащая основные подпрограммы, которые помогают передавать информацию между элементами в компьютере 110, например в течение запуска, обычно сохраняется в ПЗУ 131. ОЗУ 132 обычно содержит данные и/или программные модули, которые являются немедленно доступными и/или обрабатываемыми в текущий момент времени процессором 120. Посредством примера, и без ограничения, фиг.1 иллюстрирует операционную систему 134, прикладные программы 135, другие программные модули 136 и данные 137 программы.
Компьютер 110 может также включать в себя другие сменные/несменные, энергозависимые/энергонезависимые компьютерные носители данных. Только в качестве примера фиг.1 иллюстрирует привод 140 жесткого диска, который считывает или записывает на несменный энергонезависимый магнитный носитель, привод 151 магнитных дисков, который считывает или записывает на сменный энергонезависимый магнитный диск 152, и привод 155 оптических дисков, который считывает или записывает на сменный энергонезависимый оптический диск 156 типа CD-ROM или другой оптический носитель. Другие сменные/несменные, энергозависимые/энергонезависимые компьютерные носители данных, которые могут использоваться в примерной среде, включают в себя, но без ограничения кассеты с магнитной лентой, платы флэш-памяти, цифровые универсальные диски, цифровую видеоленту, твердотельное ОЗУ, твердотельное ПЗУ и т.п. Привод 141 жесткого диска обычно соединяется с системной шиной 121 через интерфейс несменной памяти, такой как интерфейс 140, и привод 151 магнитных дисков и привод 155 оптических дисков обычно соединяется с системной шиной 121 интерфейсом сменной памяти, таким как интерфейс 150.
Приводы и связанные с ними компьютерные носители данных, описанные выше и иллюстрированные на фиг.1, обеспечивают хранение считываемых компьютерном команд, структур данных, программных модулей и других данных для компьютера 110. На фиг.1, например, привод 141 жесткого диска проиллюстрирован как хранящий операционную систему 144, прикладные программы 145, другие программные модули 146 и программные данные 147. Следует заметить, что эти компоненты могут быть или одинаковыми или отличными от операционной системы 134, прикладных программ 135, других программных модулей 136 и данных 137 программы. Операционная система 144, прикладные программы 145, другие программные модули 146 и данные программы 147 имеют различные номера, чтобы иллюстрировать, что как минимум, они являются различными копиями. Пользователь может вводить команды и информацию в компьютер 20 через устройства ввода данных, например клавиатуру 162 и устройство 161 указания, обычно упоминаемое как мышь, трекбол или сенсорная панель. Другие устройства ввода данных (не показаны) могут включать в себя микрофон, джойстик, игровую клавиатуру, спутниковую антенну, сканер или подобные устройства. Эти и другие устройства ввода данных часто соединяются с процессором 120 через интерфейс 160 пользовательского ввода, который соединен с системной шиной, но могут быть соединены другим интерфейсом и шинной структурой, таким как параллельный порт, игровой порт или универсальной последовательной шиной (USB). Монитор 191 или другой тип устройства отображения также связан с системной шиной 121 через интерфейс, такой как видеоинтерфейс 190. В дополнение к монитору, компьютеры могут также включать в себя другие периферийные устройства вывода, типа громкоговорителей 197 и принтера 196, которые могут быть связаны через интерфейс 195 периферийных устройств вывода.
Компьютер 110 может работать в связанной в сеть среде, используя логические подключения с одним или более удаленными компьютерами, таким как удаленный компьютер 180. Удаленный компьютер 180 может быть персональным компьютером, сервером, маршрутизатором, сетевым персональным компьютером, равноправным устройством или другим общим сетевым узлом, и обычно включает в себя многие или все элементы, описанные выше применительно к компьютеру 110, хотя только запоминающее устройство 181 было проиллюстрировано на фиг.1. Логические соединения, изображенные на фиг.1, включают в себя локальную сеть (ЛС, LAN) 171 и глобальную сеть (ГС, WAN) 173, но могут также включать в себя другие сети. Такие среды организации сети являются общепринятыми в офисах, компьютерных сетях в масштабах предприятия, Интранет и Интернет.
При использовании в среде ЛС компьютер 110 связан с ЛС 171 через сетевой интерфейс или адаптер 170. При использовании в среде ГС компьютер 110 обычно включает в себя модем 172 или другие средства для установления связи по ГС 173, например Интернет. Модем 172, который может быть внутренним или внешним, может быть связан с системной шиной 121 через интерфейс 160 пользовательского ввода или другим соответствующим механизмом. В связанной в сеть среде программные модули, изображенные применительно к компьютеру 110 или его частям, могут быть сохранены в удаленном запоминающем устройстве памяти. Посредством примера, и без ограничения, фиг.1 иллюстрирует удаленные прикладные программы 185 как постоянно находящиеся в устройстве 181 памяти. Очевидно, что показанные сетевые соединения являются примерными и могут использоваться другие средства установления линии связи между компьютерами.
Примерная схема виртуальной адресации
Фиг.2 показывает пример системы виртуальной адресации. Пример, изображенный на фиг.2, является схемой виртуальной адресации страничного типа, хотя понятно, что виртуальная адресация может быть основана на других моделях, такой как сегментация. Схема, показанная на фиг.2, является двухуровневой схемой адресации, такой как одна из схем виртуальной адресации, доступных на процессоре INTELx86. Схема является "двухуровневой" в том смысле, что нужно использовать два уровня косвенности, чтобы преобразовать идентификатор виртуальной страницы в физическую страницу, как описано ниже.
В этой страничной схеме каталог 202 страниц содержит набор записей. Примерная структура записи более подробно описана ниже со ссылкой на фиг.3, но в сущности каждая запись идентифицирует физическое местоположение (то есть, номер блока страниц или "PFN" (номер блока страниц)) конкретной таблицы страниц, таких как таблицы 204(1), 204(2) или 204(3) страниц. Каждая таблица страниц, в свою очередь, содержит набор записей, где каждая запись идентифицирует физическое местоположение (снова, номер блока страниц) конкретных страниц данных, таких как страницы 206(1), 206(2), 206(3) или 206(4). Страницы данных являются непрерывными частями определенной длины в оперативной памяти 132. Страницы данных могут хранить любой тип данных и следует отметить, что в дополнение к сохранению обычных данных страницы данных также используются для хранения содержимого каталога 202 страниц и страниц 204(1) - 204(3). Таким образом, заданная страница может быть каталогом, таблицей, страницей данных или может играть множество ролей в качестве любой комбинации этих трех структур.
Схема виртуальной адресации, изображенная на фиг.2, является схемой виртуальной адресации с двумя уровнями, так как необходимо пройти и каталог страниц (уровень 1) и таблицу страниц (уровень 2), чтобы определить местоположение конкретной страницы. Как очевидно специалистам в данной области техники, возможно создать систему виртуальной адресации с произвольным числом уровней и принципы настоящего изобретения могут применяться ко всем таким схемам виртуальной адресации. Как известно специалистам в данной области техники, процессор INTEL x86 поддерживает виртуальные адреса, имеющие один, два или три уровня, и обычно использует "гибридную" схему, в которой "маленькие" страницы (то есть, страницы, которые имеют объем в четыре килобайта) используют виртуальные адреса с двумя уровнями, в то время как "большие" страницы (то есть, страницы, которые имеют объем в четыре мегабайта) используют одноуровневые виртуальные адреса.
В страничной схеме на фиг.2 любой байт на странице может быть идентифицирован виртуальным адресом 210, содержащим смещение 211 каталога страниц, смещение 212 таблицы страниц и смещение 213 страницы. (Структура виртуального адреса применяется к данным, сохраненным в маленьких страницах; большие страницы описаны ниже). Таким образом, чтобы определить местоположение физического адреса, модуль управления памятью (МУП, MMU) 220, который выполняет преобразование адресов, использует смещение 211 каталога страниц, чтобы определить местоположение конкретной записи в каталоге 202 страниц. Например, смещение 211 может быть равно нулю, указывая, что нужно обращаться к нулевой записи в каталоге 202 страниц. Эта запись содержит PFN, в котором сохранена таблица страниц, так что MMU 220 использует этот PFN, чтобы определить местоположение одной из таблиц страниц (например, таблицы 204(1) страниц). MMU 220 затем использует смещение 212 таблицы страниц в качестве индекса (указателя) входа в идентифицированную таблицу страниц, и извлекает запись, найденную по этому смещению. Запись содержит PFN страницы данных (например, страница 206(1)), так что MMU 220 добавляет смещение 213 страницы к базовому адресу идентифицированной страницы, чтобы определить местоположение конкретного байта физической памяти. MMU 220 может также быть приспособлен для выполнения различных других функций в дополнение к простому преобразованию адресов: например, MMU 220 может загружать страницу с диска, если запись страницы в этой таблице отмечена как "отсутствует"; MMU 220 может отвергнуть доступ по записи, если страница отмечена "только для чтения", и т.д.
Если виртуальный адрес относится к большой странице, то структура виртуального адреса и процесс преобразования этого адреса немного отличается от того, что описано выше. Виртуальный адрес содержит только одно смещение, которое является индексом для входа в каталог. Запись в каталоге, расположенная по этому смещению, вместо того, чтобы содержать PFN таблицы страниц, содержит PFN большой страницы данных. Запись в каталоге также имеет бит, который установлен для указания, что запись относится к большой странице вместо таблицы страниц. Когда бит большой страницы установлен, виртуальный адрес не содержит индекс входа в таблицу страниц, так что никакая таблица страниц не используется в процессе преобразования; вместо этого, остаток виртуального адреса (то есть часть, отличная от индекса входа в каталог) обрабатывается в качестве индекса входа в большую страницу. Уровень таблицы страниц обойден, так что имеет место только один уровень преобразования.
В схеме виртуального адреса согласно фиг.2 местоположение (то есть PFN) самого каталога страниц сохранено в ячейке 201 памяти. MMU 220 использует содержимое этой ячейки памяти, чтобы определить местоположение каталога 202 страниц, когда он начинает преобразовывать виртуальный адрес 210. Таким образом, могут быть в наличии множество карт страницы, и конкретная карта может быть выбрана для текущего использования посредством установки содержимого ячейки 201 памяти так, чтобы она содержала PFN каталога страниц данной карты. В примере с процессором INTEL x86 ячейка 201 памяти соответствует регистру с именем CR3.
Как отмечено выше, каждая запись в таблице страниц или каталоге страниц содержит PFN конкретной физической страницы и может также содержать некоторые другие данные. Фиг.3 показывает пример структуры для записи 300 в каталоге страниц или таблице страниц.
Запись 300 включает в себя PFN 302 конкретной физической страницы. Например, если запись 300 является частью каталога страниц, то PFN 302 является PFN таблицы страниц, к которой нужно обращаться на следующем уровне процесса преобразования адресов (или, в случае ссылки на большую страницу, запись просто содержит PFN большой страницы данных, к которой относится запись). Дополнительно, запись 300 содержит бит 304, указывающий, относится ли запись к большой или маленькой странице. (Этот бит будет иметь значение только тогда, когда запись 300 является частью каталога страниц. Ради простоты формат записи может быть одинаковым вне зависимости от того, является ли запись частью каталога или таблицы, хотя в случае таблицы значение бита 304 будет неопределенным).
Бит 306 "только для считывания" указывает, должна ли страница данных, которая является последним адресатом записи, быть обработана как предусматривающая считывание/запись (сброшенный бит) или только считывание (бит установлен). Если целевая страница данных (страница-адресат) предназначена только для считывания, то запросы на запись к этой странице будут выдавать ошибку (может использоваться MMU 220, чтобы установить состояние "только для считывания" страницы). Бит "только для считывания" может существовать в записях и каталога, и таблицы; если каталог и табличные ссылки, которые в конечном счете ведут к странице данных, имеют конфликтующие параметры настройки своих соответствующих битов "только для считывания", может использоваться правило разрешения конфликтов, чтобы определить, предназначена ли целевая страница данных для считывания/записи или только для считывания. Например, правило конфликтов может устанавливать, что для того, чтобы страница, которая должна быть обработана как поддерживающая считывание/запись, ссылки и каталога, и таблиц, которые указывают на эту страницу, должны быть отмечены как поддерживающие считывание/запись (то есть бит 306 "только для считывания" в обоих записях должен быть сброшен). Одна и та же страница может быть доступна различными способами через карту и то, должна ли быть страница обработана как поддерживающая считывание/запись или только считывание, может зависеть от используемого способа, чтобы достичь этой страницы.
Бит 308 "наличия" указывает, присутствует ли целевая страница данных в настоящее время в физической памяти или должна быть скопирована в память с диска. Например, если бит 308 "наличия" сброшен (указывая, что целевая страница отсутствует), запрос доступа по этой странице может генерировать страничный сбой, который затем обрабатывается программой обработки прерывания, которая копирует содержимое страницы с диска в физическую память и корректирует карту преобразования адресов, чтобы отразить физическое местоположение страницы. Когда бит наличия установлен по-разному в записях каталога страниц и таблицы страниц для данного отображения, то конфликт между этими битами может быть разрешен правилом разрешения конфликтов, подобно описанному выше для бита считывания/записи, например преобразование обрабатывается как "наличие", если и только если записи и каталога и таблицы были отмечены как "наличие" (присутствующие).
Управление доступом к памяти, используя управление редактированием записи в таблице преобразования адресов (УПА)
Одним из признаков схемы виртуальной адресации, описанной со ссылками на фиг.2-3, является то, что возможно существование части физической памяти, для которой никакого соответствующего виртуального адреса не существует. Следствием этого факта является то, что для любой части памяти возможно ограничить доступ к этой части памяти, гарантируя, чтобы карта преобразования адресов не указывала на эту часть памяти. В действительности ячейка памяти отображается вне границ (памяти), потому что эта ячейка памяти не имеет никакого виртуального адреса. (Во многих системах, например процессоре INTEL x86, почти все запросы доступа к памяти осуществляются посредством виртуального адреса; для тех ограниченных обстоятельств, в которых запросы доступа осуществляются посредством физического адреса, может использоваться параллельный механизм управления доступом.)
Способ, которым используется УПА для того, чтобы достичь управления доступом к памяти, описывается следующими терминами: NA ("нет доступа") - набор страниц, к которым доступ отклонен в соответствии с некоторой политикой. МР ("преобразованные страницы") - набор страниц, которые являются доступными через карту преобразования адресов - то есть набор страниц, для которых виртуальный адрес существует. Доступ к страницам, которые являются членами NA, может быть предотвращен, пока условие NA ∩ МР = ψ продолжает оставаться истинным. Это условие изображено на фиг.4 как диаграмма Венна: то есть страницы 406 являются набором физических страниц, доступных на машине; МР 402 является набором страниц, для которых виртуальные адреса существуют; NA 404 является набором страниц, к которым доступ запрещен в соответствии с политикой. Пока условие на фиг.4 остается истинным, невозможно использовать виртуальные адреса для доступа к страницам, к которым запрещен доступ, потому что карта не указывает на эти страницы (то есть страницы не имеют никакого виртуального адреса). Таким образом, условие, изображенное на фиг.4, может использоваться для достижения управления доступом к памяти посредством УПА. Это условие называется " инвариант, " так как цель УПА состоит в том, чтобы ограничить изменения в карте преобразования адресов, чтобы предотвратить изменения условие из состояния "истина" в состояние "ложь".
Фиг.4 изображает простое инвариантное условие, которое может использоваться для управления доступом к памяти, и показано только с целью иллюстрации. Более сложные условия возможны в зависимости от среды, в которой управление доступом должно иметь место. Например, возможно установить набор определенных правил относительно того, что записи могут содержаться в каталоге (или в таблице), и совершенствовать управление доступом, используя биты "только для считывания" и/или "наличия", чтобы помочь предписать состояние управления доступом. Например, ниже описан пример набора правил, который может использоваться, чтобы достичь управления доступом к памяти через УПА в процессоре INTEL x86:
D1 является набором страниц, которые могут использоваться в качестве каталогов страниц. D2 является набором страниц, которые могут использоваться в качестве таблицы страниц. D = D1 И D2. Каждая запись в каталоге страниц или таблице страниц, которая отмечена как "текущая“ (то есть чей бит "наличие" установлен), называется "ссылкой". Страница в D2 является "активной по записи", если имеется маленькая ссылка считывания/ записи от некоторой страницы в D1 к рассматриваемой странице D2. ("Маленькая" ссылка является ссылкой от каталога к таблице, то есть ссылкой в каталоге, которая будет в конечном счете приводить к маленькой странице. "Большая" ссылка является ссылкой в каталоге, которая указывает на большую страницу). Предполагается, что существует политика, которая задает страницы, к которым некоторому объекту разрешен доступ для считывания и/или записи.
Поддерживаются следующие инварианты:
- CR3 находится в D1;
- все страницы D1 и D2 являются считываемыми при релевантной политике;
- каждая маленькая ссылка от страницы D1 указывает на страницу D2;
- ссылки от страниц D2 указывают на страницу, которая является считываемой при релевантной политике;
- каждая ссылка считывания-записи от активной по записи страницы D2 указывает на страницу, которая является перезаписываемой при релевантной политике, и это имеет место не в D;
- каждая маленькая страница, содержащаяся в адресате большой страницы большую ссылку из страницы D1, является считываемой при релевантной политике; если ссылка обеспечивает считывание-запись, то маленькая страница также является перезаписываемой при этой политике и не в D.
УПА используется для того, чтобы гарантировать, что изменения в карте преобразования адресов, которые могут нарушить вышеупомянутые инварианты, предотвращаются. Поддержание этих инвариантов гарантирует, что рассматриваемый объект не может нарушить политику.
Независимо от того, какой инвариант налагается, истинность инварианта может поддерживаться посредством оценки каждого запроса на доступ, чтобы определить, приведет ли запрос, если фактически будет выполнен, к состоянию, при котором инвариант продолжает поддерживаться. Если результирующее состояние удовлетворяет инварианту, то запрос выполняют. Если, однако, инвариант будет не в состоянии поддерживаться, то имеются по меньшей мере две возможности:
- (1) отклоняют запрос; или
- (2) модифицируют запрос в форму, которая будет продолжать удовлетворять инвариант. Возможность (1) имеет тот недостаток, что на практике большое количество запросов на доступ должно быть отклонено, что подрывает функционирование компьютерной системы. При возможности (2), однако, программный объект запишет значение в ячейку памяти, и ячейка памяти может прекратить сохранять модифицированное значение, которое отличается от того значения, которое, как полагает программный объект, записано; как отмечено выше, корректное функционирование программного обеспечения (например, проверка контрольной суммы) может зависеть от памяти, хранящей фактические значения, которое, как полагает программное обеспечение, записано в памяти, и таким образом возможность (2) может также подрывать функционирование программного обеспечения. Изобретение направлено на решение этой проблемы, сохраняя множество версий страницы. Одна версия содержит точные данные, которые, как полагает программа, записаны в странице. Другие копии страницы содержат версии данных, которые при использовании в процессе преобразования адресов вынудят поддерживать релевантное инвариантное состояние.
Теневые страницы
Согласно одному признаку изобретения может существовать множество представлений страницы. Множественные представления одной и той же страницы гарантируют, что имеется версия страницы, которая содержит данные, которые программа фактически записывает в страницу, и другие ("теневые") версии этой страницы, которые являются безопасными для использования в процессе преобразования адресов в качестве каталогов страниц и таблиц страниц. "Безопасные для использования" в этом контексте означает, что использование теневой страницы в качестве каталога (или может быть таблицы, в качестве примера) не будет нарушать инвариант, применяемый системой УПА.
Предпочтительно, имея страницу x, имеются три версии этой страницы, которые должны быть упомянуты как d(x), t(x), и m(x). d(x) является версией "каталога" этой страницы, то есть версией страницы, которая является подходящей для использования в качестве каталога страниц в процессе преобразования адресов, описанном выше. t(x) является версией страницы, которая является безопасной для использования в качестве таблицы страниц. m(x) является версией "памяти" страницы, то есть, версией, которая содержит фактические данные, которые были записаны в странице одной или более программами. В этом описании термин "d(x)" может относиться или к содержимому версии каталога для страницы x, или, иначе, к PFN, в котором сохранена версия каталога для страницы x. Аналогично для t(x) и m(x). Относятся ли термины d(x), t(x) и m(x) к содержимому страницы или к его PFN, будет ясно из контекста или иначе это будет указано специально.
Фиг.5 показывает, как d(x), t(x) и m(x) используются в процессе преобразования адресов. Фиг.5 относится к трем страницам, помеченным x, y, и z (ссылочные номера 502, 504 и 506 соответственно). Страница x является каталогом страниц, страница y является таблицей страниц, и страница z является страницей данных. Следует отметить, что страницы x, y, и z могут выполнять множество ролей. Таким образом, x может функционировать или как каталог страниц, или страница данных, в зависимости от обстоятельств. Страница y может функционировать как таблица страниц в одних случаях и каталог страниц в других случаях. Однако для цели, с которой приведена фиг.5, предполагается, что конкретный виртуальный адрес преобразуется и с целью преобразования этого адреса страницы x, y, и z играют роли каталога, таблицы и страницы данных соответственно.
Страница x существует в версиях d(x), t(x) и m(x). Чтобы преобразовать рассматриваемый адрес, обращаются к версии каталога для страницы x (то есть, d(x)). В качестве каталога, записи в х содержат PFN целевых таблиц страниц и принципиальное различие между x и d(x) заключается в том, что для каждого целевого
i
i
i
t в каталоге x страниц x содержит PFN для t, в то время как d(x) содержит PFN для t(t), другими словами, d(x) модифицируется для того, чтобы указать на версии таблицы целевых страниц вместо первоначальных версий этих страниц.
i
i
i
i
i
Когда обращаются к странице d(x), соответствующая запись в d(x) (то есть запись, указанная частью смещения каталога виртуального адреса, элемент 211 на фиг.2) указывает на страницу t(y). Затем обращаются к странице t(y), чтобы определить местоположение конкретной страницы данных. Записи в t(y) содержат PFN целевых страниц данных. Соотношения между t(y) и y аналогичны соотношениям между d(x) и x: для каждой страницы d данных, указываемой y, t(y) содержит PFN для m(d) вместо PFN для d. (Следует отметить, однако, что PFN для m(d) обычно является тем же самым, что и PFN для d, так как хранение версии данных страницы в первоначальном местоположении страницы является в общем случае наиболее эффективным использованием памяти). Используя смещение, указанное полем смещения таблицы виртуального адреса (например, элемент 212 на фиг.2), определяют местоположение соответствующей записи в таблице t(y). Эта запись относится к PFN конкретной страницы данных, которой в этом примере является m(z).
После того как страница m(z) идентифицирована, к соответствующему модулю данных в странице m(z) обращаются на основании смещения страницы, указанном в виртуальном адресе (элемент 213 на фиг.2).
Таким образом, в обычном процессе преобразования адресов путь к странице данных ведет от страницы x к странице y, к странице z. Когда используются теневые таблицы страниц согласно изобретению, страница преобразования ведет от страницы d(x) к странице t(y), к странице m(z).
Создание страниц d(x),t(x) и m(x)
Страницы d(x), t(x) и m(x) создаются посредством выполнения заданных преобразований над страницей x.
Ниже следует описание предпочтительного варианта воплощения этих преобразований.
Предпочтительно, m(x) представляет фактические данные, которые программы записывают в страницу x, без какой-либо модификации или фильтрации. Другими словами, преобразование из x в m(x), по существу, является тождественным преобразованием.
i
i
i
i
i
i
Предпочтительно, d(x) и t(x) создаются согласно следующим правилам. d(x) является тем же, что и x, за исключением того, что для каждой страницы t, ссылающейся на запись страницы x, которая отмечена как присутствующая, соответствующая запись в d(x) относится к PFN для t(t) вместо PFN для t. t(x) является той же, что и x, за исключением того, что для каждой страницы d, ссылающейся на запись страницы x, которая отмечена как присутствующая, t(x) относится к PFN для m(d) вместо PFN для d. Дополнительно, если целевая страница является считываемой, но не перезаписываемой при релевантной политике, или если целевая страница является каталогом страниц или таблицей страниц, то запись отмечается как "только для считывания".
Ниже приведено более формальное описание того, как создаются d(x) и t(x). Для целей этого описания D1 является набором PFN, которые являются пригодными для использования в качестве каталогов страниц, и D2 является набором PFN, которые являются пригодными для использования в качестве таблиц страниц. Выражение D1.x означает, что x является элементом D1, и D2.x означает, что x является элементом D2. Пусть М будет картой распределения памяти, как видно релевантным программным объектом, на котором схема управления доступом к памяти должна быть установлена. M.x.e относится к значению, сохраненному в “e”-й записи физической страницы, чьей PFN является x. "R.x" означает, что x является считываемой при релевантной политике, и W.x означает, что x является перезаписываемой при релевантной политике. m, t, d и P являются такими, что поддерживаются следующие соотношения (в каждом случае пусть v есть M.x.e и пусть D.x = D1.x V D2.x):
Если R.x, m.x = t.x = d.x = не определено, где "не определено" является PFN страницы не в физической памяти.
d.x = если D1.x, то x, иначе не определено
D2.x => t.x = не определено
P.(m.x).e = v (то есть в P, m.x выглядит точно так же, как x в M)
d.x ≠ не определено => P.(d.x).e = если v. присутствует, то v [PFN  t (v.PFN)], иначе v
T.x ≠ не определено => P.(T.x).e =если v. присутствует, то v [PFN  m.(v.PFN), rw  (v.rw  ( R.(v.PFN) => W.(v.PFN))  D.(v.PFN))], иначе v
Другими словами, версия каталога для x выглядит точно так же, как версия памяти для x, но с PFN, переадресованными к версиям таблицы; версия таблицы для x выглядит точно так же, как версия памяти для x, но с PFN, переадресованными на считываемые версии, и с битами считывания-записи, сброшенными для адресатов, которые являются считываемыми, но не перезаписываемыми, или в D (или иначе битами "только для считывания", установленными для таких адресатов, в зависимости от того, включает ли в себя представление записи (элемента) бит "считывания/записи" или бит "только для считывания"). Следует заметить, что для каталогов сохраняется версия x каталога в х, но для таблиц сохраняется версия считывания x в х для минимизации стоимости удаления x из D2 (например, для обмена ее с диском). Всякий раз, когда оказывается, что версии хранят одни и те же данные (например, для каталогов и таблиц, которые УПА будет иметь разрешенными), они совместно используют одну и ту же физическую страницу, так что для программного объекта, который не пытается осуществлять операции записи, которые УПА может отклонить или изменить, никакие теневые страницы не должны быть созданы.
Фиг.6 и 7 показывают пример процессов для создания d(x) и t(x) соответственно.
Со ссылками на фиг.6 предполагается, что имеется страница x, которая является частью карты (то есть карты М, как описано выше), и желательно создать страницу d(x) на основании х. Сначала определяют (602), является ли страница x считываемой при соответствующей политике. Если x не является считываемой, то d(x) является неопределенной (606), и процесс заканчивается. Если x является считываемой, то определяют (604), является ли x элементом D1, то есть обозначена ли x пригодной для использования в качестве каталога страниц. Если x не является элементом D1, то d(x) является неопределенной (606). Если x является элементом D1, тогда страница d(x) создается такой, что она содержит то же самое содержимое, что и страница x, за исключением того, что поля PFN в записях, отмеченные как "присутствующие", изменяются, чтобы указать на версии таблицы их адресатов. Этот результат может быть достигнут, устанавливая n=0 (607), и затем для заданного значения n определяют, отмечена ли n-я запись как присутствующая (608). Если n-я запись не отмечена как присутствующая, то n-я запись в d(x) может быть установлена равной n-й записи в (610). Если n-я запись отмечена как присутствующая, то n-я запись в d(x) устанавливается равной n-й записи в х, за исключением того, что поле PFN изменяется, чтобы указать на версию таблицы (612), то есть, если P.n.PFN ссылается на поле PFN страницы P, и если v имеет значение, описанное выше, то d(x).n.PFN = t(v.PFN). После того, как n-я запись в d(x) установлена, n увеличивается (614), и процесс возвращается к этапу 608, чтобы установить следующую запись.
Со ссылками на фиг.7, снова предполагается, что имеется страница x, которая является частью карты, и желательно создать страницу t(x). Первоначально определяют (702), является ли x считываемой при релевантной политике. Если x не является считываемой, то t(x) устанавливают в неопределенное значение, и процесс заканчивается. Если x является считываемой при этой политике, то определяют (704), является ли x элементом D2. Если x не является элементом D2, то t(x) устанавливают в неопределенное значение (706). Если x является элементом D2, то страницу t(x) создают такой, что значения в записях являются равными значениям в х, за исключением того, что PFN страниц, отмеченных как присутствующие, корректируются так, чтобы они указывали на версию памяти целевой страницы, и некоторые ссылки для считывания/записи корректируются так, чтобы сделать их предназначенными только для считывания. Чтобы создать это содержимое для страницы t(x), первоначально счетчик n устанавливают в 0 (этап 708). Затем определяют, отмечена ли n-я запись в странице x как присутствующая. Если запись не отмечена как присутствующая, то n-я запись в t(x) устанавливается равной n-й записи в х (этап 712). Если n-я страница отмечена как присутствующая, то n-я запись в странице t(x) устанавливается равной n-й записи в х, за исключением того, что поле PFN этой записи устанавливается так, чтобы указать на версию памяти целевой страницы (714), то есть, если целевая страница n-й записи в х имеет PFN = A, то поле PFN этой n-й записи в t(x) установлено равным m(A). (Как отмечено выше, PFN для m(A) часто равен PFN для A.) Затем определяют (716), является ли целевая страница n-й записи страницей, которая является считываемой, но не перезаписываемой при релевантной политике. Если целевая страница является считываемой, но не перезаписываемой, то n-я запись в t(x) отмечается как предназначенная только для считывания (720). Иначе определяют (718), является ли целевая страница n-й записи в х элементом D1 или D2. Если это так, то n-я запись в t(x) отмечается как предназначенная только для считывания (720). Значение счетчика n затем увеличивается (722), и процесс возвращается назад к этапу 714, чтобы создать следующую запись в t(x).
Сохранение теневых страниц
Возможно хранить три копии каждой страницы (то есть, d(x), t(x) и m(x)), хотя имеются некоторые способы оптимизации, которые позволяют страницам быть представленными более эффективно. Во-первых, нет необходимости создавать теневую страницу, если алгоритмы, описанные выше, могут привести к созданию теневой страницы, которая является идентичной версии, которая уже сохранена. Таким образом, для большинства страниц необходимо сохранять только одну версию страницы, в этом случае для такой страницы x, PFN для d(x), t(x) и m(x) - все являются одинаковыми.
Во-вторых, для всех страниц, отличных от каталогов, предпочтительно первоначальную копию страницы x использовать в качестве версии данных этой страницы. Таким образом, для страниц не-каталогов (то есть страниц, чей номер блока не является элементом D1) PFN для m(x) равен PFN для x; версии каталога и таблицы для x могут быть сохранены в другом месте. В случае страниц каталога, однако, предпочтительно (и в некоторых случаях необходимо) для первоначального определения местоположения страницы использовать в качестве версии каталога страниц. Так как набор D1 определен в терминах PFN страниц, которым разрешено выступать в качестве каталогов (например, в процессоре INTEL x86, те страницы, чьи PFN могут быть загружены в CR3), непрактично перемещать версию каталога в другой PFN: так как CR3 должен быть загружен программным объектом, который может быть не оповещен о существовании теневых страниц (например, CR3 может быть загружен операционной системой, чей доступ к памяти ограничивается системой УПА), может быть необходимо разместить страницы каталога в PFN, в которых, как полагает программный объект, эти страницы расположены.
Использование теневых страниц с большими страницами
Как описано выше, процессор INTEL x86 (так же как и различные другие процессоры) поддерживает использование больших страниц, в этом случае никакая таблица страниц не вовлечена в преобразование виртуального адреса в физический адрес. Чтобы включить большие страницы в работу механизма создания теневых станиц, описанного выше, таблица теневых страниц может быть создана для большой страницы даже при том, что эта таблица теневых страниц не соответствует какой-либо реальной таблице страниц. Таким образом, когда каталог x страниц содержит большую ссылку, может быть создана версия каталога этой страницы (то есть d(x)), которая содержит маленькую ссылку в записи, которая соответствует большой ссылке для x. Эта маленькая ссылка указывает на таблицу теневых страниц (то есть t(x)), которая содержит ссылки на индивидуальные маленькие страницы, которые составляют большую страницу. Так как часть алгоритма создания теневых страниц, описанного выше, вовлекает отметку некоторых страниц как предназначенных только для считывания, разбиение большой страницы на маленькие страницы избегает необходимости отмечать полную большую страницу как страницу, предназначенную только для считывания. Индивидуальные маленькие страницы, которые являются частью большой страницы, могут быть отмечены как предназначенные только для считывания в случае необходимости. (Недостаток в маркировке большой страницы как предназначенной только для считывания заключается в том, что каждый запрос записи к такой странице может генерировать исключение и должен быть оценен более привилегированным компонентом (например, компонентом, который выполняет УПА), чтобы определить, может ли запись иметь место без того, чтобы нарушить применимый инвариант. Требование обработки каждого запроса на запись к большой странице, таким образом, может значительно ухудшить производительность системы).
Следует отметить, что приведенные выше примеры приведены просто с целью объяснения и не предназначены для того, чтобы рассматриваться как ограничение существующего изобретения. В то время как изобретение было описано со ссылкой на различные воплощения, понимается, что признаки, которые использовались, являются признаками описания и чертежей, а не ограничениями. Кроме того, хотя изобретение было описано со ссылками на конкретные средства, данные и варианты воплощения, изобретение не ограничивается этими конкретными раскрытыми сведениями, скорее изобретение распространяется на все функционально эквивалентные структуры, способы и использования, например, тех, что входят в прилагаемую формулу изобретения. Квалифицированный специалист в данной области, ознакомленный с настоящим описанием, может создать многочисленные модификации и изменения этого изобретения без выхода за рамки формы и объема изобретения в его аспектах.