Трудно отлаживать SEGV из-за пропущенных cmov из-за пределов памяти

Question

Я пытаюсь закодировать несколько высокопроизводительных функций сборки в качестве упражнения и столкнулся со странным segfault, возникающим при запуске программы, но не в valgrind или nemiver.

В основном, cmov, который не должен запускаться, с внешним адресом, делает меня segfault, даже если условие всегда ложно

У меня быстрая и медленная версия. Медленный работает все время. Быстрый работает, если только он не получает не ascii char, в этот момент он ужасно падает, если я не использую adb или nemiver.

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

это работает:

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    jnz .error
    mov EAX, [rel ascii_flags + EDI]    ; load ascii table if input fits
    and EAX, 0b00001000         ; get specific bit
.error:
    ret

но это не так:

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    cmovz EAX, [rel ascii_flags + EDI]  ; load ascii table if input fits
    and EAX, flag_print         ; get specific bit
    ret

В действительности Valgrind аварийно завершает работу, но не имеет никакой другой информации, кроме адресов памяти, поскольку мне не удалось получить больше отладочной информации.

Edit:

Я написал три версии функций, чтобы учесть замечательные ответы:

ft_isprint:
    mov RAX, 128                            ; load default index
    test RDI, ~127                          ; check for non-ascii (>127) input
    cmovz RAX, RDI                          ; if none are found, load correct index
    mov AL, byte [ascii_flags + RAX]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit (and zeros rest of RAX)
    ret

ft_isprint_branch:
    test RDI, ~127                          ; check for non-ascii (>127) input
    jnz .out_of_bounds                      ; if non-ascii, jump to error handling
    mov AL, byte [ascii_flags + RDI]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit (and zeros rest of RAX)
    ret
.out_of_bounds:
    xor RAX, RAX                            ; zeros return value
    ret

ft_isprint_compact:
    xor RAX, RAX                            ; zeros return value preemptively
    test RDI, ~127                          ; check for non-ascii (>127) input
    jnz .out_of_bounds                      ; if non-ascii was found, skip dereferenciation
    mov AL, byte [ascii_flags + RDI]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit
.out_of_bounds:
    ret

После тщательного тестирования функции ветвления определенно быстрее, чем функция cmov, примерно в 5-15% для всех типов данных. Разница между компактной и некомпактной версиями, как и ожидалось, минимальна. Компактность всегда немного быстрее для набора предсказуемых данных, в то время как некомпактность так же немного быстрее для непредсказуемых данных.

Я пробовал разные способы пропустить инструкцию 'xor EAX, EAX', но не смог найти ни одного, который бы работал.

Редактировать: после дополнительных испытаний я обновил код до трех новых версий:

ft_isprint_compact:
    sub EDI, 32                             ; substract 32 from input, to overflow any value < ' '
    xor EAX, EAX                            ; set return value to 0
    cmp EDI, 94                             ; check if input <= '~' - 32
    setbe AL                                ; if so, set return value to 1
    ret

ft_isprint_branch:
    xor EAX, EAX                            ; set return value to 0
    cmp EDI, 127                            ; check for non-ascii (>127) input
    ja .out_of_bounds                       ; if non-ascii was found, skip dereferenciation
    mov AL, byte [rel ascii_flags + EDI]    ; dereference index into least sig. byte
.out_of_bounds:
    ret

ft_isprint:
    mov EAX, 128                            ; load default index
    cmp EDI, EAX                            ; check if ascii
    cmovae EDI, EAX                         ; replace with 128 if outside 0..127
                                            ; cmov also zero-extends EDI into RDI
;   movzx EAX, byte [ascii_flags + RDI]     ; alternative to two following instruction if masking is removed
    mov AL, byte [ascii_flags + RDI]        ; load table entry
    and EAX, flag_print                     ; apply mask to get correct bit and zero rest of EAX
    ret

Производительность следующая, в микросекундах. 1-2-3 показывают порядок выполнения, чтобы избежать преимущества кэширования:

