Псевдонимы (вычисления)
В вычислениях псевдонимы можно получить через описывают ситуацию, в которой доступ к ячейке данных в памяти разные символические имена в программе. Таким образом, изменение данных через одно имя неявно изменяет значения, связанные со всеми псевдонимами, чего программист может не ожидать. В результате псевдонимы особенно затрудняют понимание, анализ и оптимизацию программ. Анализаторы псевдонимов предназначены для получения и вычисления полезной информации для понимания псевдонимов в программах.
Примеры
[ редактировать ]Переполнение буфера
[ редактировать ]Например, большинство реализаций языка программирования C не выполняют проверку границ массива . Затем можно использовать реализацию языка программирования компилятором и соглашения о языке ассемблера компьютерной архитектуры для достижения эффектов псевдонимов путем записи за пределы массива (тип переполнения буфера ). Это вызывает неопределенное поведение в соответствии со спецификацией языка C; однако многие реализации C будут демонстрировать описанные здесь эффекты наложения псевдонимов.
создается массив Если в стеке с переменной, расположенной в памяти непосредственно рядом с этим массивом , можно выполнить индексацию вне массива и напрямую изменить переменную, изменив соответствующий элемент массива. Например, если есть int массив размером 2 (для этого примера назовем его arr), рядом с другим int переменная (назовите ее i), arr[2] (т. е. третий элемент) будет иметь псевдоним i если они соседствуют в памяти.
# include <stdio.h>
int main()
{
int arr[2] = { 1, 2 };
int i=10;
/* Write beyond the end of arr. Undefined behaviour in standard C, will write to i in some implementations. */
arr[2] = 20;
printf("element 0: %d \t", arr[0]); // outputs 1
printf("element 1: %d \t", arr[1]); // outputs 2
printf("element 2: %d \t", arr[2]); // outputs 20, if aliasing occurred
printf("i: %d \t\t", i); // might also output 20, not 10, because of aliasing, but the compiler might have i stored in a register and print 10
/* arr size is still 2. */
printf("arr size: %lu \n", (long) (sizeof(arr) / sizeof(int)));
}
Это возможно в некоторых реализациях C, поскольку массив представляет собой блок непрерывной памяти, а ссылки на элементы массива просто смещаются от адреса начала этого блока, умноженного на размер одного элемента. Поскольку в C нет проверки границ, возможна индексация и адресация за пределами массива. Обратите внимание, что вышеупомянутое поведение псевдонимов является неопределенным поведением . Некоторые реализации могут оставлять пространство между массивами и переменными в стеке, например, для выравнивания переменных по областям памяти, кратным собственному размеру слова архитектуры . Стандарт C обычно не определяет, как данные должны располагаться в памяти. (ИСО/МЭК 9899:1999, раздел 6.2.6.1).
Компилятор не будет ошибкой пропускать эффекты псевдонимов для обращений, выходящих за пределы массива.
Псевдонимы указателей
[ редактировать ]Другая разновидность псевдонимов может встречаться в любом языке, который может ссылаться на одно место в памяти более чем одним именем (например, с помощью указателей ). Это обычная проблема с функциями, которые принимают аргументы-указатели, и их устойчивость (или ее отсутствие) к псевдонимам должна быть тщательно документирована, особенно для функций, которые выполняют сложные манипуляции с переданными им областями памяти.
Указанный псевдоним
[ редактировать ]В некоторых случаях может быть желательным контролируемое поведение псевдонимов (то есть заданное поведение псевдонимов, в отличие от того, которое обеспечивается расположением памяти в C). Это обычная практика в Фортране . Язык Perl программирования в некоторых конструкциях определяет поведение псевдонимов, например в foreach петли. Это позволяет напрямую изменять определенные структуры данных с меньшим количеством кода. Например,
my @array = (1, 2, 3);
foreach my $element (@array) {
# Increment $element, thus automatically
# modifying @array, since $element is ''aliased''
# to each of @array's elements in turn.
$element++;
}
print "@array \n";
в результате выведет «2 3 4». Если кто-то хочет обойти эффекты псевдонимов, можно скопировать содержимое индексной переменной в другую и изменить копию.
Конфликты с оптимизацией
[ редактировать ]Оптимизаторам часто приходится делать консервативные предположения о переменных, когда возможно наложение псевдонимов. Например, зная значение переменной (например, x равен 5) обычно допускает определенные оптимизации (например, постоянное распространение ). Однако компилятор не может использовать эту информацию после присвоения другой переменной (например, в C, *y = 10) потому что это может быть так *y это псевдоним x. Это может произойти после такого задания, как y = &x. В результате этого поручения *y, значение x также будет изменено, поэтому распространение информации, которая x равно 5 к утверждениям, следующим *y = 10 было бы потенциально неправильно (если *y действительно это псевдоним x). Однако, если есть информация об указателях, процесс распространения констант может сделать запрос типа: can x быть псевдонимом *y? Тогда, если ответ отрицательный, x = 5 можно безопасно размножать.
Еще одна оптимизация, на которую влияет псевдонимы, — это изменение порядка кода. Если компилятор решит, что x не имеет псевдонимов *y, затем код, который использует или изменяет значение x можно переместить перед заданием *y = 10, если это улучшит планирование или позволит дополнительную оптимизацию цикла выполнить .
Чтобы обеспечить такую оптимизацию предсказуемым образом, стандарт ISO для языка программирования C (включая его новую редакцию C99 , см. раздел 6.5, параграф 7) определяет, что незаконно (за некоторыми исключениями) получать доступ к одной и той же ячейке памяти с помощью указателей разные типы. Поэтому компилятор может предположить, что такие указатели не являются псевдонимами. Это правило, известное как правило строгого псевдонимов , иногда позволяет добиться впечатляющего увеличения производительности. [1] но известно, что он нарушает некоторый в остальном действительный код. Некоторые программные проекты намеренно нарушают эту часть стандарта C99. Например, Python 2.x сделал это для реализации подсчета ссылок , [2] и потребовались изменения в базовых структурах объектов в Python 3, чтобы включить эту оптимизацию. Ядро Linux делает это, потому что строгое использование псевдонимов вызывает проблемы с оптимизацией встроенного кода. [3] В таких случаях при компиляции с помощью gcc опция -fno-strict-aliasing вызывается для предотвращения нежелательных оптимизаций, которые могут привести к появлению неожиданного кода.
Аппаратное псевдонимирование
[ редактировать ]Термин «алиасинг» также используется для описания ситуации, когда из-за выбора конструкции оборудования или сбоя оборудования один или несколько доступных битов адреса не используются в процессе выбора памяти. [4] Это может быть конструктивным решением, если доступно больше адресных битов, чем необходимо для поддержки установленных устройств памяти. В случае сбоя один или несколько адресных битов могут быть закорочены вместе или принудительно заземлены ( логический 0) или напряжение питания (логическая 1).
- Пример
В этом примере предполагается, что память имеет 8 ячеек, требующих только 3 адресных строки (или бита , поскольку 2 3 = 8). Биты адреса (с именами от A2 до A0) декодируются для выбора уникальных ячеек памяти следующим образом, в стандартном режиме двоичного счетчика :
| А2 | А1 | А0 | Местоположение памяти |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
| 1 | 0 | 0 | 4 |
| 1 | 0 | 1 | 5 |
| 1 | 1 | 0 | 6 |
| 1 | 1 | 1 | 7 |
В таблице выше каждая из 8 уникальных комбинаций битов адреса выбирает другую ячейку памяти. Однако, если один бит адреса (скажем, A2) будет закорочен на землю, таблица будет изменена следующим образом:
| А2 | А1 | А0 | Местоположение памяти |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
В этом случае, когда A2 всегда равно нулю, первые четыре ячейки памяти дублируются и снова отображаются как вторые четыре. Ячейки памяти с 4 по 7 стали недоступны.
Если бы это изменение произошло с другим битом адреса, результаты декодирования были бы другими, но в целом эффект был бы тот же: потеря одного бита адреса сокращает доступное пространство памяти вдвое, что приводит к дублированию (алиасингу) бита адреса. оставшееся пространство.
См. также
[ редактировать ]- Сглаживание
- Псевдонимы для использования слова применительно к обработке сигналов, включая компьютерную графику.
Ссылки
[ редактировать ]- ^ Майк Эктон (1 июня 2006 г.). «Понимание строгого псевдонимов» .
- ^ Нил Шеменауэр (17 июля 2003 г.). «Строгое псевдонимы ANSI и Python» .
- ^ Линус Торвальдс (26 февраля 2003 г.). «Re: Неверная компиляция без -fno-strict-aliasing» .
- ^ Майкл Барр (27 июля 2012 г.). «Программное тестирование памяти» .
Внешние ссылки
[ редактировать ]- Понимание строгого псевдонимов – статья Майка Эктона
- Псевдонимы, приведение указателей и gcc 3.3 – информационная статья в списке рассылки NetBSD
- Анализ псевдонимов на основе типов в C++ — Информационная статья об анализе псевдонимов на основе типов в C++.
- Понимание строгого псевдонимов C/C++ — статья о строгом псевдониме, взятая из вики разработчика boost.