Привет, Хабр! Представляю вашему вниманию перевод статьи "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];
}

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

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

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

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

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

Но мы еще не закончили: это правило имеет единственное исключение, которое мы можем использовать в нашу пользу. Если арифметическая операция вычисляет значение указателя на адрес точно после конца массива, то все в порядке. (Это исключение необходимо для вычисления 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 и y были выделены друг за другом, причем y имеет больший адрес. Тогда x_ptr указывает на начало y! Тогда условие истинно и присваивание происходит. При этом тут нет UB из-за выхода указателя за границы.

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

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

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

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

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

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

int foo(int *restrict x, int *restrict y) {
    *x = 42;
    if (x == y) {
        *y = 23;
    }
    return *x;
}

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

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

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

Простая модель указателей

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

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

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

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

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

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

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

Наша модель разваливается на куски

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

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

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

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

От указателей к байтам

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

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

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

Например, PtrFragment(ptr, 0) представляет собой первый байт указателя ptr. Таким образом, memcpy может "разбить" указатель на отдельные байты, представляющие этот указатель в памяти, и копировать их по отдельности. На 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,
}

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

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

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

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

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

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

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

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

Заключение

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