-O3 a.out
1 cond 153185, 2 branch 238341 3 no_table 145436
1 cond 148928, 3 branch 248954 2 no_table 116629
2 cond 149599, 1 branch 226222 3 no_table 117428
2 cond 117258, 3 branch 241118 1 no_table 147053
3 cond 117635, 1 branch 228209 2 no_table 147263
3 cond 146212, 2 branch 220900 1 no_table 147377
-O3 main.c
1 cond 132964, 2 branch 157963 3 no_table 131826
1 cond 133697, 3 branch 159629 2 no_table 105961
2 cond 133825, 1 branch 139360 3 no_table 108185
2 cond 113039, 3 branch 162261 1 no_table 142454
3 cond 106407, 1 branch 133979 2 no_table 137602
3 cond 134306, 2 branch 148205 1 no_table 141934
-O0 a.out
1 cond 255904, 2 branch 320505 3 no_table 257241
1 cond 262288, 3 branch 325310 2 no_table 249576
2 cond 247948, 1 branch 340220 3 no_table 250163
2 cond 256020, 3 branch 415632 1 no_table 256492
3 cond 250690, 1 branch 316983 2 no_table 257726
3 cond 249331, 2 branch 325226 1 no_table 250227
-O0 main.c
1 cond 225019, 2 branch 224297 3 no_table 229554
1 cond 235607, 3 branch 199806 2 no_table 226286
2 cond 226739, 1 branch 210179 3 no_table 238690
2 cond 237532, 3 branch 223877 1 no_table 234103
3 cond 225485, 1 branch 201246 2 no_table 230591
3 cond 228824, 2 branch 202015 1 no_table 226788

Версия без таблицы примерно такая же быстрая, как у cmov, но не допускает легко реализуемых локальных объектов. Алгоритм ветвления хуже разве что на предсказуемых данных при нулевой оптимизации? У меня там нет объяснений.

Я сохраню версию cmov, которая является самой элегантной и легко обновляемой. Спасибо за помощь.

Answer 1

Как объяснил Питер Кордес, cmovCC безусловно загружается из памяти. Одна вещь, которую вы можете сделать, чтобы облегчить эту проблему, это сначала сделать условное движение на edi, чтобы очистить edi, если персонаж находится вне диапазона, вызывая загрузку условного движения с ascii_flags[0] и избегая вашей проблемы. Удобно, когда вы это делаете, eax уже ясно.

Также обратите внимание, что вы можете избегать использования 32-битных регистров в качестве регистров базы и индекса, так как они требуют дополнительного префикса для представления и могут быть медленнее на некоторых архитектурах. Просто используйте их 64-битные аналоги.

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    cmovnz EDI, EAX             ; clear EDI if not ascii
    cmovz EAX, [ascii_flags + RDI]  ; load ascii table if input fits
    and EAX, flag_print         ; get specific bit
    ret

Чтобы решить другие проблемы Питера Кордеса, я бы на самом деле использовал такой код:

; PIC/PIE safe version, doing only a byte load
ft_isprint:
    lea   rsi, [rel ascii_flags] ; load address of ascii_flags
    mov   eax, 128               ; load offset of dummy entry for "not ASCII"
    test   edi, ~127             ; check if ascii
    cmovz  eax, edi              ; load proper entry if ascii
    movzx  eax, byte [rsi + rax] ; load table entry
    and    eax, flag_print       ; mask the desired flag
    ret

Answer 2

cmov - это операция выбора ALU, которая всегда считывает оба источника до проверки условия . Использование источника памяти не меняет этого. Это не предикатная инструкция ARM, которая действует как NOP, если условие было ложным. cmovz eax, [mem] также безоговорочно пишет EAX, с расширением нуля в RAX независимо от условия.

Что касается большей части ЦП (планировщик вне очереди и т. Д.), То cmovcc reg, [mem] обрабатывается точно так же, как adc reg, [mem]: инструкция ALU с 3 входами и 1 выходом . (adc пишет флаги, в отличие от cmov, но не обращайте на это внимания.) Операнд источника с микроплавкой памятью - это отдельный моп, который, как оказалось, является частью той же инструкции x86. Так работают правила ISA.

