Стефан Шульце Фрилингхаус

24 Июл 2018

Теги:

#Cpp #Knowledge

Указатели в C абстрактнее, чем может показаться

24 Июл 2018

Автор: Стефан Шульце Фрилингхаус

Когда на пути встаёт компилятор
Разгадка - в отчёте об ошибке #260?
Окончательная разгадка - в операторах отношения?
Формат хранения
Различные объекты массивов
Резюме
Дополнение. Указатели на позицию за последним элементом массива

Указатель ссылается на ячейку памяти, а разыменовать указатель - значит считать значение указываемой ячейки. Значением самого указателя является адрес ячейки памяти. Стандарт языка C не оговаривает форму представления адресов памяти. Это очень важное замечание, поскольку разные архитектуры могут использовать разные модели адресации. Большинство современных архитектур использует линейное адресное пространство или аналогичное ему. Однако даже этот вопрос не оговаривается строго, поскольку адреса могут быть физическими или виртуальными. В некоторых архитектурах используется и вовсе нечисловое представление. Так, Symbolics Lisp Machine оперирует кортежами вида (object, offset) в качестве адресов.

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

#include <stdio.h>

int main(void) {
    int a, b;
    int *p = &a;
    int *q = &b + 1;
    printf("%p %p %d\n", (void *)p, (void *)q, p == q);
    return 0;
}

Если мы скомпилируем этот код GCC и уровнем оптимизации 1и запустим программу под Linux x86-64, она напечатает следующее:

0x7fff4a35b19c 0x7fff4a35b19c 0

Обратите внимание, что указатели p и q ссылаются на один и тот же адрес. Однако результат выражения p == q есть false, и это на первый взгляд кажется странным. Разве два указателя на один и тот же адрес не должны быть равны?

Вот как стандарт C определяет результат проверки двух указателей на равенство:

C11 § 6.5.9 пункт 6

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

Прежде всего возникает вопрос: что такое "объект"? Поскольку речь идёт о языке C, то очевидно, что здесь объекты не имеют ничего общего с объектами в языках ООП вроде C++. В стандарте C это понятие определяется не вполне строго:

C11 § 3.15

Объект - это область хранения данных в среде выполнения, содержимое которой может использоваться для представления значений

ПРИМЕЧАНИЕ При упоминании объект может рассматриваться как имеющий конкретный тип; см. 6.3.2.1.

Давайте разбираться. 16-битная целочисленная переменная - это набор данных в памяти, которые могут представлять 16-битные целочисленные значения. Следовательно, такая переменная является объектом. Будут ли два указателя равны, если один из них ссылается на первый байт данного целого числа, а второй - на второй байт этого же числа? Комитет по стандартизации языка, разумеется, имел в виду совсем не это. Но тут надо заметить, что на этот счёт у него нет чётких разъяснений, и мы вынуждены гадать, что же имелось в виду на самом деле.

Когда на пути встаёт компилятор

Вернёмся к нашему первому примеру. Указатель p получен из объекта a, а указатель q - из объекта b. Во втором случае применяется адресная арифметика, которая для операторов "плюс" и "минус" определена следующим образом:

C11 § 6.5.6 пункт 7

При использовании с этими операторами указатель на объект, не являющийся элементом массива, ведёт себя, как указатель на начало массива длиной в один элемент, тип которого соответствует типу исходного объекта.

Поскольку любой указатель на объект, не являющийся массивом, фактически становится указателем на массив длиной в один элемент, стандарт определяет адресную арифметику только для указателей на массивы - это уже пункт 8. Нас интересует следующая его часть:

C11 § 6.5.6 пункт 8

[...] если выражение P указывает на последний элемент объекта массива, выражение (P)+1 указывает на элемент объекта массива, следующий за последним [...] вычисление не приведет к переполнению

Из этого следует, что результатом выражения &b + 1 совершенно точно должен быть адрес, и, значит, p и q - это валидные указатели. Напомню, как определено равенство двух указателей в стандарте: "Два указателя равны тогда и только тогда, когда [...] один указатель ссылается на позицию за последним элементом массива, а другой - на начало другого массива, следующего сразу за первым в том же адресном пространстве" (C11 § 6.5.9 пункт 6). Именно это мы и наблюдаем в нашем примере. Указатель q ссылается на позицию за объектом b, за которым сразу же следует объект a, на который ссылается указатель p. Получается, в GCC баг? Это противоречие было описано в 2014 году как ошибка #61502, но разработчики GCC не считают его багом и поэтому исправлять его не собираются.

С похожей проблемой в 2016 году столкнулись программисты под Linux. Рассмотрим следующий код:

extern int _start[];
extern int _end[];

void foo(void) {
    for (int *i = _start; i != _end; ++i) { /* ... */ }
}

Символами _start и _end задают границы области памяти. Поскольку они вынесены во внешний файл, компилятор не знает, как на самом деле массивы расположены в памяти. По этой причине он должен здесь проявить осторожность и исходить из предположения, что они следуют в адресном пространстве друг за другом. Однако GCC компилирует условие цикла так, что оно всегда верно, из-за чего цикл становится бесконечным. Эта проблема описана вот в этом посте на LKML - там используется похожий фрагмент кода. Кажется, в данном случае авторы GCC все-таки учли замечания и изменили поведение компилятора. По крайней мере я не смог воспроизвести эту ошибку в версии GCC 7.3.1 под Linux x86_64.

Разгадка - в отчёте об ошибке #260?

Наш случай может прояснить отчёт об ошибке #260. Он больше касается неопределённых значений, однако в нём можно найти любопытный комментарий от комитета:

Реализации компиляторов [...] могут также различать указатели, полученные из разных объектов, даже если эти указатели имеют одинаковый набор битов.

Если понимать этот комментарий буквально, то тогда логично, что результат выражения p == q есть "ложь", так как p и q получены из разных объектов, никак не связанных между собой. Похоже, мы всё ближе подбираемся к истине - или нет? До сих пор мы имели дело с операторами равенства, а как насчёт операторов отношения?

Окончательная разгадка - в операторах отношения?

Определение операторов отношения <, <=, > и >= в контексте сравнения указателей содержит одну любопытную мысль:

C11 § 6.5.8 пункт 5

Результат сравнения двух указателей зависит от взаимного расположения указываемых объектов в адресном пространстве. Если два указателя на объектные типы ссылаются на один и тот же объект, либо оба ссылаются на позицию за последним элементом одного и того же массива, то такие указатели равны. Если указываемые объекты являются членами одного и того же составного объекта, то указатели на члены структуры, объявленные позже, больше указателей на члены, объявленные раньше, а указатели на элементы массива с большими индексами больше указателей на элементы того же массива с меньшими индексами. Все указатели на члены одного и того же объединения равны. Если выражение P указывает на элемент массива, а выражение Q - на последний элемент того же массива, то значение указателя-выражения Q+1 больше, чем значение выражения P. Во всех остальных случаях поведение не определено.

Согласно этому определению, результат сравнения указателей определён только в том случае, если указатели получены из одного и того же объекта. Покажем это на двух примерах.

int *p = malloc(64 * sizeof(int));
int *q = malloc(64 * sizeof(int));
if (p < q) // неопределённое поведение
    foo();

Здесь указатели p и q ссылаются на два разных объекта, которые не связаны между собой. Поэтому результат их сравнения не определён. А вот в следующем примере:

int *p = malloc(64 * sizeof(int));
int *q = p + 42;
if (p < q)
    foo();

указатели p и q ссылаются на один и тот же объект и, следовательно, связаны между собой. Значит, их можно сравнить — если только malloc не вернёт нулевой указатель.

Формат хранения

Пока что мы не проверяли стандарт относительно формата хранения объектов. Давайте сначала рассмотрим объекты составных типов. Составной тип - это или тип структуры, или тип массива. Первый является последовательно выделяемым непустым набором объектов членов. Единственная гарантия, которая у нас есть для членов структуры является то, что они выделяются последовательно в заданном порядке. Таким образом, компилятору не разрешается переупорядочивать члены. Однако ничего не говорится о пространстве между соседними членами. Здесь мы имеем то, что биты заполнения могут быть произвольно добавлены. Например, рассмотрим следующую структуру: struct { char a; int b; } x;. В большинстве современных архитектур между членами a и b вводятся несколько заполняющих бит согласно требований к выравниванию типа int. Таким образом, получение указателей от x.a и х.в и их сравнение на равенство приводит к неопределенному поведению, в то время как, например, их относительное сравнение &x.a < &x.b приводит к определенному поведению.

Для типов массива мы имеем то, что они описывают непустое множество смежных объектов. Важным моментом является то, что в отличие от членов структуры, члены массива размещаются в памяти последовательно. Таким образом, не только упорядочивание членов массива определено, но также соседние члены выделяются без промежутков между ними. Это дает нам возможность в конечном итоге выполнить вычисление указателя вполне определенным образом для членов массива.

Для всех других типов, то есть, несоставных типов имеем, что стандарт не определяет соответствующий формат хранения. Таким образом, для нашего вводного примера формат хранения переменных a и b не определен. Таким образом, вычисление указателей от переменных и их сравнение приводит к неопределенному поведению. GCC использует этот факт и статически относит выражение p == q к ложному. Для вводного примера имеем следующий вывод сборки при условии, если он компилируется с уровнем оптимизации 1:

.LC0:
        .string "%p %p %d\n"
main:
        sub     rsp, 24
        mov     ecx, 0
        lea     rdx, [rsp+12]
        mov     rsi, rdx
        mov     edi, OFFSET FLAT:.LC0
        mov     eax, 0
        call    printf
        mov     eax, 0
        add     rsp, 24
        ret

Выражение p == q компилируется в инструкцию в коде ассемблера mov ecx, 0.

Различные объекты массивов

