может быть на не отображенной странице памяти.

р, показывающий оптимизацию gcc и код пользователя, который может быть ошибочным

Функция 'foo' в приведенном ниже фрагменте загрузит только один из членов структуры A или B; ну, по крайней мере, это намерение неоптимизированного кода.

typedef struct {
  int A;
  int B;
} Pair;

int foo(const Pair *P, int c) {
  int x;
  if (c)
    x = P->A;
  else
    x = P->B;
  return c/102 + x;
}

Вот что дает gcc -O3:

mov eax, esi
mov edx, -1600085855
test esi, esi
mov ecx, DWORD PTR [rdi+4]   <-- ***load P->B**
cmovne ecx, DWORD PTR [rdi]  <-- ***load P->A***
imul edx
lea eax, [rdx+rsi]
sar esi, 31
sar eax, 6
sub eax, esi
add eax, ecx
ret

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

#include <stdlib.h>  

int naughty_caller(int c) {
  Pair *P = (Pair*)malloc(sizeof(Pair)-1); // *** Allocation is enough for A but not for B ***
  if (!P) return -1;

  P->A = 0x42; // *** Initializing allocation only where it is guaranteed to be allocated ***

  int res = foo(P, 1); // *** Passing c=1 to foo should ensure only P->A is accessed? ***

  free(P);
  return res;
}

Если предположения о загрузке произойдут в приведенном выше сценарии, есть вероятность, что загрузка P-> B вызовет исключение, поскольку последний байт P-> B может находиться в нераспределенной памяти. Это исключение не произойдет, если оптимизация отключена.

Вопрос

Является ли приведенная выше оптимизация gcc для спекуляций нагрузки допустимой? Где спецификация говорит или подразумевает, что это нормально? Если оптимизация законна, как код в naughtly_caller может оказаться неопределенным поведением?

 Leushenko02 окт. 2017 г., 12:58
Не является прямым ответом на вопрос о нагрузках, но, поскольку 6.7.2.1/15 говорит, что указатель на структуру всегда можно преобразовать в указатель на ее первый член,является стандартный способ сделать это, если по какой-то причине это требуется: доступA с участиемx = *(int *)P вместо. (GCC тогда испустит ветвь.) Хотя на самом деле не обобщает.
 Some programmer dude02 окт. 2017 г., 11:03
Зачем вам даже выделять меньше памяти, чем на самом деле нужно структуре? Какая у вас проблема? Или это просто любопытство?
 Sean02 окт. 2017 г., 11:03
ВыделивPair это меньше чемsizeof(Pair) Вы находитесь на неопределенной территории поведения. У вас нет разумных ожиданий, что ваш код будет работать правильно после этого.
 phuclv02 окт. 2017 г., 17:03
 joop02 окт. 2017 г., 11:07
Конечно, оптимизация законна. Функция ожидаетstruct Pair *p, но вы даете ему указатель на другой (и меньший) объект.

Ответы на вопрос(6)

если никакая соответствующая программа не может определить разницу. Например, реализация может гарантировать, что после каждого блока, выделенного с помощью malloc, есть по крайней мере восемь байтов, к которым можно получить доступ без побочных эффектов. В этой ситуации компилятор может генерировать код, который будет иметь неопределенное поведение, если вы напишите его в своем коде. Таким образом, было бы законно, чтобы компилятор считывал P [1] всякий раз, когда P [0] правильно распределен, даже если это было бы неопределенным поведением в вашем собственном коде.

Но в вашем случае, если вы не выделяете достаточно памяти для структуры, то чтениеЛюбые член неопределенного поведения. Так что здесь компилятору разрешено делать это, даже если чтение P-> B дает сбой.

 Peter Cordes02 окт. 2017 г., 21:28
