РЕАЛИЗАЦИЯ УПРАВЛЕНИЯ ДОСТУПОМ К ПАМЯТИ С ИСПОЛЬЗОВАНИЕМ ОПТИМИЗАЦИЙ

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

По данной заявке испрашивается приоритет предварительной заявки №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 в состоянии, которое удовлетворяет условию управления доступом к памяти, являются:

1. Набор вершин на расстоянии k от корневых вершин. В более формализованном виде, если S является набором вершин, а w - вершиной, то тогда d_k(S,w) означает утверждение, состоящее в том, что существует (ориентированный) путь длиной k от некоторой вершины в S к вершине w. S_d={v О V: d_k(S,w}. Тогда, если S является корневой вершиной, то S_d относится к набору страниц, расположенных на расстоянии d от корня. Например, если вершина 502 является корнем графа 500, то тогда набор вершин, имеющих расстояние 1 от корневой вершины, состоит из вершин 504 и 510, поскольку любую из этих вершин можно достичь из корня, перемещаясь по одному ребру. Обратимся к карте страниц, показанной на фиг.2, где каталог 202 страниц находится на расстоянии 1 от корня, а таблицы страниц с 204(1) по 204(3) находятся на расстоянии 2 от корня. Таким образом, в примере по фиг.2 адреса каталога страниц и таблиц страниц можно кэшировать, сохраняя идентификационные данные этих страниц, которые представляют собой соответствующие расстояния 1 и 2 от корня.

2. Наборы, определенные метками на ребрах. Обратимся за примером к фиг.5, где набор вершин, которые имеют входящее ребро с меткой «А», состоит из вершин 504 и 510, а набор вершин, которые имеют входящее ребро с меткой «B», состоит из вершин 504, 506 и 512. На карте страниц по фиг.2, где атрибуты соответствуют меткам на ребрах, набор можно определить в виде страниц, имеющих заданный атрибут. Например, возможно окажется полезным определить (и кэшировать) набор страниц с меткой «только для считывания», где можно задать набор страниц, у которых бит «только для считывания» находится в состоянии «включено» (ссылочная позиция 304, показанная на фиг.3). (Это возможно для страницы, к которой обращаются более одного раза в карте страниц, при этом разные ссылки на страницу могут иметь атрибуты «только для считывания», установленные по-разному; в этом случае такое определение набора может разрешить конфликтную ситуацию; например, страница попадает в набор, если по меньшей мере одна ссылка на эту страницу имеет атрибут «только для считывания», либо если каждая ссылка на эту страницу имеет атрибут «только для считывания» и т.д.).

Можно провести различие между локальными и нелокальными свойствами. Локальные свойства можно вычислить из ребер, входящих в заданную вершину; то есть, если можно определить, имеет ли вершина v свойство Р только исходя из ребер, которые входят в v, то говорят, что Р является локальным свойством. В противном случае, Р является нелокальным свойством. Примером локального свойства является свойство «Вершина имеет входящее ребро с меткой «запись/чтение»». Примером нелокального свойства является свойство «страница (в машине x86) имеет отображения «считывание/запись»».

3. Набор вершин, в которые входят k ребер с некоторым свойством. В более формализованном виде, если P, Q являются предикатами, а w является вершиной, то тогда

In-deg _P,Q (w)= з{vО V:P(v) и (v,w,l)О E и Q(l)}з

Набор может быть определен в виде набора вершин с заданной степенью вхождения (in-degree):

{v О V:In-deg _P,Q (v)=k}

Аналогичным образом могут быть заданы наборы на основе неравенства; например, набор вершин, в которые входят более чем (или менее чем) k ребер с некоторым свойством.

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

4. Аналогичный набор можно определить на основе степени выхода (out-degree), то есть набора вершин, которые имеют k исходящих ребер (или более k исходящих ребер, или менее k исходящих ребер) с некоторым свойством. Например, на фиг.5 набор вершин, которые имеют ровно два исходящих ребра с меткой «А», состоит из вершины 502. На фиг.2 содержатся аналогичные примеры; например, набор страниц, имеющих по меньшей мере 3 исходящих ребра (то есть ссылки к другим страницам) включает в себя каталог 202 страниц.

Эти наборы могут быть скомбинированы посредством обычных операций, выполняемых над множествами (например, объединение, пересечение, дополнение, установление различий). Например, если S₂ является набором страниц на расстоянии 2 от корня, набор страниц с отображениями «записи/считывания» в некоторых конфигурациях процессора х86 CPU может быть выражен следующим образом:

({x: x имеет большое входящее ребро страницы} пересечение {x: x имеет внутреннее ребро «записи/считывания» (r/w)} пересечение S₂) объединение ({x: x имеет малое входящее ребро страницы} пересечение {x: x имеет отображение r/w} пересечение S₃).

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

Схемы кэширования

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

Схема 1: Простое кэширование набора

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

Init() - инициализирует кэш некоторым строго определенным значением, таким как пустой набор.

Add(S) - добавляет S (один элемент или набор элементов) в кэш.

Remove(S) - удаляет S (один элемент или набор элементов) из кэша.

ShowCache(S) - возвращает все элементы, которые в текущий момент кэшированы. Кэш может предоставлять дополнительные операции доступа (например, для повышения эффективности).

Одним из способов представления такого кэша является битовый вектор. Например, если система имеет 2¹⁶ физических страниц памяти, то вектор, длина которого составляет 2¹⁶ битов (то есть, 8 Kбайт), может представлять булево значение для каждой страницы. n-й бит находится в состоянии «включено» или «выключено» в зависимости от того, находится ли n-я страница в заданном наборе. Таким образом, при заданном определенном наборе страниц членство в этом наборе можно кэшировать, затрачивая один бит на страницу. Очевидно, что операции над множествами, такие как объединение и пересечение, очень просто выполнить с помощью представления такого типа путем использования побитовых операторов «ИЛИ» («or») и «И» («and»).

Схема 2: Создание расширенного набора/поднабора

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

Схема 3: Обратное представление ребер

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

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

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

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

Init() - инициализирует кэш некоторым строго определенным значением, таким как 0.

Increment() (приращение).

Decrement() (отрицательное приращение).

GetValue() (получить значение).

Известно использование счетчиков ссылок (или аналогичных структур данных) для построения наборов. Например, иллюстративный алгоритм управления доступом к памяти может вычислять набор вершин без входящих ребер, то есть набор вершин, у которого результат подсчета ссылок равен 0. Группа счетчиков ссылок может управлять кэшем (Схема 1) этого набора следующим образом. Всякий раз, когда изменяется значение счетчика ссылок, алгоритм проверяет, стало ли это значение равным нулю. Если это так, то вершина добавляется в кэш. Аналогичным образом алгоритм отслеживает событие, состоящее в том, что счетчик ссылок, значение которого было равно нулю, принимает другое значение. При этом событии алгоритм удаляет вершину из кэш-памяти.

Далее приведено несколько примеров использования кэширования:

Кэширование расширенных наборов S_d' из S_d для d=1,2,3.

Для d=2,3: Кэш может (а) храниться в явном виде или (b) приводиться в действие счетчиком ссылок.

Вычисление локальных свойств разметки: «имеет входящие ребра записи/считывания» и «имеет большие/малые входящие ребра страниц».

Вычисление нелокальных свойств: «имеет отображения записи/считывания».

Использование счетчиков ссылок для нескольких входящих ребер считывания/записи для вершин в S₂. Эту информацию можно использовать для ускорения вычисления нелокального свойства «имеет отображения считывания/записи».

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

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

Сначала принимается (602) запрос на доступ к памяти. Когда запрос на доступ принят, система управления доступом к памяти оценивает этот запрос, чтобы определить, совместимо ли выполнение данного запроса с политикой, определяющей доступ к памяти (604). Примеры политик доступа к памяти обсуждались выше. Как показано в одном примере, политика может определять некоторые страницы как запрещенные для некоторого набора источников, а также политика может запретить любой запрос на доступ, который мог бы привести к созданию, для одной из запрещенных страниц, отображения, которое будет доступно одному из тех источников, которым не разрешен доступ к этой странице. Оценку запроса можно облегчить посредством использования сохраненной или кэшированной информации (606). Эта сохраненная или кэшированная информация может содержать данные о карте (картах) страниц, например набор страниц, о которых известно, что они содержат допустимые каталоги страниц.

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

Заметим, что вышеупомянутые примеры были приведены только для объяснения и никоим образом не претендуют на ограничение настоящего изобретения. Хотя изобретение было описано со ссылками на различные варианты его осуществления, очевидно, что использованные здесь термины носят описательный и иллюстративный, а не ограничительный характер. Кроме того, хотя изобретение было описано здесь со ссылками на конкретные средства, материалы и варианты реализации, предполагается, что данное изобретение не сводится к раскрытым здесь конкретным вариантам; наоборот, изобретение распространяется на все функционально эквивалентные структуры, способы и варианты использования, не выходящие за рамки объема, определяемого прилагаемой формулой изобретения. Специалисты в данной области техники, опираясь на положительные результаты, раскрытые в данном описании, смогут реализовать многочисленные модификации и внести изменения в изобретение, не выходя за рамки объема и сущности изобретения в его аспектах.