Хабрахабр

[Перевод] Указатели сложны, или Что хранится в байте?

Представляю вашему вниманию перевод статьи "Pointers Are Complicated, or: What's in a Byte?" авторства Ralf Jung. Привет, Хабр!

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

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

Я надеюсь, что прочитав этот пост, вы согласитесь со мной относительно обоих утверждений.

Давайте рассмотрим следующий пример: (я использую C++ здесь, так как писать небезопасный код в C++ проще, чем в Rust, и небезопасный код — это как раз то место, где и появляются проблемы. В чем проблема с "указатели — это обычные числа"? Небезопасный Rust и C имеют все те же проблемы, что и C++).

int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; int i = /* какие-то вычисления без побочных эффектов */; auto x_ptr = &x[i]; *x_ptr = 23; return y[0];
}

Обоснование такой оптимизации — изменение x_ptr, которое указывает на x, не может изменить y. Оптимизация последнего чтения y[0] с возвращением всегда 42 очень выгодна.

Так как &x[i] — это то же самое, что и x+i, мы записываем 23 в &y[0]. Однако, имея дело с языками низкого уровня, такими как C++, мы можем нарушить это предположение, присвоив i значение y-x.

Чтобы разрешить это, стандарт говорит, что наш код имеет UB. Конечно, это не мешает C++ компиляторам делать такие оптимизации.

Наша программа нарушает это правило: x[i] выходит за границы x, поэтому это является UB. Во-первых, не разрешается выполнять арифметические операции над указателями (как в случае с &x[i]), если в этом случае указатель выходит за любую из границ массива. Иными словами, даже вычисление значения x_ptr является UB, так что мы даже не доходим до того места, где мы хотим использовать этот указатель.

Однако мы могли бы написать i = ((size_t)y — (size_t)x)/sizeof(int), чтобы обойти это ограничение.) (Оказывается, i = y-x также является UB, так как разрешается вычитать только указатели, указывающие в место одного выделения памяти.

Если арифметическая операция вычисляет значение указателя на адрес точно после конца массива, то все в порядке. Но мы еще не закончили: это правило имеет единственное исключение, которое мы можем использовать в нашу пользу. (Это исключение необходимо для вычисления vec.end() для самых обычных циклов в C++98.)

Давайте немного изменим пример:

int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; auto x_ptr = x+8; // элемент после конца if (x_ptr == &y[0]) *x_ptr = 23; return y[0];
}

Тогда x_ptr указывает на начало y! А теперь представьте, что x и y были выделены друг за другом, причем y имеет больший адрес. При этом тут нет UB из-за выхода указателя за границы. Тогда условие истинно и присваивание происходит.

Однако стандарт C++ имеет другой туз в рукаве, чтобы помочь создателям компиляторов: на самом деле он не позволяет нам использовать x_ptr. Кажется, что это не позволит провести оптимизацию. Он не указывает на конкретный элемент другого объекта, даже если они имеют одинаковый адрес. Согласно тому, что говорится в стандарте про прибавление чисел к указателям, x_ptr указывает на адрес после последнего элемента массива. (По крайней мере это распространенная интерпретация стандарта, на основе которой LLVM оптимизирует этот код.)

Если мы заменим *x_ptr = 23 строкой *&y[0] = 0, мы изменим значение программы, даже несмотря на то, что два указателя проверялись на равенство. И даже несмотря на то, что x_ptr и &y[0] указывают на один адрес, это не делает их одинаковым указателем, то есть они не могут быть использованы взаимозаменяемо: &y[0] указывает на первый элемент y; x_ptr указывает на адрес после x.

Это стоит повторить:

То, что два указателя указывают на один адрес, не значит то, что они равны и могут быть использованы взаимозаменяемо.

На самом деле, это до сих пор вызывает различия в программах, скомпилированных с LLVM и GCC. Да, эта разница трудноуловима.

Другой пример — ключевое слово restrict в C, которое может быть использовано для выражения того, что указатели не перекрываются (не равны): Также заметьте, что это правило "один после" — не единственное место в C/C++, где мы можем наблюдать такой эффект.