Реализация также должна будет заполнить пространство, в которое она помещает статическое хранилище (.bss, .data и .rodata), чтобы убедиться, что в конце страницы нет статических объектов. Но да, это может работать до тех пор, пока реализацияне обеспечить доступ к любым системным вызовам ОС, которые выделяют страницу, потому что это может позволить соответствующей программе получить указатель на последний объект на странице (или что-то еще; защита памяти не должна основываться на странице).
 Martin Rosenau03 окт. 2017 г., 07:19
Давайте посмотрим на следующий пример:int *x=malloc(...); foo(x+31, y); В этом случаеP->B может быть на не отображенной странице памяти.

-> оператор и идентификатор обозначают член структуры или объединенного объекта. Это значение именованного члена объекта, на который указывает первое выражение

Если вызвать выражениеP->A хорошо определен, тоP должен фактически указывать на объект типаstruct Pair, и следовательноP->B также четко определен.

 Marc Glisse03 окт. 2017 г., 09:37
То, как его интерпретируют несколько компиляторов, «обозначает элемент структуры или объекта объединения» означает, что-> делает арифметику указателя (добавить смещение), но это только когда вы пытаетесьполучить доступ к значению (либо прочитайте, либо напишите), что второе предложение вступает в игру, и вы получаете некоторые гарантии относительно базового объекта (такx=P->A это хорошо, ошибкаvoid*z=&P->A не будет ничего гарантировать). В стандарте нет ясности по этому поводу, но, похоже, важно знать, что делают компиляторы.

потому что чтение некоторой области памяти не считается наблюдаемым поведением в общем случае (volatile изменил бы это).

Ваш пример кода действительно неопределенного поведения, но я не могу найти ни одного отрывка в стандартных документах, где это прямо указано. Но я думаю, что достаточно взглянуть на правилаэффективные типы ... из N1570, §6.5 p6:

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

Итак, ваш доступ для записи в*P на самом деле дает этот объект типPair - следовательно, он просто распространяется в память, которую вы не распределили, в результате вы получаете доступ за пределами границ.

 user237152402 окт. 2017 г., 11:18
@ Joop Я так не думаю,структура взломать доступ к массиву за пределами ... связанных, но не одно и то же.
 joop02 окт. 2017 г., 11:16
Я думаю, что рассуждения должны быть такими же, как и дляструктура взломать, (хотя в этом случае заявленный размер будетменьше чем фактический размер)
 user237152402 окт. 2017 г., 14:12
@hvd это действительно проблема с формулировкой стандарта. Понятно чтоимел ввиду (ИМХО), так как вы не можете иметь только часть объекта, и объект имеет типPairно говоря оименующий здесь неточно.
 Marc Glisse02 окт. 2017 г., 21:39
@hvd интерпретация компиляторами того факта, что написание lvalue важно.x=P->A обращается к объекту типа Pair, в то время какconst int*q=&P->A;x=*q получает доступ к объекту типа int (предположительно, дажеx=*(int const*)&P->A делает это, и это делает для Clang, но GCC имеет ошибку, и я забыл, чтоx=*&P->A должен делать).
 user74338202 окт. 2017 г., 23:57
@MarcGlisse Да, это именно то, что предназначено, поскольку оно соответствует примеру в обсуждении DR # 236 для доступа членов профсоюза, но стандарт этого не говорит, и, как вы указываете, есть угловые случаи, когда намерение неясно , Другим угловым случаем может быть просто доступ к элементу структуры в скобках: в C ++ есть общее правило, что «выражение в скобках» может использоваться точно в тех же контекстах, в которых может использоваться вложенное выражение, и с тем же значением, если не указано иное. "но C не делает, а GCCделает относиться к выражениям в скобках по-разному в C.

-> оператор наPair * подразумевает, что есть целоеPair Объект полностью выделен. (@Hurkyl цитирует стандарт.)

x86 (как и любая обычная архитектура) не имеет побочных эффектов для доступа к обычной выделенной памяти, поэтомуСемантика памяти x86 совместима с семантикой абстрактной машины C для неvolatile Память, Компиляторы могут спекулятивно загружаться, если / когда они думают, что это будет выигрыш в производительности целевой микроархитектуры, для которой они настраиваются в любой конкретной ситуации.

Обратите внимание, что в x86 защита памяти работает с гранулярностью страниц. Компилятор может развернуть цикл или векторизовать с помощью SIMD таким образом, чтобы он читал вне объекта, если все страницы, к которым он прикасался, содержат несколько байтов объекта.Безопасно ли читать после конца буфера на одной и той же странице на x86 и x64?, Libcstrlen() реализации, написанные от руки в ассемблере, делают это, но FIK gcc не делает этого, вместо этого использует скалярные циклы для оставшихся элементов в конце автоматически векторизованного цикла, даже когда он уже выровнял указатели с (полностью развернутым) циклом запуска. (Возможно, потому что это сделало бы проверку времени выполнения сvalgrind трудно.)

Чтобы получить ожидаемое поведение, используйтеconst int * rg.

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

В C вы можете передать эту функцию указатель на одинint, так долго какc ненулевой При компиляции для x86, gcc должен предполагать, что он может указывать на последнийint на странице, со следующей страницей без отображения.

Source + gcc и clang вывод для этого и других вариантов в проводнике компилятора Godbolt

// exactly equivalent to  const int p[2]
int load_pointer(const int *p, int c) {
  int x;
  if (c)
    x = p[0];
  else
    x = p[1];  // gcc missed optimization: still does an add with c known to be zero
  return c + x;
}

load_pointer:    # gcc7.2 -O3
    test    esi, esi
    jne     .L9
    mov     eax, DWORD PTR [rdi+4]
    add     eax, esi         # missed optimization: esi=0 here so this is a no-op
    ret
.L9:
    mov     eax, DWORD PTR [rdi]
    add     eax, esi
    ret

В С,выМожно передать сортировку передать объект массива (по ссылке) в функцию, гарантируя функции, что разрешено касаться всей памяти, даже если абстрактная машина C этого не делает.Синтаксисint p[static 2]

int load_array(const int p[static 2], int c) {
  ... // same body
}

Но gcc не использует преимущества и выдает идентичный код для load_pointer.

Не по теме: clang компилирует все версии (struct и array) одинаково, используяcmov без ответвлений вычислить адрес загрузки.

    lea     rax, [rdi + 4]
    test    esi, esi
    cmovne  rax, rdi
    add     esi, dword ptr [rax]
    mov     eax, esi            # missed optimization: mov on the critical path
    ret

Это не обязательно хорошо: у него более высокая задержка, чем у структурного кода gcc, потому что адрес загрузки зависит от пары дополнительных операций LU. Это очень хорошо, если оба адреса небезопасны для чтения, а ветка плохо предсказывает.

Мы можем получить лучший код для той же стратегии из gcc и clang, используяsetcc (1 моп с задержкой 1с на всех процессорах, кроме некоторых действительно старых), вместоcmovcc (2 мопа на Intel до Skylake).xorОбнуление всегда дешевле, чем LE.

int load_pointer_v3(const int *p, int c) {
  int offset = (c==0);
  int x = p[offset];
  return c + x;
}

    xor     eax, eax
    test    esi, esi
    sete    al
    add     esi, dword ptr [rdi + 4*rax]
    mov     eax, esi
    ret

gcc и clang оба ставят финалmov на критическом пути. А в семействе Intel Sandybridge режим индексированной адресации не остается микрослитой сadd, Так что это было бы лучше, как в версии с ветвлением:

    xor     eax, eax
    test    esi, esi
    sete    al
    mov     eax, dword ptr [rdi + 4*rax]
    add     eax, esi
    ret

Простые режимы адресации, такие как[rdi] или же[rdi+4] задержка на 1с ниже, чем у других процессоров семейства Intel SnB, так что на Skylake эта задержка может быть и хуже (гдеcmov дешево).test а такжеlea может работать параллельно.

