Точные измерения максимального количества циклов с помощью RDTSC

Question

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

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

Поэтому возникает вопрос: " Как я могу отличить измерение, которое было прервано, от измерения, которое законно заняло намного больше времени, чем остальные? "

Или, в более общем смысле: " Как измерить полное распределение времени выполнения, не предполагая заранее жесткого максимума? "

Хранит ли ядро ​​какую-либо информацию, которую я мог бы запросить о том, произошло ли прерывание? Что-то, что я мог бы запросить до и после измерения, что бы сказать мне, если измерение было прервано? В идеале это скажет мне, как долго в циклах потребовалось прерывание, но просто знание того, что измерение затронуто, было бы хорошим началом.

Может быть, в дополнение к (или вместо) RDTSC, я могу использовать RDPMC для считывания счетчика, который измеряет количество циклов, проведенных в Ring 0 (ядро) вместо Ring 3 (пользователь)? Может быть, счетчик уже настроен для этого или мне нужно настроить свой собственный? Нужно ли создавать собственный модуль ядра для этого или я могу использовать существующие ioctl?

Немного предыстории:

Я в основном работаю под управлением Ubuntu 14.03 Linux 4.2.0 на Intel Skylake i7-6700, но я также тестирую на Intel Sandy Bridge и Haswell. Я уже сделал все возможное, чтобы максимально уменьшить дрожание в системе. Я перекомпилировал ядро ​​без галочки с CONFIG_NOHZ_FULL, без принудительного вытеснения, с отключенной поддержкой прозрачных огромных страниц и частотой таймера 100 Гц.

Я остановил большинство ненужных процессов и удалил большинство ненужных модулей ядра. Я использую cpuset / cset shield, чтобы зарезервировать одно из ядер NoHZ для одного процесса, и использовал kernel/debug/tracing, чтобы убедиться, что у меня очень мало прерываний. Но мне все еще достаточно, чтобы точные измерения были трудными. Может быть, что еще более важно, я могу представить себе будущие "длинные хвосты" (хеш-таблицу, размер которой редко нужно изменять), где было бы очень полезно различать действительные и недействительные измерения.

Я измеряю время выполнения с помощью RDTSC/RDTSCP, используя методы, предложенные Intel в своем техническом описании, и в целом получаю ожидаемую точность. Мои тесты включают в себя поиск 16-битных значений, и я многократно и индивидуально определяю время каждого из 65536 возможных поисков случайных массивов различной длины. Чтобы процессор не усвоил правильное предсказание ветвления, поиски повторяются в разном порядке каждый раз. Найденный массив удаляется из кэша после каждого поиска с помощью "CLFLUSH".

Это исследовательский проект, и моя цель - узнать об этих проблемах. Таким образом, я готов к подходам, которые в противном случае могли бы считаться глупыми и экстремальными. Пользовательские модули ядра, сборка в защищенном режиме x64, непроверенные модификации ядра и особенности процессора - все это честная игра. Если есть способ избавиться от нескольких оставшихся прерываний, чтобы все измерения были "реальными", это также могло бы стать жизнеспособным решением. Спасибо за предложения!

Answer 1

Я предполагаю, что вы защитили свой поток тестов в максимально возможной степени:

• Он имеет эксклюзивный доступ к ядру своего процессора (не только к HyperThread), здесь вы найдете информацию о том, как легко управлять этим.
• Сродства к прерываниям удалены из этого ядра, смотрите здесь
• Если возможно, запустите nohz ядро, чтобы минимизировать тики таймера.

Более того, вам не следует прыгать в пространство ядра из своего пути кода, указанного в тесте: по возвращении ваш поток может быть запланирован на некоторое время.

Однако вы просто не можете избавиться от всех прерываний в ядре процессора: в Linux локальные прерывания таймера APIC, межпроцессорные прерывания (IPI) и другие используются для внутренних целей, и вы просто не можете избавиться от них! Например, прерывания по таймеру используются, чтобы гарантировать, что потоки в конечном счете запланированы. Аналогично, IPI используются для выполнения действий триггера на других ядрах, таких как сбой TLB.

Теперь, благодаря инфраструктуре трассировки Linux, можно из пользовательского пространства определить, произошел ли hardirq в течение определенного периода времени.

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

1. Во-первых, это "реальные" внешние аппаратные прерывания, занимаемые реальными устройствами, такими как сетевые адаптеры, звуковые карты и тому подобное.
2. Есть прерывания для внутреннего использования Linux.

Оба являются hardirq в том смысле, что процессор асинхронно передает управление в подпрограмму обработки прерываний (ISR) в соответствии с таблицей дескрипторов прерываний (IDT).

Обычно в Linux ISR - это просто заглушка, написанная на ассемблере, которая передает управление высокоуровневому обработчику, написанному на C.

Подробнее см. В arch/x86/entry_entry_64.S в исходниках ядра Linux. Для внутренних прерываний Linux определяется заглушка трассировки, в то время как для внешних прерываний трассировка оставляется высокоуровневым обработчикам прерываний.

Таким образом, существует одно событие трассировки для каждого внутреннего прерывания:

# sudo perf list | grep irq_vectors:
  irq_vectors:call_function_entry                    [Tracepoint event]
  irq_vectors:call_function_exit                     [Tracepoint event]
  irq_vectors:call_function_single_entry             [Tracepoint event]
  irq_vectors:call_function_single_exit              [Tracepoint event]
  irq_vectors:deferred_error_apic_entry              [Tracepoint event]
  irq_vectors:deferred_error_apic_exit               [Tracepoint event]
  irq_vectors:error_apic_entry                       [Tracepoint event]
  irq_vectors:error_apic_exit                        [Tracepoint event]
  irq_vectors:irq_work_entry                         [Tracepoint event]
  irq_vectors:irq_work_exit                          [Tracepoint event]
  irq_vectors:local_timer_entry                      [Tracepoint event]
  irq_vectors:local_timer_exit                       [Tracepoint event]
  irq_vectors:reschedule_entry                       [Tracepoint event]
  irq_vectors:reschedule_exit                        [Tracepoint event]
  irq_vectors:spurious_apic_entry                    [Tracepoint event]
  irq_vectors:spurious_apic_exit                     [Tracepoint event]
  irq_vectors:thermal_apic_entry                     [Tracepoint event]
  irq_vectors:thermal_apic_exit                      [Tracepoint event]
  irq_vectors:threshold_apic_entry                   [Tracepoint event]
  irq_vectors:threshold_apic_exit                    [Tracepoint event]
  irq_vectors:x86_platform_ipi_entry                 [Tracepoint event]
  irq_vectors:x86_platform_ipi_exit                  [Tracepoint event]

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

# sudo perf list | grep irq:
  irq:irq_handler_entry                              [Tracepoint event]
  irq:irq_handler_exit                               [Tracepoint event]
  irq:softirq_entry                                  [Tracepoint event]
  irq:softirq_exit                                   [Tracepoint event]
  irq:softirq_raise                                  [Tracepoint event]

Итак, проследите все эти IRQ *_entries на время вашего пути тестового кода, и вы знаете, был ли ваш образец теста отравлен IRQ или нет.

Обратите внимание, что в x86 существует третий тип стиля аппаратного прерывания: исключения. По крайней мере, я бы также проверил наличие ошибок на странице. И для НМИ, которые были пропущены выше (через nmi:nmi_handler).

Для вашего удобства я собрал небольшой кусочек кода для отслеживания IRQ во время вашего тестового пути кода. Смотрите в комплекте example.c для использования. Обратите внимание, что доступ к /sys/kernel/debug необходим для определения идентификаторов трассировки.

Answer 2

Мне известны два "быстрых" способа наблюдения прерываний на x86, первый из которых я использовал сам.

1. Вы можете использовать пользовательское пространство rdpmc читать hw_interrupts.received непосредственно, до и после вашего протестированного раздела, чтобы определить, произошли ли какие-либо прерывания. Чтобы запрограммировать счетчик и обработать чтение, в этом ответе я перечислил несколько библиотек. Если бы я начинал новый проект сейчас, я бы, вероятно, использовал pmu-toolsили, возможно, просто использовать perf_event_open непосредственно, поскольку это не так уж сложно реализовать.

2. Установка либо %fs или же %gs к ненулевому значению перед вашей временной областью, а затем проверяя, что значение остается неизменным после. Если он был установлен на ноль, то произошло прерывание, потому что iret инструкция сбрасывает эти регистры. На x86-64 лучше всего использовать %gs поскольку %fs используется для локального хранения потока. Полная информация в этом сообщении в блоге, где я узнал об этом.