int foo(int *restrict x, int *restrict y) return *x;
} int test() { int x; return foo(&x, &x);
}

Заменив *y на *x в foo, мы изменим значение программы, и она больше не будет вызывать UB. Вызов test() вызывает UB, так как два доступа к памяти в foo не должны происходить по одному адресу. Еще раз: несмотря на то, что x и y имеют один адрес, их нельзя использовать взаимозаменяемо.

Указатели — это определенно не простые числа.

Я не знаю полный ответ. Так что такое указатель? На самом деле, это открытая область для исследований.

Безусловно, на настоящем комьютере указатели являются числами. Один важный момент: здесь мы рассматриваем абстрактную модель указателей. Если бы мы написали вышеприведенные программы на ассемблере, то там не было бы ни UB, ни оптимизаций. Но настоящий компьютер не проводит те оптимизации, которые делают современные компиляторы C++. Когда требуется формально описать, что программист может и не может делать в этих языках, модель указателей как чисел разбивается вдребезги, так что нам нужно найти что-то еще. C++ и Rust применяют более "высокоуровневый" подход к памяти и указателям, ограничивая программиста в угоду компилятору. Это другой пример использования "виртуальной машины", отличающейся от реального компьютера в целях спецификации — идее, о которой я писал раньше.

Если написать это на Rust: Вот простое предложение (на самом деле эта модель указателей используется в CompCert и моей работе RustBelt, а также способ, согласно которому интерпретатор miri реализует указатели): указатель — это пара какого-то ID, однозначно определяющего область памяти (allocation), и смещение относительно этой области.

struct Pointer { alloc_id: usize, offset: isize,
}

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