После включения этого финалаmov вероятно, не существовало бы, и это могло бы простоadd вesi.

volatile) не считается "побочным эффектом", как указано в стандарте C. Таким образом, программа может свободно читать местоположение и затем отбрасывать результат, что касается стандарта Си.

Это очень распространено. Предположим, вы запрашиваете 1 байт данных из 4-байтового целого числа. Компилятор может затем прочитать все 32 бита, если это быстрее (выравнивание чтения), и затем отбросить все, кроме запрошенного байта. Ваш пример похож на это, но компилятор решил прочитать всю структуру.

Формально это находится в поведении «абстрактной машины», C11 глава 5.1.2.3. Учитывая, что компилятор следует указанным там правилам, он может делать все, что пожелает. И единственные перечисленные правила касаютсяvolatile объекты и последовательность инструкций. Чтение другого члена структуры вvolatile структура не будет в порядке.

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

 Marc Glisse02 окт. 2017 г., 21:30
Это не учитывает тот факт, что указатели C могут указывать на любой не связанный тип, только когда вы разыменовываете их, а затем читаете / записываете в них, вы получаете некоторые гарантии.
 joop02 окт. 2017 г., 11:49
Кстати: компилятору даже будет разрешено загружать элементы {A, B} в один (достаточно широкий) регистр и извлекать значения A или B, используя shift + маскирование.
 Lundin03 окт. 2017 г., 08:31
@MarcGlisse Какое это имеет отношение к вопросу?
 Hurkyl03 окт. 2017 г., 06:15
@MarcGlisse: разыменование достаточно для неопределенного поведения:The operand of unary * has an invalid value, Точно так же документация-> говорит, что его использование относится кчлен структурного объекта, так что еслиP->A четко определен,P должен указывать на случайstruct pair.
 joop02 окт. 2017 г., 18:24
Примечание: ранние 8086/8088 (и даже ранние компиляторы для него) использовали этот трюк среза регистров для регистров ах + аль.

*P распределяется правильноP->B никогда не будет в нераспределенной памяти. Это не может быть инициализировано, вот и все.

Компилятор имеет полное право делать то, что они делают. Единственное, что не разрешено, это ой о доступеP->B с тем оправданием, что он не инициализирован. Но что и как они делают, все это остается на усмотрение реализации, а не ваша забота.

Если вы приведете указатель на блок, возвращенныйmalloc вPair* это не гарантируется быть достаточно широким, чтобы держатьPair поведение вашей программы не определено.

 user237152402 окт. 2017 г., 14:15
@DanielFischer начинает такую ​​мысль с "если [...] реализация [...]всегда должен предлагать ответ. Пока вы не имеете в видуреализация определена...
 Joshua03 окт. 2017 г., 06:38
@DanielFischer: выравнивание malloc всегда гарантируется кратным размеру системного слова, чтобы предотвратить такие взрывы, как этот. По сути, стандарт гласит, что это не приведет к сбою, поэтому компилятор и malloc () должны взаимодействовать, чтобы этого не произошло. Смотреть это все же; этот нераспределенный байт может быть выделен вызовом malloc (1) или содержать защитное значение, поэтому никогда не записывайте в него.
 Jens Gustedt02 окт. 2017 г., 14:22
@DanielFischer, нет, пока под «определенным поведением» вы подразумеваете поведение, определенное стандартом Си. Любая платформа может свободно определять любые расширения, которые они хотят, но это за пределами стандарта и, следовательно, не переносимо.
 Daniel Fischer02 окт. 2017 г., 14:13
Интересно, если использовать реализацию гдеmalloc всегда выделяет размеры, кратные четырем байтам (или возвращаетNULL), а такжеsizeof(int) == alignof(int) == 4, таким образомреализация гарантирует, чтоmalloc(sizeof(Pair) - 1) выделяет достаточно для размещенияPair в случае успеха это определит поведение?

Ваш ответ на вопрос