Так, действительно, более подходящая мнемоника для cmovz как selectz

---

Только условные нагрузки x86 (которые не работают с ошибочными адресами, просто потенциально работают медленно):

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

  Если на странице, которую вы не можете прочитать, произошел удар TLB, то больше ничего не произойдет, пока сбойная нагрузка не выйдет на пенсию (известно, что она не является спекулятивной и поэтому фактически принимает исключение #PF page-fault, неизбежно будет медленным). На некоторых процессорах такая быстрая обработка приводит к атаке Meltdown. >. <См. <a href="http://blog.stuffedcow.net/2018/05/meltdown-microarchitecture/" rel="nofollow noreferrer">http://blog.stuffedcow.net/2018/05/meltdown-microarchitecture/.

• rep lodsd с RCX = 0 или 1. ( не быстро или эффективно, но ветви микрокода являются особыми и не могут получить выгоду от предсказания ветвления на процессорах Intel. См. Что делает установка REP делать? . Энди Глью упоминает о неправильных прогнозах ветвей микрокода, но я думаю, что они отличаются от обычных промахов ветвей, потому что, кажется, есть фиксированная стоимость.)

• AVX2 vpmaskmovd/q / AVX1 vmaskmovps/pd. Неисправности подавляются для элементов, где маска равна 0. Для загрузки маски с маской all-0 даже с юридического адреса требуется помощь микрокода ~ 200 циклов в режиме адресации base + index.) См. section 12.9 УСЛОВНЫЕ УПАКОВКИ И ХРАНЕНИЯ SIMD и таблица C-8 в руководстве по оптимизации Intel. (В Skylake магазинам по недопустимому адресу с маской «все ноль» также требуется помощь.)

  Более ранняя версия MMX / SSE2 maskmovdqu предназначена только для магазина (и имеет подсказку NT). Только аналогичная инструкция AVX с элементами dword / qword (вместо байтов) имеет форму загрузки.

• AVX512 маскирует нагрузки
• AVX2 собирается с некоторыми / всеми очищенными элементами маски.

... и, может быть, другие, которые я забыл. Нормальная загрузка внутри транзакций TSX / RTM: ошибка прерывает транзакцию вместо повышения #PF. Но вы не можете рассчитывать на неверную ошибку индекса, вместо того, чтобы просто читать поддельные данные откуда-то поблизости, так что на самом деле это не условная загрузка. Это также не супер быстро.

---

Альтернативой может быть cmov адрес, который вы используете безоговорочно, выбирая, с какого адреса загружать. например если бы у вас было 0 для загрузки откуда-то еще, это бы сработало. Но тогда вам придется рассчитывать индексирование таблицы в регистре, не используя режим адресации, чтобы вы могли cmov окончательный адрес.

Или просто CMOV индекс и заполнить таблицу нулевыми байтами в конце, чтобы вы могли загрузить с table + 128.

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

---

Проверка кода

Обратите внимание, что [rel] работает только тогда, когда в режиме адресации нет регистра (кроме RIP). Относительная RIP-адресация заменяет один из 2 избыточных способов (в 32-битном коде) для кодирования [disp32]. Он использует более короткое кодирование без SIB, в то время как ModRM + SIB все еще может кодировать абсолютное значение [disp32] без регистров. (Полезно для адресов, таких как [fs: 16] для небольших смещений относительно локального хранилища потоков с базами сегментов.)

Если вы просто хотите использовать RIP-относительную адресацию, когда это возможно, используйте default rel вверху вашего файла . [symbol] будет относительным RIP, но [symbol + rax] - нет. К сожалению, NASM и YASM по умолчанию default abs.

[reg + disp32] - очень эффективный способ индексации статических данных в позиционно-зависимом коде, просто не обманывайте себя, думая, что они могут быть относительными к RIP. См. 32-разрядные абсолютные адреса, более не разрешенные в x86-64 Linux? .

[rel ascii_flags + EDI] также странно, потому что вы используете 32-битный регистр в режиме адресации в коде x86-64 . Обычно нет причин тратить префикс размера адреса на усечение адресов до 32-разрядного.

Однако, в этом случае, если ваша таблица находится в младших 32 битах виртуального адресного пространства, а ваша функция arg указана только как 32 бита (поэтому вызывающей стороне разрешено оставлять мусор в верхних 32 RDI), на самом деле это выигрыш - использовать [disp32 + edi] вместо mov esi,edi или что-то, что можно расширить до нуля. Если вы делаете это нарочно, обязательно прокомментируйте, почему вы используете 32-битный режим адресации.

Но в этом случае использование cmov в индексе увеличит с нуля до 64-битного для вас.

Также странно использовать DWORD-загрузку из таблицы байтов. Иногда вы пересекаете границу строки кэша и получаете дополнительную задержку.

---

@ fuz показал версию с использованием относительного RIP LEA и CMOV в индексе.

В позиционно-зависимом коде, где 32-битные абсолютные адреса в порядке, во что бы то ни стало используйте его для сохранения инструкций . Режимы адресации [disp32] хуже, чем RIP-относительные (на 1 байт длиннее), но режимы адресации [reg + disp32] отлично подходят, когда позиционно-зависимый код и 32-битные абсолютные адреса в порядке. (Например, x86-64 Linux, но не OS X, где исполняемый файл всегда отображается за пределами младших 32 бит.) Просто имейте в виду, что это не rel.

; position-dependent version taking advantage of 32-bit absolute [reg + disp32] addressing
; not usable in shared libraries, only non-PIE executables.
ft_isprint:
    mov     eax, 128               ; offset of dummy entry for "not ASCII"
    cmp     edi, eax               ; check if ascii
    cmovae  edi, eax               ; replace with 128 if outside 0..127
              ; cmov also zero-extends EDI into RDI
    movzx   eax, byte [ascii_flags + rdi] ; load table entry
    and     al, flag_print         ; mask the desired flag
      ; if the caller is only going to read / test AL anyway, might as well save bytes here
    ret

Если какая-либо существующая запись в вашей таблице имеет те же флаги, которые вы хотите использовать для высоких значений , например может быть, запись 0, которую вы никогда не увидите в строках с неявной длиной, вы все равно можете использовать EAX с нулевым или нулевым значением и хранить в таблицах 128 байт, а не 129.

test r32, imm32 занимает больше байтов кода, чем вам нужно . ~127 = 0xFFFFFF80 подходит для байта с расширенным знаком, но это не кодировка TEST r/m32, sign-extended-imm8. Однако есть такая кодировка для cmp, как и для всех других непосредственных инструкций.

Вместо этого вы можете проверить наличие без знака выше 127 с помощью cmp edi, 127 / cmovbe eax, edi или cmova edi, eax. Это экономит 3 байта размера кода. Или мы можем сохранить 4 байта, используя cmp reg,reg, используя 128, который мы использовали для индекса таблицы.

Проверка диапазона перед индексацией массива также более интуитивна для большинства людей, чем проверка старших битов.

and al, imm8 составляет всего 2 байта против 3 байтов для and r/m32, sign-extended-imm8. Это не медленнее на любых процессорах, если вызывающая сторона читает только AL. На процессорах Intel до Sandybridge чтение EAX после ANDing в AL может привести к частичной остановке / замедлению регистрации. Sandybridge не переименовывает частичные регистры для операций чтения-изменения-записи, если я правильно помню, а IvB и более поздние версии вообще не переименовывают парциальные регистры low8.

Вы также можете использовать mov al, [table] вместо movzx для сохранения другого байта кода. Более ранний mov eax, 128 уже сломал любую ложную зависимость от старого значения EAX, поэтому у него не должно быть снижения производительности. Но movzx неплохая идея.

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