Однако, LLVM применяет их на уровне областей.) (Как мы могли видеть, стандарт C++ применяет эти правила к массивам, а не областям памяти.

Мы всегда помним, к какой области памяти относится указатель, поэтому мы можем отличить указатель "один после" одной области памяти от указателя на начало другой области. Оказывается (и miri показывает то же самое), что эта модель может хорошо послужить нам. Таким образом miri может обнаружить, что наш второй пример (с &x[8]) имеет UB.

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

Однако, это хорошо работает для интерпретатора. Я должен пояснить: это не хорошее решение, если речь заходит об определении семантики языка. Каждая область памяти идентифицируется (скрытым) ID. Это самый простой подход, и мы выбрали его, потому что непонятно, как это можно сделать иначе (кроме как не поддерживать такие приведения вовсе — но с их поддержкой miri может запускать больше программ): в нашей абстрактной машине нет единого "адресного пространства", в котором располагались бы все выделенные области памяти, а все указатели были сопоставлены с конкретными различными числами. Его цель — обсудить необходимость такой модели. Теперь мы можем начинать добавлять в нашу модель дополнительные данные вроде базового адреса для каждой области памяти, и каким-то образом использовать это для приведения числа обратно к указателю… и на этом моменте процесс становится действительно очень сложным, и, в любом случае, обсуждение этой модели не является целью написания поста. Если вы заинтересованы, я рекомендую вам прочитать этот документ, который подробнее рассматривает вышеприведенную идею добавления базового адреса.

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

Именно поэтому указатели также не являются и простыми.

Однако это значит, что простая операция вроде чтения байта из памяти не может просто вернуть u8. Я надеюсь, я привел достаточно убедительный довод, что числа — не единственный тип данных, которые нужно учитывать, если мы хотим формально описать низкоуровневые языки вроде C++ или (небезопасную часть) Rust. А что, если этот байт является частью указателя? Представьте себе, что мы реализуем memcpy, читая по очереди каждый байт источника в какую-то локальную переменную v, а затем сохраняем это значение в целевом месте. Нам нужно сказать, чему равно значение v, поэтому нам придется как-то ответить на этот вопрос. Если указатель — это пара ID области памяти и смещения, то каков будет его первый байт? Мы просто предположим, что существует некий абстрактный тип Ponter.) (И это совершенно иная проблема, чем проблема с умножением, которая была в предыдущей секции.

256 (прим.: здесь и далее 0 включается, 256 — нет). Мы не можем представить байт указателя как значение диапазона 0.. Нам придется исправить это, а для этого придется расширить наше понятие "байта" для представления этого дополнительного состояния. В целом, если мы используем наивную модель представления памяти, дополнительная "скрытая" часть указателя (та, что делает его больше чем просто числом) будет потеряна, когда указатель будет записан в память и заново считан из нее. 256 ("сырые биты"), либо n-ый байт какого-то абстрактного указателя. Таким образом, байт теперь либо значение диапазона 0.. Если бы нам пришлось реализовать нашу модель памяти на Rust, это могло бы выглядеть так:

enum ByteV1 { Bits(u8), PtrFragment(Pointer, u8),
}

Таким образом, memcpy может "разбить" указатель на отдельные байты, представляющие этот указатель в памяти, и копировать их по отдельности. Например, PtrFragment(ptr, 0) представляет собой первый байт указателя ptr. На 32-битной архитектуре полное представление ptr будет содержать 4 байта:

[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]

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

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

enum Byte { Bits(u8), PtrFragment(Pointer, u8), Uninit,
}

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

Заметьте, что LLVM также имеет значение undef, которое используется для неинициализированной памяти и работает несколько иначе. Это очень похоже на правила LLVM по отношению к специальному значению poison. Однако, компиляция нашего Uninit в undef корректна (undef в каком-то смысле "слабее"), и есть предложения убрать undef из LLVM и использовать вместо него poison.

Почему бы не выбрать какое-нибудь произвольное b: u8 для каждого нового байта, и затем использовать Bits(b) в качестве изначального значения? Вы можете удивиться, почему у нас вообще есть специальное значение Uninit. Однако, прежде всего, все компиляторы пришли к подходу с использованием специального значения для неинициализированной памяти. Это действительно является одним из вариантов. Ключевой момент здесь: всегда можно безопасно заменить Uninit любым другим значением: любая операция, получающая это значение, в любом случае приводит к UB. Не следовать этому подходу значит не только вызвать проблемы с компиляцией через LLVM, но и пересмотреть все оптимизации и убедиться, что они работают корректно с этой измененной моделью.

Например, этот код на C проще оптимизировать с Uninit:

int test() { int x; if (condA()) x = 1; // Много трудного для анализа кода, который точно приведет к выходу из функции, если condA() // не истинно, но этот код не изменяет x. use(x); // оптимизируем x = 1.
}

Без Uninit x равно либо "какому-то произвольному битовому паттерну", либо 1, и проведение той же оптимизации уже сложнее объяснить. С Uninit мы можем с легкостью сказать, что x имеет либо значение Uninit, либо значение 1, и раз замена Uninit на 1 работает, оптимизация легко объясняется.

Uninit позволяет избегать этой мороки с ненужными доказательствами.) (Мы можем возразить, что мы можем поменять местами операции, когда делаем недетерминированный выбор, но тогда нам надо будет доказать, что трудный для анализа код не использует никаким образом x.

Такие интерпретаторы имеют проблемы с операциями типа "просто выбери любое из этих значений" (т. Наконец, Uninit является лучшим выбором для интерпретаторов вроде miri. недетерминированными операциями), так как они стремятся пройти все возможные пути выполнения программы, а это значит, что им необходимо попробовать все возможные значения. е. Использование Uninit вместо произвольного битового паттерна значит, что miri может после одного выполнения программы сказать вам, использует ли ваша программа неинициализированные значения некорректно.

256. Мы увидели, что в языках вроде C++ и Rust (в отличие от реальных компьютеров) указатели могут быть различны, даже если они указывают на один адрес, и что байт — это нечто большее, чем просто число из диапазона 0.. Поэтому если в 1978 году язык C можно было "портативным ассемблером", то сейчас это невероятно ошибочное утверждение.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть