Реализация управления доступом к памяти с использованием оптимизаций

Реализация управления доступом к памяти с использованием оптимизаций

Иллюстрации

Показать все

Реферат

Перекрестные ссылки на родственные заявки

По данной заявке испрашивается приоритет предварительной заявки №60/467343 «Techniques for Efficient Implementation of Memory Access Control» («Способы эффективной реализации управления доступом к памяти»), поданной 2 мая 2003 года.

Область техники, к которой относится изобретение

Настоящее изобретение относится в целом к компьютерной защите. В частности, изобретение относится к эффективным способам реализации изолированной, или «зашторенной», памяти с использованием управления трансляцией адресов.

Предшествующий уровень техники

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

Одним из путей реализации "зашторенной" памяти является использование управления трансляцией адресов.

Во многих современных компьютерах используется система виртуальной памяти, в которой программные средства, выполняемые на компьютере, обращаются к памяти, используя виртуальные адреса, а блок управления памятью использует набор карт трансляции адресов для трансляции виртуальных адресов в физические адреса. Обычно каждый процесс имеет свою собственную карту трансляции адресов, так что отображение между виртуальными адресами и физическими адресами изменяется от процесса к процессу. Можно сконфигурировать карту трансляции адресов для данного процесса таким образом, что карта процесса не будет открывать процессу какой-либо виртуальный адрес для заданного блока (например, страницы) физической памяти. Таким образом, обеспечив наличие виртуальных адресов для заданного блока физической памяти только у защищенных процессов, можно реализовать «зашторенную» память путем управления содержимым карт трансляции адресов.

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

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

Сущность изобретения

Настоящее изобретение предоставляет механизмы для эффективного управления изменениями в картах трансляции адресов. «Зашторенная» память может быть реализована путем предотвращения перехода карт трансляции адресов в состояние, при котором виртуальный адрес для блока «зашторенной» памяти оказывается открытым для процесса (или другого объекта), которому не разрешен доступ к «зашторенной» памяти. «Политика» определяет, какие операции доступа к памяти разрешены, а система управления доступом к памяти может действовать, запрещая карте трансляции адресов переход в любое состояние, которое противоречит упомянутой политике.

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

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

Другие признаки изобретения описаны ниже.

Перечень фигур чертежей

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

фиг.1 - блок-схема вычислительной среды, в которой можно реализовать аспекты настоящего изобретения;

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

фиг.3 - блок-схема примерной таблицы страниц с атрибутами;

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

фиг.5 - блок-схема ориентированного размеченного графа, который представляет карту трансляции адресов;

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

Подробное описание изобретения

Примерная вычислительная конфигурация

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

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

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

Обратимся к фиг.1, где иллюстративная система для реализации изобретения включает в себя вычислительное устройство общего назначения в виде компьютера 110. Компоненты компьютера 110 могут включать в себя, но не в ограничительном смысле, процессор 120, системную память 130 и системную шину 121, которая соединяет различные системные компоненты, включая системную память, с процессором 120. Системная шина 121 может относиться к любому из нескольких типов шинных структур, включая шину памяти или контроллер памяти, периферийную шину и локальную шину с использованием любой из разнообразия шинных архитектур. В качестве примера, но не ограничения, такие архитектуры могут включать в себя шину с архитектурой промышленного стандарта (ISA), шину с микроканальной архитектурой (MCA), шину с расширенной архитектурой ISA (EISA), локальную шину Ассоциации по стандартам видеооборудования (VESA) и шину межсоединений периферийных компонентов (PCI) (известную также как мезонинная шина).

