Безопасные указатели
Первобытный человек совершил гигантский шаг, открыв огонь. Он не только обеспечил себя теплом и едой, но также открыл себе путь к металлическим орудиям труда и далее к индустриальному обществу. Но огонь опасен при небрежном с ним обращении и может стать причиной ужасных бедствий. Для борьбы с диким огнем созданы специальные службы, что служит лишним доказательством серьезности вопроса.
Аналогично, гигантский шаг в разработке программного обеспечения произошел при изобретении понятия указателя или ссылки. Но небрежное обращение с указателями сродни игре с огнем. Указатели приносят неоспоримые преимущества, но при небрежном обращении немедленно следует катастрофа, например, «синий экран смерти», безвозвратная потеря данных, либо брешь в защите, через которую проникают вирусы.
Обычно в программном обеспечении высокой надежности использование указателей существенно ограничено. Ссылочные типы в Аде сочетают семантику указателей со множеством дополнительных ограничений в использовании. Это делает их пригодными для использования повсеместно, быть может, за редким исключением наиболее требовательных к безопасности областей.
Ссылки, указатели и адреса
Вместе с указателями появляются несколько возможностей совершить ошибки, такие как:
Нарушение типа — создать объект одного типа и получить доступ к нему (через указатель) как если бы он был другого типа. В более общем виде, используя указатель, обратиться к объекту таким способом, что нарушается согласованность с семантическими свойствами этого объекта (например, присвоить значение константе или обойти ограничения диапазона).
Висячие ссылки — доступ к объекту через указатель после того, как объект перестал существовать Это может быть указатель на локальную переменную после выхода из подпрограммы или на динамически созданный объект, уничтоженный затем через другой указатель.
Исчерпание свободного пространства — ошибка создания объекта вследствие нехватки ресурсов. Что в свою очередь может быть результатом следующего:
Созданные объекты становятся недоступными («мусором») и никогда не освобождаются;
Фрагментация «кучи», когда суммарное количество свободного пространства достаточно, но нет ни одного непрерывного участка нужного размера;
Необходимый размер «кучи» был недооценен;
Постоянная утечка (все созданные объекты доступны, но создаются бесконечно, например объекты создаются и добавляются в связный список в бесконечном цикле).
Хотя детали разнятся, нарушения типов и висячие ссылки возможны также и в языках, где есть указатели на подпрограммы.
Исторически в языках применялись различные подходы для решения этих проблем. Ранние языки, такие как Fortran, COBOL и Algol 60 не предоставляли пользователю такое понятие как указатель вообще. Программы на всех языках используют адреса в базовых операциях, таких как вызов подпрограммы, но пользователи этих языков не могли оперировать адресами напрямую.
C (и C++) предоставляют указатели как на объекты созданные в «куче», так и на объекты в стеке, а также на функции. Хотя некоторые проверки все же присутствуют, в основном программист сам должен следить за корректным использованием указателей. Например, т. к. C представляет массив, как указатель на первый элемент и разрешает арифметику над указателями, программист может легко себе создать проблему.
Java и другие «чисто» объектно-ориентированные языки не раскрывают существование указателей приложению, но используют указатели и динамическое создание объектов как базовые понятия языка. Проверка типов сохраняется, и удается избежать висящих ссылок (т. к. нет способа явно вызвать free). Чтобы предотвратить исчерпание «кучи» более недоступными объектами, вводится автоматическая сборка «мусора». Это приемлемо для некоторого класса программ. Но довольно спорно в программах реального времени, особенно в областях требующих высокой надежности и безопасности.
Следует заметить, что «сборка мусора» сама по себе не может защитить от исчерпания свободного пространства: программа добавляющая объекты в связный список в бесконечном цикле в конце концов истратит всю память несмотря на все усилия сборщика мусора. (Бесконечный цикл не обязательно является ошибкой в программе, системы управления процессом и им подобные часто пишутся как программы не имеющие завершения. Для остановки такой программы требуются внешнее влияние, например, чтобы оператор повернул тумблер питания).
Сама история указателей в Аде довольно интересна. Изначально, в версии Ада 83, были доступны только указатели на динамически созданные объекты (т.е. не было указателей на объявленные объекты и на подпрограммы). Также предлагалась явная операция освобождения объектов (Unchecked_Deallocation). Таким образом предотвращалось нарушение типизации и появление висящих указателей на более недоступные локальные объекты. Вместе с тем, оставалась возможность получить висящий указатель при некорректном использовании Unchecked_Deallocation.
Введение Unchecked_Deallocation было неизбежно, так как единственная альтернатива — требовать реализациям предоставлять сборщик мусора — не вписывается в областях вычислений в реальном времени и высокой надежности, где ожидалось широкое распространение языка. Философия Ады такова - любое небезопасное действие должно быть четко обозначено. В самом деле, если мы используем Unchecked_Deallocation, нам необходимо указать его в спецификаторах использования (with Ada.Unchecked_Deallocation;), а затем настроить на нужный тип. (Концепции спецификаторов использования и настраиваемых модулей будет рассмотрена в следующем разделе). Такой сравнительно утяжеленный синтаксис одновременно предотвращает безалаберное использование и облегчает чтение и сопровождение кода, четко выделяя опасные места.
Ада 95 расширяет версию Ада 83 и разрешает иметь указатели на объявленные объекты и на подпрограммы. Версия Ада 2005 идет немного дальше, облегчая передачу указателя на подпрограмму в качестве параметра. Как при этом удается сохранить безопасность мы и рассмотрим в этой главе.
Еще одно замечание до того, как мы углубимся в детали. Поскольку термин указатель часто несет дополнительный низкоуровневый подтекст, в Аде используется термин ссылочный тип. Таким образом, делается акцент на том, что значения ссылочного типа позволяют нам ссылаться на другие объекты некоторого заранее известного типа (и являются своего рода динамическими именами этих объектов) и не должны восприниматься просто как машинный адрес. В самом деле, на уровне реализации представление этих значений могут отличаться от физических указателей.
Ссылочные типы и строгая типизация
Используя возможности языка Ада 2005 мы можем объявить переменную Ref, чьи значения предоставляют доступ к объектам типа T:
Ref : access T;
Если мы не укажем начальное значение, то будет использовано специальное значение null. Ref может ссылаться на обычную переменную типа T (которая, однако, должна быть помечена как aliased):
Obj : aliased T;
...
Ref := Obj'Access;
Это аналогично следующей записи на языке C:
t* ref;
t obj;
ref = &obj;
Тип T в свою очередь может быть определен как:
type Date is record
Day : Integer range 1 .. 31;
Month : Integer range 1 .. 12;
Year : Integer;
end record;
и далее мы можем написать:
Birthday: aliased Date :=(Day => 10, Month => 12, Year => 1815);
AD : access Date := Birthday'Access;
Можно обратиться к отдельным компонентам даты, используя AD:
The_Day : Integer := AD.Day;
Переменная AD также может ссылаться на динамически созданный объект, расположенный «в куче» (которая в Аде носит названия пул /storage pool/).
AD := new Date'(Day => 27, Month => 11, Year => 1852);
(Здесь использованы даты рождения и смерти графини Ады Лавлейс, в честь которой назван язык).
Типичным случаем использования ссылочных типов является связный список. Например, мы можем определить:
type Cell is record
Next : access Cell;
Value : Integer;
end record;
и затем мы сможем создать цепочку объектов типа Cell, связанных в список.
Часто удобно иметь именованный ссылочный тип:
type Date_Ptr is access all Date;
Здесь слово all означает, что этот тип служит для работы как с динамическими созданными объектами, так и с объявленными переменными, расположенными в стеке (которые помечены aliased).
Сама пометка aliased — весьма полезная «страховка». Она предупреждает программиста, что к объекту можно обратиться через ссылку (что помогает при беглом ознакомлении). Кроме того — это сигнал компилятору, что при оптимизации кода нужно учитывать возможность косвенного обращения к объекту через ссылочные значения.
Важным моментом является то, что ссылочный тип всегда связан с типом объектов, на которые он ссылается. Таким образом, всегда выполняется контроль типов при присваивании, передаче параметров и во всех других вариантах использования. Кроме того, ссылочное значение всегда имеет только легальные значения (в числе которых и null). При исполнении программы, при попытке доступа к объекту по ссылке Date_Ptr выполняется проверка, что значение не равно null и возбуждается исключение Constraint_Error, если это не так.
Мы можем явно задать, что ссылочное значение всегда будет отличным от null, записав определение переменной следующим образом:
WD : not null access Date := Wedding_Day'Access;
Естественно, сразу нужно указать начальное значение отличное от null. Использование этой возможности позволяет гарантировать, что упомянутое выше исключение никогда не произойдет.
Наконец, следует отметить, что ссылочное значение может указывать на компоненту составного типа, при условии, что сама компонента помечена как aliased. Например:
A : array (1..10) of aliased Integer := (1,2,3,4,5,6,7,8,9,10);
P : access Integer := A (4)'Access;
Но мы не можем использовать арифметику над ссылочным значением P, такую как P++ или P+1, чтобы обратиться к A (5), как это возможно в C. (На самом деле в Аде нет даже такого оператора, как ++.) Хорошо известно, что подобные действия в C легко приводят к ошибкам, т. к. ничто не мешает нам выйти за границы массива.
Ссылочные типы и контроль доступности
Только что мы рассмотрели, как строгая типизация в языке предотвращает доступ по ссылочному значению к объекту неправильного типа. Следующее требование — убедиться, что объект не прекратит свое существование, пока какой-либо объект ссылочного типа указывает на него. Для случая с определениями объектов это достигается механизмом контроля доступности (accessibility). Рассмотрим следующий код:
package Data is
type Int_Ref is access all Integer;
Ref1 : Int_Ref;
end Data;
with Data; use Data;
procedure P is
K : aliased Integer;
Ref2 : Int_Ref;
begin
Ref2 := K'Access; -- Illegal
Ref1 := Ref2;
end P;
Хотя это довольно искусственный пример, он в сжатом объеме демонстрирует основные интересные нам места. Пакет Data предоставляет ссылочный тип Int_Ref и объект Ref1 этого типа. Процедура P объявляет локальную переменную K и локальную ссылочную переменную Ref2 также типа Int_Ref. Затем делается попытка присвоить переменной Ref2 ссылку на K. Это запрещено. В самом присвоении Ref2 этого значения проблемы нет потому, что оба объекта (K и Ref2) прекратят свое существование одновременно при завершении вызова процедуры. Настоящая опасность в том, что в дальнейшем мы можем скопировать значение Ref2 в глобальную переменную, в данном случае Ref1, которая будет хранить ссылку на K даже после того, как K перестанет существовать.
Главное правило таково, что время жизни объекта, на который мы получаем ссылку (такого как K) должно быть как минимум такое же, как время жизни указанного ссылочного типа (в нашем случае Int_Ref). В нашем примере это не выполняется, поэтому попытка получить значение, ссылающееся на K незаконна.
Соответствующие правила сформулированы в терминах уровней доступности (accessibility levels), обозначающих вложенность конструкций, охватывающих данное определение. Таким образом, обозначенные правила опираются в основном на статические конструкции языка, проверяются компилятором в момент компиляции и не влекут дополнительных издержек в момент исполнения. Однако правила для параметров подпрограмм, имеющих анонимные ссылочные типы, имеют динамическую природу и проверяются в момент исполнения. Это плата за дополнительную гибкость, которую другим способом достичь не удается.
В столь коротком обзоре языка как этот, у нас нет возможности еще больше углубиться в детали. Достаточно сказать, что правила контроля доступности предотвращают висящие ссылки на объявляемые объекты, которые являются источником множества коварных и трудно устранимых ошибок в других «дырявых» языках.
Ссылки на подпрограммы
В Аде разрешены ссылки на процедуры и функции. Работают они аналогично ссылкам на объекты. Соответственно для них также выполняются проверки строгой типизации и контроль доступности. Например, используя возможности Ады 2005, мы можем написать:
A_Func : access function (X : Float) return Float;
После этого объект A_Func может хранить ссылки только на функции с параметром типа Float и возвращающие Float (такова, к примеру, предопределенная функция Sqrt).
И так мы можем написать:
A_Func := Sqrt'Access;
...
X : Float := A_Func (4.0); -- косвенный вызов
Это приведет к вызову функции Sqrt с аргументом 4.0, а результат, видимо, будет 2.0.
Язык тщательно следит за совпадением параметров, поэтому мы не можем вызвать функцию с неверным количеством/типом параметров. Это же верно и для результата функции. Список параметров и результат функции составляют отдельное понятие, техническое название которого — профиль функции.
Теперь рассмотрим предопределенную функцию вычисления арктангенса Arctan. Она имеет два параметра и возвращает угол θ (в радианах) такой, что tan θ = Y/X.
function Arctan (X : Float; Y : Float) return Float;
Если мы напишем:
A_Func := Arctan'Access; -- Ошибка
Z := A_Func (A); -- косвенный вызов предотвращен
Компилятор отвергнет такой код потому, что профиль функции Arctan не совпадает с профилем A_Func. Это как раз то, что нужно, иначе функция Arctan достала бы два аргумента из стека, в то время как косвенный вызов по ссылке A_Func положит в стек лишь один аргумент (Это, на самом деле, зависит от ABI аппаратной платформы, не факт, что floats будут передаваться через стек). Результат получился бы совершенно бессмысленным.
Соответствующие проверки выполняются независимо от пересечения границ модулей компиляции (модули компиляции — программные единицы, компилируемые раздельно, мы остановимся на этом в главе «Безопасная архитектура»). Аналогичные проверки в С не работают в этом случае, что часто приводит к серьезным проблемам.
Более сложный случай возникает, когда одна подпрограмма передается в другую как параметр. Допустим, у нас есть функция для решения уравнения Fn(X) = 0, причем функция Fn сама передается как параметр:
function Solve (Trial : Float;
Accuracy : Float;
Fn : access function (X : Float) return Float)
return Float;
Параметр Trial — это первое приближение, параметр Accuracy — требуемая точность, третий параметр Fn — функция из уравнения.
К примеру, мы инвестировали 1000 долларов сегодня и 500 долларов в течении года, какова должна быть процентная ставка, чтобы конечная чистая стоимость за два года была в точности 2000 долларов? Задавая процентную ставку как X, мы можем вычислить конечную чистую стоимость по формуле:
Nfv (X) = 1000 * (1 + X/100)2 + 500 * (1 + X/100)
Чтобы ответить на вопрос, определим функцию, которая вернет 0.0 когда стоимость достигнет 2000.0:
function Nvf_2000 (X : Float) return Float is
Factor : constant Float := 1.0 + X / 100.0;
begin
return 1000.0 * Factor ** 2 + 500.0 * Factor - 2000.0;
end Nvf_2000;
Затем можно сделать:
Answer : Float := Solve
(Trial => 5.0, Accuracy => 0.01, Fn => Nvf_2000'Access);
Мы предлагаем решить уравнение, указав первое приближение в 5%, точность 0.01 и целевую функцию Nvf_2000. Предлагаем читателю найти решение, наше значение вы найдете в конце главы. (Термин «конечная чистая стоимость» хорошо известен финансовым специалистам.)
Мы хотели бы отметить, что в Аде будут проверяться типы параметров функции, даже когда она сама передается как параметр, благодаря тому, что профиль функции может иметь произвольную глубину вложенности. Многие языки имеют ограничение в один уровень.
Заметим, что параметр Fn имеет анонимный тип. Аналогично ссылкам на объекты, мы можем определить именованный ссылочный тип для подпрограмм. И можем заставить ссылочный тип хранить только не null значения. Т.е. можно написать:
A_Func : not null access function (X : Float) return Float
:= Sqrt'Access;
Плюс тут в том, что мы явно гарантируем, что A_Func не равен null в любом месте, где бы мы его не использовали.
В том случае, если Вы считаете использование произвольной функции (в данном случае Sqrt), как начального значения не равного null безвкусицей, можно определить специальную функцию для значения по умолчанию:
function Default (X : Float) return Float is
begin
Put ("Value not set");
return 0.0;
end Default;
...
A_Func : not null access function (X : Float) return Float
:= Default'Access;
Аналогично, нам необходимо добавить not null в профиль функции Solve:
function Solve
(Trial : Float;
Accuracy : Float;
Fn : not null access function (X : Float) return Float)
return Float;
Это гарантирует что аргумент Fn никогда не будет null.
Вложенные подпрограммы в качестве параметров
Как мы упоминали ранее, контроль доступности также работает и для ссылок на подпрограммы. Допустим функция Solve определена в пакете и использует именованный ссылочный тип для параметра Fn:
package Algorithms is
type A_Function is
not null access function (X : Float) return Float;
function Solve
(Trial : Float; Accuracy : Float; Fn : A_Function)
return Float;
...
end Algorithms;
Допустим мы хотим обобщить пример с вычислением чистой стоимости, чтобы иметь возможность передавать целевое значение как параметр. Попробуем так:
with Algorithms; use Algorithms;
function Compute_Iterest (Target : Float) return Float is
function Nfv_T (X : Float) return Float is
Factor : constant Float := 1.0 + X/100.0;
begin
return 1000.0*Factor**2 + 500.0*Factor - Target;
end Nfv_T;
begin
return Solve (Trial => 5.0, Accuracy => 0.01,
Fn => Nfv_T'Access); -- Illegal
end Compute_Iterest;
Однако Nfv_T'Access нельзя использовать как значение параметра Fn, потому, что это нарушает правила контроля доступности. Проблема в том, что функция Nfv_T находится на более глубоком уровне вложенности, чем тип A_Function. (Так и должно быть, поскольку нам необходим доступ к параметру Target.) Если бы подобное было разрешено, мы могли бы присвоить это значение какой-нибудь глобальной переменной типа A_Function. После выхода из функции Compute_Interest функция Nfv_T будет недоступна для использования, но глобальная переменная все еще будет хранить ссылку на нее. Например:
Dodgy_Fn : A_Function := Default'Access; -- Глобальный объект
function Compute_Iterest (Target : Float) return Float is
function Nfv_T (X : Float) return Float is
...
end Nfv_T;
begin
Dodgy_Fn := Nfv_T'Access; -- Ошибка
...
end Compute_Iterest;
После завершения вызова мы делаем:
Answer := Dodgy_Fn (99.9); -- результат непредсказуем
Вызов Dodgy_Fn будет пытаться вызвать Nfv_T, но это невозможно, потому, что она локальна для Compute_Interest и будет пытаться обратиться к параметру Target, которого уже не существует. Если бы Ада не запрещала это делать, последствия были бы непредсказуемы. Заметьте, что при использовании анонимного типа для параметра Fn, мы могли бы передать вложенную функцию, как аргумент Solve, но тогда контроль доступности сработал бы при попытке присвоить это значение переменной Dodgy_Fn. Во время исполнения выполнилась бы проверка, что уровень вложенности Nfv_T больше, чем уровень вложенности типа A_Function и произошло бы возбуждение исключения Program_Error. Таким образом, правильным решением было бы определить:
package Algorithms is
function Solve
(Trial : Float;
Accuracy : Float;
Fn : not null access function (X : Float)
return Float)
return Float;
end Algorithms;
и оставить функцию Compute_Interest в первоначальном варианте (удалив комментарий Ошибка, конечно).
Может показаться, что проблема лежит в том, что функция Nfv_T вложена в Compute_Iterest. Мы могли бы сделать ее глобальной и проблемы с доступностью исчезли бы. Но для этого нам пришлось бы передавать значение Target через какую-нибудь переменную в пакете верхнего уровня, в стиле COMMON-блоков языка FORTRAN. Мы не можем добавить ее в список параметров функции, т. к. список параметров должен совпадать со списком для Fn. Но передавать данные через глобальные переменные фактически порочная практика. Она нарушает принцип сокрытия информации, принцип абстракции, а также плохо стыкуется с многозадачностью. Заметим, что практика использования вложенных функций, когда функция получает доступ к нелокальным переменным (таким как Target) часто называется «замыканием».
Такие замыкания, другими словами передача указателя на вложенную подпрограмму как параметр времени исполнения, используются в некоторых местах стандартной библиотеки Ады, например для перебора элементов какого-нибудь контейнера.
Использовать вложенные подпрограммы в таких случаях естественно, т. к. они нуждаются в нелокальных данных. Подобный подход затруднен в «плоских» языках программирования, таких как C, C++ и Java. В некоторых случаях можно использовать механизм наследования, но он менее ясен, что может повлечь проблемы при сопровождении кода.
Наконец, может потребоваться комбинировать алгоритмы, используя вложенность. Так, наш пакет Algorithms может содержать другие полезные вещи:
package Algorithms is
function Solve
(Trial : Float;
Accuracy : Float;
Fn : not null access function (X : Float)
return Float)
return Float;
function Integrate
(Lo, Hi : Float;
Accuracy : Float;
Fn : not null access function (X : Float)
return Float)
return Float;
type Vector is array (Positive range <>) of Float;
procedure Minimize
(V : in out Vector; Accuracy : Float;
Fn : not null access function (V : Vector)
return Float)
return Float;
end Algorithms;
Функция Integrate подобна Solve. Она вычисляет определённый интеграл от данной функции на заданном интервале. Процедура Minimize несколько отличается. Она находит те значения элементов массива, на которых данная функция достигает минимума. Возможна ситуация, когда целевая функция минимизации является интегралом и использует V. Кому-то это может показаться притянутым за уши, но автор потратил первые несколько лет своей карьеры программиста, работая над подобными вещами в химической индустрии.
Код может иметь вид:
with Algorithms; use Algorithms;
procedure Do_It is
function Cost (V: Vector) return Float is
function F (X : Float) return Float is
Result : Float;
begin
... -- Вычислим Result используя V и X
return Float;
end F;
begin
return Integrate (0.0, 1.0, 0.01, F'Access);
end Cost;
A : Vector (1 .. 10);
begin
... -- perhaps read in or set trial values for the vector A
Minimize (A, 0.01, Cost'Access);
... -- output final values of the vector A
end Do_It;
В Аде 2005 (и соответственно в Аде 2012) подобный подход срабатывает «на ура», как если бы вы делали это на Algol 60. В других языках подобное сделать трудно, либо требует использования небезопасных конструкций, которые могут привести к появлению висящих ссылок.
Дополнительные примеры использования ссылочных типов для подпрограмм можно найти в главе «Безопасная коммуникация».
И, наконец, искомая процентная ставка при которой 1000 долларов инвестиций с последующими 500 долларами за два года дадут 2000 чистой стоимости равна 18.6%. И это круто!