Похоже, мы ближе и ближе подходим к истине ;-) Основная проблемная часть с которой мы пока столкнулись была в пункте § 6.5.9 главы 6, где явно разрешается сравнивать два объекта из двух разных объектов массива. Давайте пофилософствуем. Что из себя представляют разные объекты массива? Согласно формулировке, использованной в стандарте, каждое измерение многомерного массива является массивом само по себе. Модифицированная версия нашего вводного примера, содержащая многомерный массив, имеет следующий вид:

#include <stdio.h>

int main(void) {
    int x[2][1];
    int *p = &x[0][1];
    int *q = &x[1][0];
    printf("%p %p %d\n", (void *)p, (void *)q, p == q);
    return 0;
}

Указатель p указывает на элемент объекта массива, следующий за последним, который является частью объекта многомерного массива. Указатель q указывает на первый элемент объекта массива, смежного с объектом массива от которого вычисляется p. Так как оба массива являются частью многомерного массива, сравнение p и q на равенство - это определенное поведение. Таким образом p == q всегда имеет значение true. GCC и Clang вычисляет выражение во время компиляции и заменяет его на константу со значением true, т.е. выдают инструкцию ассемблера mov ecx, 1 для всех уровней оптимизации, кроме 0.

Важной частью примера является то, что &x[0] указывает на объект, отличный от &x[1]. Однако это явно не указывается в стандарте С11, но читается между строк.

Резюме

Мы начали с безобидного примера и наткнулись на несколько ловушек, которые привели нас к неопределенному поведению. Наш вводный пример содержит в себе ту же проблему, что и пример из Linux: сравнение двух указателей, полученных от двух полностью несвязанных объектов, вызывает неопределенное поведение. Не имеет значения, имеют ли объекты внешнюю или внутреннюю линковку, имеют ли автоматическую длительность хранения или нет.

Наиболее проблематичной частью был пункт § 6.5.9 главы 6, где было явно разрешено сравнивать два указателя из двух разных объектов массива. В этот момент я бы предпочел иметь пояснение в качестве по крайней мере одного предложения, заявляющего, что оба указателя должны происходить из двух массивов, которые являются составными частями одного многомерного массива. Формулировка стала еще более запутанной в пункте § 6.5.8 главы 5, где определены реляционные операторы. Там стандарт говорит только об указателях на тот же объект массива.

По моему мнению, разговор о различных массивах для каждого измерения многомерного массива вводит в заблуждение. Подходя к вопросу с философской точки зрения, разве элемент массива, содержащегося в многомерном массиве, не является сам элементом многомерного массива? Если так, то два элемента e1, e2 двух различных массивов a1, a2 которые в одном и том же многомерном массиве x, также являются двумя элементами из того же многомерного массива x. Тогда два указателя p1, p2, указывающих на элементы e1, e2, также указывают на разные объекты массива a1, a2 и одновременно на один и тот же объект массива x. Таким образом, понятия одинаковый и различный становятся избыточными и запутывают больше, чем помогают.

Общее ощущение относительно формулировки стандарта C11 относительно представленной проблемы неудовлетворительное. Так как несколько человек уже столкнулись с этим, возникает вопрос: почему бы не сделать формулировку более точной?

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

Если вы заинтересованы подобной работе по той же теме, я могу рекомендовать следующую: Clarifying the C memory object model (n2012)

Дополнение. Указатели на позицию за последним элементом массива

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

const int num = 64;
int x[num];

for (int *i = x; i < &x[num]; ++i) { /* ... */ }

С помощью цикла мы обходим весь массив x, состоящий из 64 элементов, т.е. тело цикла должно выполниться ровно 64 раза. Но на самом деле условие проверяется 65 раз - на один раз больше, чем число элементов в массиве. В первые 64 итерации указатель i всегда ссылается внутрь массива x, тогда как выражение &x[num] всегда указывает на позицию за последним элементом массива. На 65-й итерации указатель i будет также ссылаться на позицию за концом массива x, из-за чего условие цикла станет ложным. Это удобный способ обойти весь массив, при этом он опирается на исключение из правила о неопределённости поведения при сравнении таких указателей. Обратите внимание, что стандарт описывает поведение лишь при сравнении указателей; их разыменование - это отдельная тема.

Можно ли изменить наш пример так, чтобы на позицию за последним элементом массива x не ссылался бы ни один указатель? Можно, но это будет сложнее. Придётся изменить условие цикла и запретить инкремент переменной i на последней итерации.

const int num = 64;
int x[num];

for (int *i = x; i <= &x[num-1]; ++i) {
        /* ... */
        if (i == &x[num-1]) break;
}

В этом коде полно технических тонкостей, возня с которыми отвлекает от главной задачи. Кроме того, в теле цикла появилась дополнительная ветка. Так что я считаю разумным, что стандарт разрешает исключения при сравнении указателей на позицию за последним элементом массива.

Примечание команды PVS-Studio

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

Статья впервые была опубликована на английском языке на сайте stefansf.de. Оригинал и перевод публикуются на нашем сайте с разрешения автора.

#Cpp #Knowledge