Компьютер 110 обычно включает в себя разнообразные машиночитаемые носители. Машиночитаемые носители могут представлять собой любые имеющиеся носители, к которым компьютер 110 может осуществить доступ, и могут включать в себя как энергозависимые, так и энергонезависимые носители, а также как съемные, так и несъемные носители. В качестве примера, но не как ограничение, машиночитаемые носители могут содержать компьютерные носители данных и среды передачи данных. Компьютерные носители данных включают в себя энергозависимые и энергонезависимые, съемные и несъемные носители, реализованные любым способом или по любой технологии для хранения информации, такой как машиночитаемые команды, структуры данных, программные модули или другие данные. Компьютерные носители данных включают в себя, но не в ограничительном смысле, ОЗУ (RAM), ПЗУ (ROM), электрически стираемое программируемое ПЗУ (EEPORM), флэш-память, либо память, выполненную по другой технологии, ПЗУ на компакт-диске (CD ROM), цифровые универсальные диски (DVD) либо другое запоминающее устройство на оптическом диске, магнитные кассеты, магнитную ленту, запоминающее устройство на магнитном диске или другие магнитные запоминающие устройства, либо любой другой носитель, который можно использовать для хранения требуемой информации и к которому компьютер 110 может осуществить доступ. Среды передачи данных обычно воплощают машиночитаемые команды, структуры данных, программные модули либо другие данные в сигнале, модулированном данными, таком как сигнал несущей или другой механизм транспортировки, и включают в себя любые среды для доставки информации. Термин «сигнал модулированный данными» означает сигнал, имеющий одну или несколько характеристик, которые установлены или изменены таким образом, чтобы закодировать информацию в этом сигнале. Например, но не как ограничение, среда передачи данных включает в себя проводную среду, такую как проводная сеть или непосредственное проводное соединение, и беспроводную среду, такую как акустическая, радиочастотная (RF), инфракрасная и другие беспроводные среды. В состав машиночитаемых носителей также следует включить комбинации из любых вышеперечисленных сред.

Системная память 130 включат в себя компьютерный носитель данных в виде энергозависимой и/или энергонезависимой памяти, такой как постоянное запоминающее устройство 131 (только для считывания) (ROM) и оперативное запоминающее устройство 132 (с произвольной выборкой) (RAM). В памяти ROM 131 обычно находится базовая система 133 ввода/вывода (BIOS), содержащая базовые процедуры, которые помогают пересылать информацию между элементами в компьютере 110, к примеру, во время запуска. Память RAM 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). К системной шине 121 через интерфейс, такой как видеоинтерфейс 190, также подсоединен монитор 191 либо устройство отображения другого типа. В дополнение к монитору компьютеры могут также включать в себя другие периферийные устройства вывода, такие как громкоговорители 197 и принтер 196, которые могут быть подсоединены через выходной периферийный интерфейс 190.

Компьютер 110 может работать в сетевой среде, используя логические соединения с одним или несколькими удаленными компьютерами, такими как удаленный компьютер 180. Удаленный компьютер 180 может представлять собой персональный компьютер, сервер, маршрутизатор, сетевой персональный компьютер, одноранговое устройство либо другой обычный сетевой узел, причем, хотя на фиг.1 показано только запоминающее устройство 181, такой компьютер обычно включает в себя многие или все элементы, описанные выше в связи с компьютером 110. Логические соединения, изображенные на фиг.1, включают в себя локальную сеть (LAN) 171 и глобальную сеть (WAN) 173, но также могут включать другие сети. Такие сетевые среды типичны для офисов, компьютерных сетей масштаба предприятия, интрасетей и Интернет.

При использовании сетевой среды LAN компьютер 110 подсоединен к LAN 171 через сетевой интерфейс или адаптер 170. При использовании в сетевой среде WAN компьютер 110 обычно включает в себя модем 172 либо другое средство для установления связи через сеть WAN 173, такую как Интернет. Модем 172, который может быть встроенным или внешним, можно подсоединить к системной шине 121 через интерфейс 160 пользовательского ввода либо другой подходящий механизм. В сетевой среде программные модули, показанные применительно к компьютеру 110 или его частям, могут храниться в удаленном запоминающем устройстве. На фиг.1 в качестве примера, но не как ограничение, показано, что удаленные прикладные программы 185 находятся в запоминающем устройстве 181. Очевидно, что показанные сетевые соединения являются лишь примерами и что можно использовать другие средства для установления линии связи между компьютерами.

Доступ к памяти с использованием трансляции адресов

Память в компьютерной системе (например, RAM 132, показанная на фиг.1) имеет физический адрес для каждого байта. Таким образом, байты, составляющие эту память, можно рассматривать как пронумерованные, так что каждый байт может быть однозначно идентифицирован по его номеру. В этом случае номер образует физический адрес. Например, в памяти объемом 256 байт байты могут иметь физические адреса в диапазоне от нуля до 2²⁸-1. Однако в современных компьютерных системах к памяти обычно обращаются не по физическому адресу, а по виртуальному адресу. Для преобразования физических адресов в виртуальные адреса используют карту трансляции адресов.

На фиг.2 показан пример карты трансляции адресов и ее использования в реальной компьютерной системе. Показанная на фиг.2 иллюстративная карта трансляции адресов является «страничной» схемой, где память разбита на блоки, называемые «страницами». На фиг.2 представлена страничная схема, используемая в процессоре INTEL x86.

На фиг.2 каталог 202 страниц содержит массив указателей (то есть физические базовые адреса) таблиц страниц, таких как таблицы 204(1), 204(2) и 204(3) страниц. Каждая таблица страниц, в свою очередь, содержит массив указателей базовых адресов страниц (например, страницы 206(1), 206(2), 206(3) и 206(4)) и также может содержать информацию, такую как атрибут «только для считывания/только для записи», бит «присутствует/отсутствует» и т.д., как было описано выше. Страницы являются участками памяти RAM 132 фиксированной длины. Вдобавок, каталог страниц и таблицы страниц также обычно храняться в RAM 132. Страничная схема, изображенная на фиг.2, является двухуровневой страничной схемой, поскольку для определения местоположения конкретной страницы необходимо исследование как каталога страниц (уровень 1), так и таблицы страниц (уровень 2). Специалистам в данной области техники очевидно, что можно построить страничную схему с произвольным количеством уровней и что изобретение применимо ко всем страничным схемам такого рода. Специалистам в данной области техники также известно, что в процессоре INTEL x86 обычно используется двухуровневая страничная схема, показанная на фиг.2, но также возможна конфигурация, где используется одноуровневая или трехуровневая страничная схема.

В страничной схеме по фиг.2 любой байт на странице может быть идентифицирован по виртуальному адресу 210, содержащему смещение 211 каталога страниц, смещение 212 таблицы страниц и смещение 213 страницы. Таким образом, для того, чтобы определить физический адрес, блок управления памятью (MMU) 220 использует смещение 211 каталога страниц для определения местоположения конкретного элемента в каталоге 202 страниц. Этот элемент является физическим базовым адресом таблицы страниц, так что MMU 220 разыменовывает этот адрес, чтобы определить местоположение одной из таблиц страниц (например, таблицы 204(1)) страниц. Затем блок MMU 220 использует смещение 212 таблицы страниц в качестве индекса в идентифицированной таблице страниц и извлекает элемент, обнаруженный при этом смещении. Этот элемент является физическим базовым адресом страницы (например, страницы 206(1)), так что блок MMU добавляет смещение 213 страницы к базовому адресу идентифицированной страницы, чтобы определить местоположение конкретного байта физической памяти. Блок MMU 220 может быть сконфигурирован таким образом, чтобы учитывать такую информацию, как информация о том, отмечена ли данная страница как страница только для считывания или чтения/записи, отмечена ли страница как «присутствующая» или «отсутствующая» и т.д., как описывается ниже в связи с фиг.3.

Страничная схема по фиг.2 также включает в себя ячейку 201 памяти, которая содержит указатель на каталог страниц. Блок MMU 220 использует этот указатель для определения местоположения каталога 202 страниц, когда начинается трансляция виртуального адреса 210. В примере с процессором INTEL x86 ячейка 201 памяти соответствует регистру под названием CR3 - то есть, в процессоре INTEL x86 в регистре CR3 хранится физический адрес каталога страниц для текущего контекста. Таким образом, можно построить альтернативные наборы таблиц трансляции (то есть два или более наборов каталогов страниц и таблиц страниц) и изменить применяемый набор таблиц трансляции просто путем записи базового адреса нового каталога страниц в ячейку 201 памяти. Этот способ принято использовать для каждого процесса, выполняющегося на компьютере, чтобы иметь собственный каталог страниц и таблицы страниц, когда выполняется «переключение контекста» (то есть операция, которая, среди прочего, предписывает системе виртуальной памяти указать адресное пространство для нового процесса) путем записи базового адреса каталога страниц нового процесса в ячейку 201 памяти. В случае, когда каждый процесс имеет свой собственный каталог страниц, идентификационные данные процесса, выполняющегося в текущий момент, определяют, какое значение загружается в ячейку 201 памяти.

В дополнение к указателям на страницы, таблицы страниц и каталоги страниц могут также содержать «атрибуты» для страниц. На фиг.3 показаны детали иллюстративной таблицы 204(1) страниц, которая содержит как указатели, так и атрибуты. Каждый элемент в таблице 204(1) страниц включает в себя адрес 302 конкретной страницы, бит 304, служащий индикатором того, является ли страница, на которую указывает этот элемент, страницей «только для считывания», и бит 306, служащий индикатором того, «присутствует» ли страница, на которую указывает этот элемент. Таким образом, если первый элемент 301 в таблице 204(1) страниц указывает на страницу 206(1) (показанную на фиг.2), то тогда бит 304, в зависимости от того, установлен ли он в «нуль» или в «единицу», служит индикатором того, должен ли блок MMU 220 (показанный на фиг.2) разрешить как считывание, так и запись для страницы 206(1), либо только считывание. Аналогично, бит 306 служит индикатором того, присутствует или нет страница 206(1) в памяти. (Бит 306 может также быть установлен в «нуль», показывая отсутствие, если, например, содержимое страницы 206(1) было перемещено на диск, чтобы освободить место для других страниц в памяти). В таблице 204(1) страниц могут также храниться и другие атрибуты.

Использование карт трансляции адресов для управления доступом к памяти

В системе, где доступ к памяти осуществляется по виртуальному адресу, можно реализовать систему, которая ограничивает доступ к памяти на основе следующего положения: если карта трансляции адресов сконфигурирована таким образом, что ни один виртуальный адрес не транслируется в данный физический адрес, то тогда память, представленная этим физическим адресом, является недоступной. Например, в страничной схеме, описанной выше в связи с фиг.2, заданная страница памяти (например, страница 206(1)) может быть сделана недоступной посредством гарантии отсутствия каких-либо путей, ведущих через карту к этой странице. При отсутствии такого пути не будет виртуального адреса 210, который транслировался бы в страницу. В системе, где любой доступ к памяти осуществляется по виртуальному адресу, недоступность заданной страницы (или другой части) памяти обеспечивается организацией соответствующего управления картой трансляции адресов, не допускающего использование виртуальных адресов для этой части памяти. Даже в тех системах, где в той или иной степени разрешена физическая адресация памяти, недоступность памяти можно обеспечить путем дополнения управления картой трансляции адресов управлением теми запросами на доступ, которые основаны на физическом адресе.

Способ управления содержимым карты трансляции адресов с целью управления доступом к памяти формально можно сформулировать следующим образом. Предположим, что S является набором источников, которые потенциально могут осуществить доступ к памяти. Предположим далее, что P является политикой, которая определяет, какие части памяти какому источнику могут быть доступны. Таким образом, если s О S является источником, то тогда MP(s) обозначает часть памяти, которая доступна источнику s через карту трансляции адресов (например, набор ячеек памяти, которые имеют виртуальные адреса), а NA(Ps) обозначает части памяти, к которым данному источнику не разрешен доступ согласно политике Р. (В случае, когда каждый процесс имеет свою собственную карту трансляции адресов, каждый процесс можно рассматривать как отдельный «источник», хотя понятно, что концепция источника выходит за рамки примера одного процесса). Таким образом, соблюдение политики можно гарантировать, пока выполняется следующее условие:

NA(P,s) ∩ MP(s) = φ

Это условие показано на фиг.4, где память 132 представлена в виде набора ячеек памяти, MP(s) 402 представлены в виде набора ячеек памяти, которые доступны источнику s через отображение карты трансляции адресов, а NA(P,s) 404 представлены в виде набора ячеек памяти, к которым не разрешен доступ со стороны источника s согласно политике Р. Поскольку в набор ячеек памяти, к которым не разрешен доступ от источника s согласно политике Р, не включена ни одна из ячеек (MP(s)), которые могут адресовать источник s через отображение в карте трансляции адресов, условие, показанное на фиг.4, эффективно реализует политику Р применительно к источнику s.

Таким образом, проблема управления доступом источника s к частям памяти 132 в некоторых случаях может быть сведена к обеспечению безусловного выполнения условия, показанного на фиг. 4. Одним из решений этой проблемы является оценка любой операции (например, запись в память, загрузка регистра CR3 и т.д.), которая может потенциально изменить отображение в карте трансляции адресов, политику или текущий источник. Настоящее изобретение предлагает способы, позволяющие эффективно выполнить такую оценку.

Должно быть ясно, что условие, показанное на фиг.4, является лишь примером условия, которое можно использовать для реализации управления доступом к памяти. Возможны другие варианты условия, показанного на фиг.4, к примеру варианты, включающие в себя набор ячеек памяти, включенный в карту трансляции адресов, набор ячеек памяти, к которым разрешен доступ от источника s, но не для записи (или считывания) и т.д. Однако следует заметить, что упомянутые условия для управления доступом к памяти обычно включают в себя проверку «непересечения» двух или более наборов ячеек памяти.

Вдобавок, хотя MP(s) можно рассматривать как «отображенные страницы», доступные источнику s, следует заметить, что концепция управления доступом к памяти не сводится к системам, где используется страничная схема. В стандартном варианте реализации решение о том, в какие ячейки памяти разрешено источнику записывать данные согласно политике, либо о том, какие ячейки памяти отображаются для источника, принимается на постраничной основе. Однако изобретение не сводится к случаю распределения памяти на постраничной основе либо случаю, когда доступ к памяти разрешается или ограничивается на постраничной основе.

Обобщенная модель для трансляции адресов

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

В этой модели В является базовым набором, а L алфавитом. При заданных В и L, G = (V, E) является ориентированным графом с метками на ребрах, так что V Н B и E Н {(v,w,l): v О V, w О V, l О L}. Любой член Е можно интерпретировать как ориентированное ребро от вершины v к вершине w с меткой l. Метки также могут иметься и у вершин. На фиг.5 показан граф, соответствующий вышеописанной модели. Граф 500 включает в себя вершины 502, 504, 506, 508, 510 и 512. Эти вершины соединены ребрами 522, 524, 526, 528, 530, 532 и 534 так, как это показано на чертеже. Каждое ребро имеет метку с символом из алфавита. В данном примере алфавит содержит символы А, B и С. Таким образом, ребра 522 и 524 помечены символом А, ребра 526, 528 и 532 помечены символом В, а ребра 530 и 534 помечены символом С. Также могут иметь место элементы базового набора (например, элементы 550 и 552), которые не являются вершинами в графе 500.

Следует иметь в виду, что компоненты графа 500 соответствуют определенным компонентам карты трансляции адресов, показанной на фиг.2. Например, на фиг.2 в качестве вершин графа можно видеть каталог 202 страниц, таблицы 204(1) - 204(3) страниц и страницы 206(1) - 206(4). В качестве ребер графа здесь можно видеть указатели, которые соединяют эти вершины (например, указатели от элементов в таблице 204(1) страниц к страницам 206(1) и 206(2)). Применительно к фиг.3 в качестве метки для ребра здесь можно видеть атрибуты 304 и 306 записи (например, биты «только для считывания» и «присутствия»). Таким образом, «алфавит» является набором возможных перестановок атрибутов. (В примере по фиг.3, где имеется два двоичных атрибута, возможны четыре комбинации, так как в алфавите имеется четыре символа). В случае, когда атрибуты не используются, алфавит может содержать «пустой» символ. Кроме того, нераспределенные страницы памяти соответствуют членам базового набора, которые не имеют входящих ребер.

В модели графа, описанной выше, можно определить понятие «состояние». При заданных B и L «состояние» - это пара (R, G), где G - это ориентированный размеченный граф, определенный выше, а R Н V - это набор вершин G. R представляет набор «корневых вершин». Корневые вершины представляют тот набор вершин в базовом наборе, которые допустимо использовать в качестве корней для графа. В примере по фиг.2 набором «корневых вершин» является набор допустимых каталогов страниц (то есть те значения, которые разрешено загружать в ячейку 201 памяти, такую как регистр CR3 в процессоре INTEL х86). При заданных B и L набор S является набором всех состояний.

Согласно вышеопределенной модели механизм трансляции адресов (ATM) может быть смоделирован следующим образом:

базовый набор B вершин;

алфавит L (возможно пустой);

начальное состояние s₀ О S (где S - множество состояний);

набор правил перехода из состояния в состояние (возможно пустой);

функция трансляции адресов;

глобальные флаги.

Правила перехода из состояния в состояние изменяют механизм ATM при переходе от одного состояния к другому. Таким образом, можно определить набор правил r_i перехода из состояния в состояние: S ® S (где i - некоторый индекс), которые изменяют текущее состояние ATM. Механизмы ATM могут иметь правила перехода любого из следующих типов:

изменение (добавление, удаление, повторное задание меток) ребер G;

добавление или удаление вершин G;

изменение корневого набора R.

В примере на фиг.2 и 3 удаление указателя на страницу или изменение атрибутов страницы соответствует изменению ребра графа. Добавление новых каталогов страниц, новых таблиц страниц или новых страниц данных соответствует добавлению или удалению вершин. Задание нового страничного каталога, базовый адрес которого может быть загружен в ячейку 201 памяти (например, в регистр CR3), соответствует изменению корневого набора. В сущности, текущее состояние определяет, какие ячейки памяти потенциально доступны посредством трансляции адресов.

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

При заданном некотором свойстве Р (которое отличается от политики Р, описанной ниже), можно оценить запрос на выполнение действия, которое могло бы изменить состояние (выполнение r_i для некоторого i) из s в r_i(s), чтобы определить, является ли Р(r_i(s)) истинным, - то есть будет ли новое (предложенное) состояние, которое возникнет как результат выполнения r_i, иметь свойство Р. Если истинность Р означает, что ограничения на доступ к памяти не будут нарушены, то тогда истинность Р(r_i(s)) означает, что изменение состояния, осуществленное в результате выполнения r_i, разрешено продолжить. В противном случае, разрешение на продолжение операции не выдается.

Следует иметь в виду, что каждая запись в память может потенциально изменить состояние ATM. Таким образом, необходимо учесть два обстоятельства:

алгоритм должен вычислять Р(s) по возможности часто;

обычно новое состояние s' получают из старого состояния s. Если старое состояние имело свойство Р, то тогда появляется возможность упростить процесс принятия решения в отношении Р(s') посредством допущения относительно Р(s) и анализа только того, могут ли изменения (ограниченное количество изменений) в s, которые создали s', привести к нарушению Р.

Изобретение обеспечивает методики, позволяющие эффективно вычислять истинность Р. Как описано ниже, во многих случаях такая эффективность может быть достигнута путем сохранения (или кэширования) некоторой репрезентативной информации о текущем состоянии ATM, которую позднее можно использовать для принятия решения о том, какие тесты необходимо выполнить для подтверждения истинности Р при переходе из состояния в состояние и каких тестов можно избежать.

Иллюстративные классы свойств

Одним типом свойства Р является свойство, которое можно выразить в виде наборов вершин. Например, условие, показанное на фиг.4, и обсужденное выше, по существу является свойством, состоящим в том, что наборы MP(s) и NA(P,s) друг с другом не пересекаются. Множество свойств, которые можно выразить в виде наборов вершин и связей между этими наборами, можно эффективно реализовать путем сохранения (или кэширования) идентификационных данных вершин в наборе.

Примерами наборов, которые могут оказаться полезными при оценке того, находится ли механизм ATM в состоянии, кот