1. Впервые прочел про сборку ядра Linux с LTO оптимизацией и Clang из новостей, где упоминалась компания Google. Она использует Clang и LTO оптимизацию для сборки ядра Linux и получения лучшей производительности. Компания Google для меня является синонимом инноваций, лучших программистов в мире и поэтому для меня ее опыт является самым авторитетным. Плюс она привнесла очень много в развитие open source, и ее наработками пользуются тысячи компаний во всем мире.
2. Хоть компания Google начала использовать Clang и LTO оптимизацию раньше, только с выходом ядра Linux 5.12.6 и 5.12.7 было закрыто большое количество багов, и сборка ядра c LTO оптимизаций стала доступна многим. До этого при сборке ядра с LTO оптимизацией многие драйвера давали сбой.
3. Мною уже протестирована работа ядра с LTO на Ryzen 9 3900x + AMD Radeon 5700 XT. Плюс уже давно использую LLVM 12 и Clang для сборки системных программ. Инструментарий LLVM12 и Clang стали основными в моей системе по причине лучшей поддержки моего процессора и нужные мне программы работают быстрее при сборке с помощью Clang. Для программистов Clang дает лучший контроль ошибок, оптимизации и unpredictable behavior. -fdebug-macro, -fsanitize=address, -fsanitize=memory, -fsanitize=undefined, -fsanitize=thread, -fsanitize=cfi, -fstack-protector, -fstack-protector-strong, -fstack-protector-all, -Rpass=inline, -Rpass=unroll, -Rpass=loop-vectorize, -Rpass-missed=loop-vectorize, -Rpass-analysis=loop-vectorize и т.д.
4. Данная возможность толком нигде не была описана в связи с п.2 и есть подводные моменты, которые будут рассмотрены в данной статье.

Внимание, автор статьи не несет ответственность за причиненный вред в следствии использования данной статьи! Все действия вы выполняете на свой страх и риск! Все действия должны выполнять только профессионалы!

Немного теории

• Оптимизируется Абстрактное Синтаксическое Дерево. Оптимизируются циклы, удаляется мертвый код, результат которого нигде не используется. Раскрываются выражения, например 2+5 можно заменить на 7, чтобы при работе приложения не вычислять его значение каждый раз и тем самым сделать его быстрее и т.д.
• Оптимизированное дерево может быть преобразовано в машинный псевдокод понятный компилятору. Псевдокод используется для дополнительной оптимизации, упрощает разработку универсального компилятора для разных архитектур процессора, например для x86-64 и ARMv7\. Так же как ASM листинг, этот псевдокод еще используется, чтобы понять, как компилятор генерирует машинный код, и служит для понимания работы компилятора, поиска ошибок, например, ошибок оптимизации и unpredictable behavior. Стоит заметить этот этап не является обязательным и в некоторых компиляторах отсутствует.
• Происходит векторизация. Векторизация ,Automatic Vectorization, SIMD
• Генерируется объектный файл. Объектный файл содержит в себе машинный код для компьютера, и специальные служебные структуры, в которых все еще есть неизвестные адреса функций и данных, поэтому этот файл все еще не может быть запущен на исполнение. Чтобы разрешить неизвестные адреса, был добавлен этап линковки.

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

• blog.llvm.org/2016/06/thinlto-scalable-and-incremental-lto.html>
• clang.llvm.org/docs/ThinLTO.html>

Установка LLVM 12 и Clang

Cборка LLVM 12 из Arch User Repository

MAKEFLAGS="-j20"NINJAFLAGS="-j20"

MAKEFLAGS="-j$(nproc)"NINJAFLAGS="-j$(nproc)"

• Build with clang and llvm toolchain? Собрать с помощью llvm и clang? Отвечаем Y или Enter если да, и N если нет. Рекомендую собирать LLVM с помощью Clang.
• Skip build tests? Пропустить сборку тестов? Отвечаем Y или Enter. Так как во время сборки, не все тесты проходят проверку, то сборка будет прекращена. Поэтому мы пропускаем сборку тестов, и на самом деле сборка будет идти даже быстрее.
• Skip build documentation? Пропустить сборку документации? Отвечаем Y или Enter если да, и N если нет. Если вам не нужна документация, то можно пропустить, это ускорит сборку. Лучше читать документацию на официальном сайте, это удобнее.
• Skip build OCaml and Go bindings? Пропустить сборку OCaml и Go биндингов? Отвечаем Y или Enter если да, и N если нет. Для большинства ответ Y и их сборку можно смело пропустить в угоду скорости сборки. Для тех кому они нужны, а это очень маленькое количество людей могут ответить N.

Делаем LLVM и Clang сборочным тулчейном по умолчанию в Arch Linux

export CC=clangexport CXX=clang++export LD=ld.lldexport CC_LD=lldexport CXX_LD=lldexport AR=llvm-arexport NM=llvm-nmexport STRIP=llvm-stripexport OBJCOPY=llvm-objcopyexport OBJDUMP=llvm-objdumpexport READELF=llvm-readelfexport RANLIB=llvm-ranlibexport HOSTCC=clangexport HOSTCXX=clang++export HOSTAR=llvm-arexport HOSTLD=ld.lld

CFLAGS="-fdiagnostics-color=always -pipe -O2 -march=native -fstack-protector-strong"CXXFLAGS="-fdiagnostics-color=always -pipe -O2 -march=native -fstack-protector-strong"LDFLAGS="-Wl,-O1,--sort-common,--as-needed,-z,relro,-z,now"

CARCH="x86_64"CHOST="x86_64-pc-linux-gnu"CARCH="x86_64"CHOST="x86_64-pc-linux-gnu"#-- Compiler and Linker Flagsexport CC=clangexport CXX=clang++export LD=ld.lldexport CC_LD=lldexport CXX_LD=lldexport AR=llvm-arexport NM=llvm-nmexport STRIP=llvm-stripexport OBJCOPY=llvm-objcopyexport OBJDUMP=llvm-objdumpexport READELF=llvm-readelfexport RANLIB=llvm-ranlibexport HOSTCC=clangexport HOSTCXX=clang++export HOSTAR=llvm-arexport HOSTLD=ld.lldCPPFLAGS="-D_FORTIFY_SOURCE=2"CFLAGS="-fdiagnostics-color=always -pipe -O2 -march=native -fstack-protector-strong"CXXFLAGS="-fdiagnostics-color=always -pipe -O2 -march=native -fstack-protector-strong"LDFLAGS="-Wl,-O1,--sort-common,--as-needed,-z,relro,-z,now"RUSTFLAGS="-C opt-level=2"#-- Make Flags: change this for DistCC/SMP systemsMAKEFLAGS="-j20"NINJAFLAGS="-j20"#-- Debugging flagsDEBUG_CFLAGS="-g"DEBUG_CXXFLAGS="-g"#DEBUG_CFLAGS="-g -fvar-tracking-assignments"#DEBUG_CXXFLAGS="-g -fvar-tracking-assignments"#DEBUG_RUSTFLAGS="-C debuginfo=2"

cat << 'EOF' >> "${HOME}/.bashrc"export CARCH="x86_64"export CHOST="x86_64-pc-linux-gnu"export CC=clangexport CXX=clang++export LD=ld.lldexport CC_LD=lldexport CXX_LD=lldexport AR=llvm-arexport NM=llvm-nmexport STRIP=llvm-stripexport OBJCOPY=llvm-objcopyexport OBJDUMP=llvm-objdumpexport READELF=llvm-readelfexport RANLIB=llvm-ranlibexport HOSTCC=clangexport HOSTCXX=clang++export HOSTAR=llvm-arexport HOSTLD=ld.lldexport CPPFLAGS="-D_FORTIFY_SOURCE=2"export CFLAGS="-fdiagnostics-color=always -pipe -O2 -march=native -fstack-protector-strong"export CXXFLAGS="-fdiagnostics-color=always -pipe -O2 -march=native -fstack-protector-strong"export LDFLAGS="-Wl,-O1,--sort-common,--as-needed,-z,relro,-z,now"export RUSTFLAGS="-C opt-level=2"export MAKEFLAGS="-j20"export NINJAFLAGS="-j20"export DEBUG_CFLAGS="-g"export DEBUG_CXXFLAGS="-g"EOF

Список системных библиотек и программ которые стоит собирать вручную

Внимание, сборка всех программ и все консольные команды надо выполнять под обычным пользователем, перед установкой у вас попросит пароль root. Сборка всех библиотек и программ из списка не занимает много времени. Все кроме Mesa у меня собирается в районе 1 минуты. Список дан в той в последовательности в которой рекомендуется сборка! К примеру от zlib-ng и zstd зависит Mesa, а от Mesa зависит xorg-server.

source=("https://downloads.sourceforge.net/sourceforge/$pkgname/$pkgname-$pkgver.tar.xz"  "72fa126446460347a504f3d9b90f24aed1365595.patch")sha256sums=('505e70834d35383537b6491e7ae8641f1a4bed1876dbfe361201fc80868d88ca'  '84298548e43976265f414c53dfda1b035882f2bdcacb96ed1bc0a795e430e6a8')prepare() {  cd $pkgname-$pkgver  patch --forward --strip=1 --input="${srcdir:?}/72fa126446460347a504f3d9b90f24aed1365595.patch"}

  -D debug=false \  -D optimization=2 \  -D b_ndebug=true \  -D b_lto=true \  -D b_lto_mode=thin \  -D b_pie=true \

[+] zstd 1.5.0-1[+] libpng 1.6.37-3[+] libjpeg-turbo 2.1.0-1[+] mesa 21.1.2-1[+] pixman 0.40.0-1[-] glib2 2.68.3-1 -> 2.68.2-1[+] gtk2 2.24.33-2[+] gtk3 1:3.24.29-2[+] gtk4 1:4.2.1-2[+] qt5-base 5.15.2+kde+r196-1[+] icu 69.1-1[+] freetype2 2.10.4-1[+] pango 1:1.48.5-1[+] fontconfig 2:2.13.93-4[+] harfbuzz 2.8.1-1[+] cairo 1.17.4-5[+] wayland-protocols 1.21-1[+] egl-wayland 1.1.7-1[+] xorg-server 1.20.11-1[+] xorgproto 2021.4-1[+] xorg-xauth 1.1-2[+] xorg-util-macros 1.19.3-1[+] xorg-xkbcomp 1.4.5-1[+] xorg-setxkbmap 1.3.2-2[+] kwin 5.22.0-1[+] plasma-workspace 5.22.0-2[+] glibc 2.33-5

Сборка Ядра с помощью LLVM и Clang с LTO оптимизацией

Внимание! Сборку ядра необходимо выполнять под обычным пользователем. Перед установкой ядра у вас попросит sudo пароль. Не рекомендуется использовать патчи ядра linux-ck, linux-zen, MuQSS и т.д. Мною были протестированы все, при кажущемся увеличении производительности системы, происходят кратковременные лаги и снижается стабильность системы, некоторые подсистемы ядра работают не стабильно! С выходом ядра 5.11 стандартный планировщик работает не хуже и значительно стабильнее! Единственный патч который мною применяется это патч для применения оптимизации под процессор github.com/graysky2/kernel_gcc_patch Выбрать ваш процессор можно в меню конфигуратора ядра Processor type and features-->Processor family.

make CC=clang LD=ld.lld AR=llvm-ar NM=llvm-nm STRIP=llvm-strip \  READELF=llvm-readelf HOSTCC=clang HOSTCXX=clang++ \  HOSTAR=llvm-ar HOSTLD=ld.lld OBJCOPY=llvm-objcopy OBJDUMP=llvm-objdump

make CC=clang LD=ld.lld AR=llvm-ar NM=llvm-nm STRIP=llvm-strip \  READELF=llvm-readelf HOSTCC=clang HOSTCXX=clang++ \  HOSTAR=llvm-ar HOSTLD=ld.lld OBJCOPY=llvm-objcopy OBJDUMP=objdump

export BUILD_FLAGS="LLVM=1 LLVM_IAS=1 CC=clang CXX=clang++ LD=ld.lld AR=llvm-ar NM=llvm-nm STRIP=llvm-strip READELF=llvm-readelf HOSTCC=clang HOSTCXX=clang++ HOSTAR=llvm-ar HOSTLD=ld.lld OBJCOPY=llvm-objcopy OBJDUMP=objdump"make ${BUILD_FLAGS} -j$(nproc)

export BUILD_FLAGS="LLVM=1 LLVM_IAS=1 CC=clang CXX=clang++ LD=ld.lld AR=llvm-ar NM=llvm-nm STRIP=llvm-strip READELF=llvm-readelf HOSTCC=clang HOSTCXX=clang++ HOSTAR=llvm-ar HOSTLD=ld.lld OBJCOPY=llvm-objcopy OBJDUMP=objdump"tar -xf linux-5.12.10.tar.xz -C /tmpcd /tmp/linux-5.12.10zcat /proc/config.gz > .config # Берем конфигурацию запущенного ядра из /proc/config.gz и используем ее для сборкиecho "-mykernel" > .scmversionmake ${BUILD_FLAGS} oldconfigmake ${BUILD_FLAGS} -j$(nproc) nconfig

make ${BUILD_FLAGS} -j$(nproc)make ${BUILD_FLAGS} -j$(nproc) modulessudo make ${BUILD_FLAGS} -j$(nproc) modules_installsudo cp -v arch/x86_64/boot/bzImage /boot/vmlinuz-mykernel

sudo ${BUILD_FLAGS} dkms install ${dkms_module} -k 5.12.10-mykernel

Автоматизация сборки ядра Linux

KERNEL_VERSION='5.12.10'         # Версия Linux для сборки. Любая версия с официального сайта kernel.org, включая rc версии.KERNEL_POSTFIX='noname'         # Постфикс для названия ядра. Ядро будет иметь имя версия-постфикс, 5.12.10-noname, нужно для разделения в системе ядер с одной версией.KERNEL_CONFIG='/proc/config.gz' # Конфигурационный файл ядра. Поддерживает любые текстовые файлы и с жатые с расширением gz.KERNEL_CONFIGURATOR='nconfig'   # Конфигуратор ядра nconfig, menuconfig, xconfig.# Рекомендую использовать nconfig, он лучше menuconfig.# Можно писать полную строку, например MENUCONFIG_COLOR=blackbg menuconfig# Дополнительную информацию можно найти в документации к ядру https://www.kernel.org/doc/html/latest/kbuild/kconfig.htmlMKINITCPIO=1 # Запускать "mkinitcpio -p конфигурационный_файл" После сборки? 0 - Нет, 1 - Да.MKINITCPIO_CONFIG="${KERNEL_POSTFIX}" # Имя конфигурационного файла mkinitcpio, по умолчанию равно постфиксу.CONFIGURATOR=0      # Запускать конфигуратор ядра? 0 - Нет, 1 - Да. Если вам не нужно конфигурировать ядро, то можно поставить 0.LLVM=0              # Использовать LLVM Для сборки? 1 - Да, 0 - Нет(Будет использован GCC или другой системный компилятор по умолчанию)THREADS=8           # Количество поток для сборки. Ускоряет сборку. Для автоматического определения надо заменить на $(nproc)BUILD_DIR='/tmp'    # Директория в которой будет проходить сборки ядра. У меня 32gb оперативной памяти и сборка происходит в tmpfs.DOWNLOAD_DIR=${PWD} # Директория для сохранения архивных файлов с исходниками ядра. ${PWD} - в папке из которой запущен скрипт сборки.DIST_CLEAN=0    # Если директория с исходниками существует выполнять make disclean перед сборкой? 0 - Нет, 1 - ДаCLEAN_SOURCE=0  # Выполнять make clean после сборки ядра? 0 - Нет, 1 - ДаREMOVE_SOURCE=1 # Удалять директорию с исходными файлами ядра после сборки? 0 - Нет, 1 - Да.SYSTEM_MAP=0    # Копировать System.map в /boot После сборки? 0 - Нет, 1 - Да.PATCH_SOURCE=1                          # Применять патчи ядра? 0 - Нет, 1 - Да.PATCHES=("${HOME}/confstore/gcc.patch") # Список патчей ядра. Нельзя поменять с помощью параметров скрипта.DKMS_INSTALL=1                                        # Выполнять DKMS Install? 0 - Нет, 1 - Да.DKMS_UNINSTALL=1                                      # Выполнять DKMS Uninstall? 0 - Нет, 1 - Да.DKMS_MODULES=('openrazer-driver/3.0.1' 'digimend/10') # Список DKMS модулей, который нужно собрать и установить. Нельзя поменять с помощью параметров скрипта.

Внимание! Сборку ядра необходимо выполнять под обычным пользователем. Перед установкой ядра у вас попросит sudo пароль. Не рекомендуется использовать патчи ядра linux-ck, linux-zen, MuQSS и т.д. Мною были протестированы все, при кажущемся увеличении производительности системы, происходят кратковременные лаги и снижается стабильность системы, некоторые подсистемы ядра работают не стабильно. С выходом ядра 5.11 стандартный планировщик работает не хуже и значительно стабильнее! Единственный патч который мною применяется это патч для применения оптимизации под процессор github.com/graysky2/kernel_gcc_patch. Нас интересует файл more-uarches-for-kernel-5.8+.patch. Путь к нему имеет смысл указать в PATCHES. Выбрать ваш процессор можно в меню конфигуратора ядра Processor type and features-->Processor family.

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

Представьте, что у вас есть большой проект на С или С++ (или даже С#), который разрабатывался много лет и многими людьми. В результате разные части проекта выглядят по-разному нет единого стиля имен переменных, функций, типов данных. То есть в разных частях проекта использовался разный coding style: где-то имена в верхнем регистре, где-то CamelCase, где-то с префиксами, в других местах без Некрасиво, в общем.

И вот вы собрались навести порядок, начав, например, с имен переменных. Решили, что все имена должны быть в верхнем регистре и с префиксом по типу данных (так называемая Венгерская нотация).

Вот такое, например, переименование:

Тут некоторые наверняка подумали: Ну, и в чем проблема? Автозамена же поможет. В крайнем случае скрипт на Python на коленке запилить

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

Значит, автозамена не подходит. Пишем скрипт на коленке. С областями видимости разобраться не сложно. Но, представляете, переменным, функциям и даже типам данных иногда позволено иметь одинаковые имена. То есть реально, вот такая конструкция вполне себе законна (правда, только в GNU C):

typedef int Something;int main(){    int Something(Something Something)    {        return Something + Something;    }    printf("This is Something %d!\n", Something(10));    return 0;}

C:\HelloWorld.exeThis is Something 20!

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

Абстрактное Синтаксическое Дерево (Abstract Syntax Tree, AST) это, по сути, ваш исходный код, разобранный на мельчайшие атомы, то есть переменные, константы, функции, типы данных и т.д., которые уложены в направленный граф.

typedef int SomeNumber;int SomeFunction(SomeNumber num){    return num + num;}int main(){       printf("This is some number = %d!\n", SomeFunction(10));    return 0;}

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

Где растут деревья?

Поскольку мы рассматриваем проект на С (или С++), то первым делом вспоминается великий и могучий GNU Compiler Collection, он же GCC.

Front-end в GCC для своих собственных нужд генерирует AST дерево и позволяет экспортировать его для дальнейшего использования. Это, в принципе, удобно для ручного анализа кода изнутри, но если мы задаемся целью делать автоматические исправления в самом коде, то в данном случае все остальное для этого нам придется написать самим.

Не менее могучий LLVM/clang также умеет экспортировать AST, но этот проект пошел еще дальше и предложил уже готовый инструмент для разбора и анализа дерева Clang-Tidy. Это инструмент 3-в-1 он генерирует дерево, анализирует его и выполняет проверки, а также автоматически вносит исправления в код там, где это нужно.

Что также важно для нас это Open Source проект с доступным исходным кодом, в который легко добавить свои новые функции, если вдруг там чего-то не хватает.

Лес рубят щепки летят

Для того, чтобы исследовать AST дерево своего проекта, нам понадобится Clang. Если у вас его еще нет, то готовую сборку можно скачать на странице проекта LLVM: https://clang.llvm.org/

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

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

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

Эта команда выдаст все AST дерево сразу:

clang -c -Xclang -ast-dump <filename.c>

Вы наверняка удивитесь, насколько оно огромное. Для моего примера Hello World выше, из 7 строк кода, дерево получилось в 6259 строк. Это потому, что в нем будет также все, что было подключено из стандартных заголовочных файлов: типы данных, функции и т.д.

Поиск чего-то нужного в таком огромном массиве информации может вызвать уныние, поэтому удобнее использовать команду clang-query для извлечения только нужной информации. Запросы пишутся с использованием специального синтаксиса AST Matchers, который описывается вот тут

Например, следующий запрос выдаст нам весь внутренний мир функции с именем SomeFunction:

clang-query> set output dumpclang-query> match functionDecl(hasName("SomeFunction"))Match #1:Binding for "root":FunctionDecl 0x195581994f0 <C:\HelloWorld.c:5:1, line:8:1> line:5:5 used SomeFunction 'int (SomeNumber)'|-ParmVarDecl 0x19558199420 <col:18, col:29> col:29 used num 'SomeNumber':'int'`-CompoundStmt 0x19558199638 <line:6:1, line:8:1>  `-ReturnStmt 0x19558199628 <line:7:2, col:15>    `-BinaryOperator 0x19558199608 <col:9, col:15> 'int' '+'      |-ImplicitCastExpr 0x195581995d8 <col:9> 'SomeNumber':'int' <LValueToRValue>      | `-DeclRefExpr 0x19558199598 <col:9> 'SomeNumber':'int' lvalue ParmVar 0x19558199420 'num' 'SomeNumber':'int'      `-ImplicitCastExpr 0x195581995f0 <col:15> 'SomeNumber':'int' <LValueToRValue>        `-DeclRefExpr 0x195581995b8 <col:15> 'SomeNumber':'int' lvalue ParmVar 0x19558199420 'num' 'SomeNumber':'int'1 match.

Ну, и давайте попробуем запустить сам Clang-Tidy, из спортивного интереса:

C:\clang-tidy HelloWorld.c -checks=* --C:\HelloWorld.c:12:53: warning: 10 is a magic number; consider replacing it with a named constant [cppcoreguidelines-avoid-magic-numbers]        printf("This is some number = %d!\n", SomeFunction(10));                                                           ^C:\HelloWorld.c:12:53: warning: 10 is a magic number; consider replacing it with a named constant [readability-magic-numbers]

Работает! И даже встроенные чекеры подают признаки жизни.

Пристегнитесь крепче начинаем кодировать!

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

Первым делом нам нужны исходники LLVM. Да, прямо вот весь проект LLVM, огромный, отсюда: репозиторий

Еще понадобится cmake, вот здесь

Удобство проектов, написанных с использованием cmake, заключается в том, что можно автоматически сгенерировать проект для нескольких разных сред разработки. У меня, например, Visual Studio 2019 для Windows, поэтому мой алгоритм получения рабочего проекта выглядит так:

git clone https://github.com/llvm/llvm-project.git
cd llvm-project
mkdir build
cd build
cmake -DLLVM_ENABLE_PROJECTS='clang;clang-tools-extra' -G 'Visual Studio 16 2019' -A x64 -Thost=x64 ../llvm

После этих шагов будет сгенерирован LLVM.sln, который можно открывать в Visual Studio и собирать нужные компоненты. Минимальный набор: сам clang-tidy и clang-apply-replacements. Если времени не жалко совсем, то можно построить и весь LLVM, но в целом этого не требуется для нашей задачи.

Интересующие нас исходники находятся в llvm\clang-tools-extra\clang-tidy. Здесь можно посмотреть на примеры других чекеров, то есть модулей в Clang-Tidy для выполнения различных проверок. Они сгруппированы по нескольким категориям, таким как readability, portability, performance и т.д. Их назначение, в принципе, понятно из названия. Здесь же есть скрипт, который поможет нам сгенерировать заготовку для своего чекера:

python add_new_check.py misc ultra-cool-variable-renamer

Здесь misc это категория, в которую мы определили наш чекер, а ultra-cool-variable-renamer это имя нашего чекера.

Скрипт-генератор создаст несколько новых файлов, в том числе для документации и тестов. Но нам на данном шаге интересны только два, в папке misc: UltraCoolVariableRenamer.h и UltraCoolVariableRenamer.cpp

Важный момент: поскольку наш проект для Visual Studio был сгенерирован с помощью cmake, то новые файлы сами по себе в проект не попадут. Для этого нужно перезапустить cmake еще раз, и он обновит проект автоматически.

Собираем и запускаем Clang-Tidy. Видим, что наш чекер появился и показывает сообщения из
сгенерированного чекера-заготовки, радуемся этому:

C:\clang-tidy HelloWorld.c -header-filter=.* -checks=-*,misc-ultra-cool-variable-renamer 354 warnings generated.C:\HelloWorld.c:5:5: warning: function 'SomeFunction' is insufficiently awesome [misc-ultra-cool-variable-renamer]int SomeFunction(SomeNumber num)    ^C:\HelloWorld.c:5:5: note: insert 'awesome'int SomeFunction(SomeNumber num)    ^    awesome_C:\HelloWorld.c:10:5: warning: function 'main' is insufficiently awesome [misc-ultra-cool-variable-renamer]int main()    ^C:\HelloWorld.c:10:5: note: insert 'awesome'int main()    ^    awesome_

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

Если посмотреть на код самого чекера, то мы увидим что он состоит из всего двух методов: registerMatchers() и check().

void UltraCoolVariableRenamerCheck::registerMatchers(MatchFinder* Finder) {  // FIXME: Add matchers.  Finder->addMatcher(functionDecl().bind("x"), this);}void UltraCoolVariableRenamerCheck::check(const MatchFinder::MatchResult& Result) {  // FIXME: Add callback implementation.  const auto* MatchedDecl = Result.Nodes.getNodeAs<FunctionDecl>("x");  if (MatchedDecl->getName().startswith("awesome_"))    return;  diag(MatchedDecl->getLocation(), "function %0 is insufficiently awesome")    << MatchedDecl;  diag(MatchedDecl->getLocation(), "insert 'awesome'", DiagnosticIDs::Note)    << FixItHint::CreateInsertion(MatchedDecl->getLocation(), "awesome_");}

Метод registerMatchers()вызывается один раз, при старте Clang-Tidy, и нужен для того, чтобы добавить правила для отлова нужных нам мест в AST дереве. При этом здесь применяется такой же синтаксис AST matchers, как мы использовали раньше в clang-query. Затем для каждого срабатывания зарегистрированного правила будет вызван метод check().

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

  auto VariableDeclaration = varDecl();  Finder->addMatcher(VariableDeclaration.bind("variable_declaration"), this);  auto VariableReference = declRefExpr(to(varDecl()));  Finder->addMatcher(VariableReference.bind("variable_reference"), this);

Поскольку мы хотим переименовать переменные не только в месте их объявления, но и везде, где они используются, нам нужно зарегистрировать два правила. Обратите внимание на то, что для регистрации правила нужно использовать тот тип объекта из AST дерева, который мы хотим обработать. То есть varDecl для объявлений переменных и declRefExpr для ссылок на какой-либо объявленный объект. Поскольку объявленным объектом может быть не только переменная, то здесь мы применяем еще дополнительный критерий to(varDecl()), чтобы отфильтровать только ссылки на переменные.

Нам осталось написать содержимое метода check(), который будет проверять имя переменной и показывать предупреждение, если оно не соответствует используемому нами стандарту:

void UltraCoolVariableRenamerCheck::check(const MatchFinder::MatchResult& Result) {  const DeclRefExpr* VariableRef = Result.Nodes.getNodeAs<DeclRefExpr>("variable_reference");  const VarDecl* VariableDecl = Result.Nodes.getNodeAs<VarDecl>("variable_declaration");  SourceLocation location;  StringRef name;  StringRef type;  if (VariableDecl) {    location = VariableDecl->getLocation();    name = VariableDecl->getName();    type = StringRef(VariableDecl->getType().getAsString());      } else if (VariableRef) {    location = VariableRef->getLocation();    name = VariableRef->getDecl()->getName();    type = StringRef(VariableRef->getDecl()->getType().getAsString());  } else {    return;  }  if (!checkVarName(name, type)) {       diag(location, "variable '%0' does not comply with the coding style")        << name;  }}

Что здесь происходит: метод check() может быть вызван как для объявления переменной, так и для ее использования. Обрабатываем оба этих варианта. Дальше функция checkVarName() (оставим ее содержимое за кадром) проверяет соответствие имени переменной принятому нами стилю кодирования, и если соответствия нет, то показываем предупреждение.

Убеждаемся, что мы видим это предупреждение для всех трех мест, где встречается переменная в нашем коде:

C:\HelloWorld.c:5:29: warning: variable 'num' does not comply with the coding style [misc-ultra-cool-variable-renamer]int SomeFunction(SomeNumber num)                            ^C:\HelloWorld.c:7:9: warning: variable 'num' does not comply with the coding style [misc-ultra-cool-variable-renamer]        return num + num;               ^C:\HelloWorld.c:7:15: warning: variable 'num' does not comply with the coding style [misc-ultra-cool-variable-renamer]        return num + num;                     ^

Больше трюков добавляем исправление

На самом деле, мы уже почти все сделали. Чтобы Clang-Tidy не только показывал предупреждения, но и сам вносил исправления, нам осталось добавить пару строчек для того, чтобы описать, как именно и что нужно исправить.

Давайте напишем функцию generateVarName(StringRef oldVarName, StringRef varType), которая будет переводить прежнее имя переменной в верхний регистр и, в зависимости от типа данных, добавлять к ней префикс (примитивное содержимое этой функции также оставим за скобками).

Все, что нам осталось, это добавить в вывод diag правило замены, указав, где нужно заменить и на что:

  if (!checkVarName(name, type)) {       diag(location, "variable '%0' does not comply with the coding style")        << name       << type;      diag(location, "replace to '%0'", DiagnosticIDs::Note)        << generateVarName(name, type)        << FixItHint::CreateReplacement(location, generateVarName(name, type));  }

Теперь, если мы запустим Clang-Tidy еще раз, то увидим не только сообщения о неправильных именах, но и предложенные исправления. А если запустим его с ключом -fix, то эти исправления будут автоматически внесены в исходный код.

C:\HelloWorld.c:5:29: warning: variable 'num' does not comply with the coding style [misc-ultra-cool-variable-renamer]int SomeFunction(SomeNumber num)                            ^C:\HelloWorld.c:5:29: note: replace to 'snNUM'int SomeFunction(SomeNumber num)                            ^~~                            'snNUM'C:\HelloWorld.c:7:9: warning: variable 'num' does not comply with the coding style [misc-ultra-cool-variable-renamer]        return num + num;               ^C:\HelloWorld.c:7:9: note: replace to 'snNUM'        return num + num;               ^~~               'snNUM'C:\HelloWorld.c:7:15: warning: variable 'num' does not comply with the coding style [misc-ultra-cool-variable-renamer]        return num + num;                     ^C:\HelloWorld.c:7:15: note: replace to 'snNUM'        return num + num;                     ^~~                     'snNUM'

Итак, мы сделали автоматическое исправление всех переменных в нашем проекте, написав меньше 100 строчек кода. Да, этот пример примитивный, он не учитывает многих особенностей и на любом более-менее крупном проекте из коробки не заработает и все сломает Чтобы такое переименование заработало везде и хорошо, придется еще попотеть. И все же это вполне рабочий прототип, поверх которого можно добавлять ту логику, которую вы захотите.

Бочку мёда видим, где же дёготь?

Что ж, метод хорош, но как же без ограничений? Главное ограничение исходит из самой идеи использования синтаксического дерева: в поле зрения попадет и будет обработано только то, что есть в дереве. То, что в дерево не попало, останется без изменений.

Почему вдруг это может быть плохо?

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

  
  

  #if ARCH==ARMdo_something();#elif ARCH==MIPSdo_something_else();#endif
  

  
  

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

  
  

• То, что не является исходным кодом, тоже не попадет в дерево. То есть комментарии в исходниках останутся нетронутыми. Если у вас в комментариях упоминаются ваши переменные или функции, то придется вам их обновлять вручную. Еще можно попробовать автоматизировать это внешними средствами, используя информацию о переименованиях, которую Clang-Tidy умеет экспортировать.

  
  

• Не так все просто с макросами. Они обрабатываются предпроцессором еще до того, как запускается сама компиляция. Это означает, что для правильного переименования символов, которые взаимодействуют с макросами, нужно будет предпринимать дополнительные усилия. Также макросы не присутствуют в AST дереве, хотя возможность их обнаружения и переименования имеется для этого нужно использовать PPCallbacks.

  
  

Как глубока кроличья нора?

С простой задачей разобрались, а что насчет сложных? К этому моменту у вас наверняка возникло много вопросов: насколько умным может быть чекер, что вообще можно им сделать и где черпать идеи?

Прежде всего, с помощью Clang-Tidy можно сделать практически любой анализ и любые манипуляции с исходным кодом. В примере выше мы разобрали работу с переменными как самый простой случай. Однако функции, константы, классы, типы данных и все остальное, из чего состоит код, также разбирается на атомы в AST дереве и также доступно в Clang-Tidy.

В качестве отправной точки для изучения того, какие задачи можно решать с помощью Clang-Tidy и как это можно делать, я советую посмотреть на исходный код других чекеров, который находится там же, в папке с исходниками Clang-Tidy. Это отличное дополнение к официальной документации LLVM, которая, честно говоря, не блещет многословием. Особенно интересно подсмотреть, как сделаны чекеры от Google.

Напоследок хочется пожелать никогда не сдаваться, проявлять изобретательность и фантазию, и конечно удачи!

• Ядра операционных систем, например, Linux.
• Микроконтроллеры
• Видеокодеки
• Общие низкоуровневые библиотеки наподобие OpenSSL
• Инструменты командной строки Unix наподобие ls, cat и git

Go и Rust демонстрируют потенциал

LLVM: недостающий кусок пазла

• Zig, который я довольно подробно описывал здесь.
• Odin замена C, во многом похожий на Go.
• Язык V. Ещё один C-подобный язык, разработчики которого сильно вдохновлялись Go и Rust.

Что такое язык на замену C?

• Простота использования уже имеющихся библиотек C. Ada, Modula-2 и прочие провалились в основном потому, что их нельзя эффективно использовать с огромной экосистемой C.
• Создание языка на основе устоявшихся знаний и договорённостей. Go очень быстро набирает популярность, потому что, несмотря на некоторые изменения синтаксиса, API и способ кодинга очень знакомы программисту на C.
• Нет сборки мусора/ручное управление памятью. C доминирует в областях, где требуется тщательный контроль над использованием памяти. В эту нишу сборка мусора просто не уместится. Именно это помешало Go полностью заменить C.
• Малый размер получающихся двоичных файлов. Как и C, Zig, например, позволяет создавать очень маленькие двоичные файлы. Если вы хотите создать альтернативный язык для сферы встроенных устройств, то нельзя взять язык наподобие Go, создающий большие двоичные файлы.
• Дружественность на уровне систем. Требуется возможность манипулирования битами и байтами. Нужны хорошие бинарные операторы и указатели. Во многих языках, появившихся за последние десятилетия, нет нужной реализации указателей. В Java слово указатель превратилось в ругательство, но в Go они частично вернулись.
• Постепенная замена кода на C. Наличие превосходной двоичной совместимости с C.

Вывод

На правах рекламы

В этой статье мы попробуем разобраться с одним из самых неоднозначных и непонятных нововведений стандарта C++17 функцией стандартной библиотеки std::launder. Мы посмотрим на std::launder с другой стороны, посмотрим на источник. Разберем что лежит в основе функции на примере решения задачи девиртуализации и реализации виртуальных указателей в LLVM.

Девиртуализация это крайне важная оптимизация компилятора, которая позволяет заменить виртуальные (dynamic, indirect) вызовы обычными (static, direct). Виртуальные вызовы приводят к снижению производительности, не могут быть встроены, имеют более сложные механизмы спекулятивного выполнения (Indirect branch prediction), которые могут приводить к снижению безопасности и служить вектором атаки (например, Spectre). Clang и LLVM обеспечивают полную девиртуализацию виртуальных вызовов, когда удается статически определить динамический тип объекта или определить отсутствие переопределения метода и устраняют избыточную загрузку динамической информации (виртуальных таблиц) во всех остальных случаях.

Виртуальный вызов

Виртуальные вызовы реализуют концепцию, которая часто называется динамической диспетчеризацией (dynamic dispatch). Динамическая диспетчеризация это механизм, позволяющий выбрать реализацию полиморфного метода на основе динамического (фактического) типа объекта во время выполнения программы. По умолчанию вызовы методов выполняются в рамках статической диспетчеризации т.е. на основе статического типа известного во время компиляции. Спецификатор virtual у метода позволяет сменить тип диспетчеризации.

В выражение вида E1.E2, например, вызов метода a->foo() или a.foo(), выражение E1 называется object expression. Динамический тип в данном контексте это тип объекта, на который ссылается текущее значение выражения E1.

struct A{    int foo() { return 1; }    // объявление метода с virtual меняет статическую диспетчеризацию на динамическую.    virtual int bar() { return 1; }};struct B : A{    int foo() { return 2; }    int bar() override { return 2; }};int main(){    B b;    A *a = &b;    // вызов A::foo() на основе статического типа а    const int v1 = a->foo();    // вызов B::foo() на основе динамического (фактического) типа а.    // динамический тип это тип объекта, на который ссылается указатель а.    // в данном случае, это объект типа B.    const int v2 = a->bar();    assert(v1 == 1);    assert(v2 == 2);}

Стандарт не регулирует каким именно образом должен быть реализован механизм динамической диспетчеризации. Все современные компиляторы C++ реализуют динамическую диспетчеризацию и виртуальные вызовы с помощью специальных структур: виртуальных таблиц (virtual table, vtable, vtbl).

Виртуальные таблицы

Виртуальные таблицы генерируются для каждого класса с виртуальными методами или виртуальными базовыми классами. Во время создания экземпляра такого класса, адрес соответствующей таблицы записывается в специальное техническое поле: виртуальный указатель (virtual pointer). Виртуальных указателей может быть несколько, для каждого базового класса. При этом под адресом виртуальной таблицы т.е. адрес, который будет записан в виртуальный указатель экземпляра класса, не всегда понимается адрес начала таблицы. В терминах ABI этот адрес называется address point. Доступ ко всем записям таблицы осуществляется фиксированными смещениями, как положительными, так и отрицательными, относительно этого адреса.

Виртуальные таблицы содержат следующую информацию:

1. Virtual call offsets. Записи содержат смещения для корректировки указателя (this) от виртуального базового класса до класса-потомка. Используются для вызова переопределенного в классе-потомке метода виртуального базового класса.
2. Virtual base offsets. Записи содержат смешения от адреса поля виртуального указателя до адреса подобъекта виртуального базового класса. Добавляется для каждого виртуального базового класса.
3. Offset to top. Запись содержит смешение от адреса поля виртуального указателя до адреса начала объекта т.е. адреса первого байта. Смещение позволяет найти начало объекта из любого базового подобъекта с помощью виртуального указателя.
4. Typeinfo pointer. Запись содержит адрес объекта с данными о типе RTTI.
5. Virtual function pointers. Записи содержат адреса виртуальных методов класса или адреса вторичных точек входа (thunk). Используются для динамической диспетчеризации. Реализация таких указателей определяется конкретным ABI. Последовательность записей совпадает с последовательностью объявлений соответствующих методов в классах. Все записи в таблицах иерархии совместимых классов находятся в согласованном состояние т.е. для каждого виртуального метода в дереве наследования имеется одно, фиксированное смещение в таблице. Если дочерний класс перегружает реализацию базового метода, то в таблице этого класса меняется соответствующая запись на адрес перегруженного метода. Такая таблица совместима с таблицей базового класса.

Например, для иерархии классов:

struct A{    void s();    virtual void f();    virtual void g();};struct B : A{    void f() override;    virtual void h();};struct C{    virtual void k();};struct D : A, C{    void g() override;    void k() override;};

Будут сгенерированы следующие таблицы (x86-64 clang 10.0.0):

# виртуальная таблица для класса Аvtable for A:    .quad 0                # Смещение Offset To Top    .quad typeinfo for A   # адрес объекта typeinfo с данными о типе RTTI    .quad A::f()           # адрес базовой реализации метода f()    .quad A::g()           # адрес базовой реализации метода g()# виртуальная таблица для класса Bvtable for B:    .quad 0                # Смещение Offset To Top    .quad typeinfo for B   # адрес объекта typeinfo с данными о типе RTTI    .quad B::f()           # адрес переопределенного метода f()    .quad A::g()           # адрес базовой реализации метода g()    .quad B::h()           # адрес метода h()# виртуальная таблица для класса Cvtable for C:    .quad 0                # Смещение Offset To Top    .quad typeinfo for C   # адрес объекта typeinfo с данными о типе RTTI    .quad C::k()           # адрес базовой реализации метода k()# виртуальная таблица для класса D# состоит из двух таблиц,# одна совместима с виртуальной таблицей B, другая с виртуальной таблицей Cvtable for D:    #                        Cовместимая с B таблица    .quad 0                # Смещение Offset To Top    .quad typeinfo for D   # адрес объекта typeinfo с данными о типе RTTI    .quad A::f()           # адрес базовой реализации метода f()    .quad D::g()           # адрес переопределенного метода g()    .quad D::k()           # адрес переопределенного метода k()    #                        Cовместимая с С таблица    .quad -8               # Смещение Offset To Top    .quad typeinfo for D   # адрес объекта typeinfo с данными о типе RTTI    .quad thunk for D::k() # вторичная точка входа для переопределенного метода D::k()

Можно заметить, что записи о виртуальных методах в таблицах совместимы, например, метод f() имеет одно и тоже смещение во всех таблицах совместимых типов (А, B, D).

Класс D использует множественное наследование с несколькими базовыми классами: A и C. Объект типа D содержит два виртуальных указателя. Один принадлежит базовому подобъекту A и указывает на таблицу совместимую с таблицей класса A, другой принадлежит базовому подобъекту C и содержит адрес таблицы совместимой с виртуальной таблицей класса C.

Чтобы понять почему в таблице совместимой с классом С вместо указателя на метод D::k() помещен thunk for D::k(), рассмотрим следующий код:

D *d = new D;A *a = dynamic_cast<A*>(d);C *c = dynamic_cast<C*>(d);c->k();

Если посмотреть на адреса d, a, c и this в методе k(), то они будут, например, такими

d:    0x1edcee0a:    0x1edcee0c:    0x1edcee8this: 0x1edcee0

Адреса d, а, this совпадают, а адрес с смещен на 8 байт относительно d. Так происходит из-за того, что в памяти базовый подобъект C смещен на 8 байт из-за технического поля (виртуального указателя) базового подобъекта A. Поэтому при вызове, мы не можем передать c в качестве this в метод k(). Перед вызовом this должен быть скорректирован, чтобы указывать на объект класса, который выполнил переопределение метода. Именно эту корректировку и делает thunk перед передачей управления методу k().

Таким образом, вторичная точка входа thunk это сегмент кода ассоциированный с целевым методом, который выполняет определенные корректировки входных параметров (например, this) перед передачей управления методу. Thunk может содержать просто дополнительную инcтрукцию, которая будет выполнена до перехода к целевому методу или быть полноценной функцией со своим стековым кадром и дальнейшим полноценным вызовом метода. Используется при множественном наследовании.

Ассоциация виртуальных таблиц

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

void test(A *a){    a->s();    a->f();    a->f();    a->g();}int main(){    A *a = new B;    test(a);}

Будет сгенерирован следующий код (x86-64 clang 10.0.0):

# виртуальная таблица для класса Аvtable for A:    .quad 0    .quad typeinfo for A    .quad A::f()   # address point    .quad A::g()# виртуальная таблица для класса Bvtable for B:    .quad 0    .quad typeinfo for B    .quad B::f()   # address point    .quad A::g()    .quad B::h()main:    push    rbx    mov     edi, 8    # new expression    # вызов оператора new    call    operator new(unsigned long)    mov     rbx, rax    mov     rdi, rax    # вызов конструктора B    call    B::B() [base object constructor]    mov     rdi, rbx    call    test(A*)    xor     eax, eax    pop     rbx    ret# конструктор класса BB::B() [base object constructor]:    push    rbx    mov     rbx, rdi    # вызов конструктора базового класса A    call    A::A() [base object constructor]    # сохраняем адрес виртуальной таблицы (address point) класса B    # переписываем значение сохраненное в конструкторе базового класса    # 16 - это смещение до address point таблицы B    mov     qword ptr [rbx], offset vtable for B+16    pop     rbx    ret# конструктор класса AA::A() [base object constructor]:    # сохраняем адрес виртуальной таблицы (address point) класса A    # 16 - это смещение до address point таблицы A    mov     qword ptr [rdi], offset vtable for A+16    ret

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

Вызов виртуального метода

В общем случае виртуальный вызов состоит из следующих шагов:

1. Прочитать адрес виртуальной таблицы из виртуального указателя;
2. Сместить значение загруженного указателя до записи в таблице с адресом вызываемого метода;
3. Прочитать адрес метода;
4. Выполнить косвенный вызов по прочитанному адресу.

Без каких-либо оптимизаций, эти шаги выполняются при каждом виртуальном вызове, независимо от контекста, например, при вызове в цикле.

Сгенерированный код функции test() из предыдущего примера (x86-64 clang 10.0.0 -std=c++17 -O1):

test(A*):    push    rbx    mov     rbx, rdi    # вызов a->e()    # прямой вызов метода по фиксированному адресу, статическая диспетчеризация,    # тип известен на этапе компиляции    call    A::e()    # вызов a->f()    # читаем виртуальный указатель, хранит    # адрес записи в виртуальной таблице с адресом метода f()    mov     rax, qword ptr [rbx]    # читаем адрес f() из таблицы и выполняем косвенный вызов метода    call    qword ptr [rax]    # еще один вызов a->f()    # читаем виртуальный указатель, хранит    # адрес записи в виртуальной таблице с адресом метода в f()    mov     rax, qword ptr [rbx]    mov     rdi, rbx    # читаем адрес f() из таблицы и выполняем косвенный вызов метода    call    qword ptr [rax]    # вызов a->g()    # читаем виртуальный указатель, хранит    # адрес записи в виртуальной таблице с адресом метода в f()    mov     rax, qword ptr [rbx]    mov     rdi, rbx    # смещаем на следующую запись относительно f(): adress point + 8    # запись содержит адрес метода g()    # читаем адрес g() из таблицы и выполняем косвенный вызов метода    call    qword ptr [rax + 8]    pop     rbx    ret

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

Девиртуализация может быть выполнена на разных уровнях:

1. Front-end. На уровне конкретного языка, эксплуатируя конкретные языковые особенности;
2. Middle-end. На уровне промежуточного представления, в нашем случае LLVM IR, до этапа генерации кода.

Front-end. Девиртуализация на уровне C++

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

Динамический тип совпадает со статическим

struct A{    virtual void f();};struct B : A{    void f() override;};void test(){    B a;    a.f();    a.f();}

По стандарту, вызов a.f() также является виртуальным. Любой вызов виртуального метода является виртуальным, исключая вызовы с явно квалифицированным именем метода. Т.е. вызов a.A::f() выполняется в рамках статической диспетчеризации.

Напомним, что в выражении вида E1.E2, например, вызов метода a.f(), динамический тип это тип объекта, на который ссылается значение выражения E1 (object expression). Значение выражения в данном случае, является сам объект а, т.е. динамический и статический тип совпадают. Поэтому мы можем просто заменить косвенный вызов на прямой.

Будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O0):

test():    push    rbp    mov     rbp, rsp    sub     rsp, 16    lea     rdi, [rbp - 8]    call    B::B() [base object constructor]    lea     rdi, [rbp - 8]    # прямой вызов B::f()    call    B::f()    lea     rdi, [rbp - 8]    # прямой вызов B::f()    call    B::f()    add     rsp, 16    pop     rbp    ret

Вызов виртуальных методов в конструкторе/деструкторе

struct A{    A()    {        f();    }    virtual ~A()    {        f();    }    virtual void f();};struct B : A{    B()    {        f();    }    ~B()    {        f();    }    void f() override;};

Поcмотрим еще раз на генерируемый код и на порядок инициализации виртуального указателя в конструкторе/деструкторе.

# конструктор класса AA::A() [base object constructor]:    push    rax    # сохраняем адрес виртуальной таблицы для класса А    mov     qword ptr [rdi], offset vtable for A+16    # прямой вызов A::f();    call    A::f()    pop     rax    ret# деструктор класса AA::~A() [base object destructor]:    push    rax    # сохраняем адрес виртуальной таблицы для класса А    mov     qword ptr [rdi], offset vtable for A+16    # прямой вызов A::f()    call    A::f()    pop     rax    ret# конструктор класса BB::B() [base object constructor]:    push    rbx    mov     rbx, rdi    # вызов конструктора базового класса    call    A::A() [base object constructor]    # сохраняем адрес виртуальной таблицы для класса B    mov     qword ptr [rbx], offset vtable for B+16    mov     rdi, rbx    # прямой вызов B::f()    call    B::f()    pop     rbx    ret# деструктор класса BB::~B() [base object destructor]:    push    rbx    mov     rbx, rdi    # сохраняем адрес виртуальной таблицы для класса B    mov     qword ptr [rdi], offset vtable for B+16    # прямой вызов B::()    call    B::f()    mov     rdi, rbx    # вызов деструктора базового класса    call    A::~A() [base object destructor]    pop     rbx    ret

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

На front-end'е эту оптимизацию делают GCC и MSVC. Clang оставляет эту задачу LLVM. LLVM оптимизирует эти вызовы с помощью store to load propagation (в конструкторе/деструкторе видны запись и чтение виртуального указателя) в рамках прохода GVN (Global Value Numbering).

Локализация класса в юните трансляции

namespace{    struct A    {        virtual int f() { return 1; }    };}int test(A *a){    return a->f();}

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

Финализация класса/метода

struct A{    virtual int f() final;    virtual int g();};struct B final : A{    int g() override;};void test(A *a, B *b){    a->f();    a->g();    b->g();}

Сгенерированный код (x86-64 clang 10.0.0 -std=c++17 -O0):

test(A*, B*):    push    rbp    mov     rbp, rsp    sub     rsp, 32    mov     qword ptr [rbp - 8], rdi    mov     qword ptr [rbp - 16], rsi    mov     rdi, qword ptr [rbp - 8]    # прямой вызов A::f(),    # метод f() финализирован в классе А и не может быть переопределен    call    A::f()    mov     rcx, qword ptr [rbp - 8]    mov     rdx, qword ptr [rcx]    mov     rdi, rcx    mov     dword ptr [rbp - 20], eax    # косвенный вызов метода g(),     # т.к. может существовать класс-потомок переопределяющий метод    call    qword ptr [rdx + 8]    mov     rdi, qword ptr [rbp - 16]    mov     dword ptr [rbp - 24], eax    # прямой вызов B::g(), т.к. класс B финализирован    call    B::g()    add     rsp, 32    pop     rbp    ret

Middle-end. Девиртуализация на уровне промежуточного представления

Рассмотрим небольшой пример, чтобы понять на чем оcнован традиционный подход к девиртуализации:

struct A{    virtual void f();};struct B : A{    void f() override;};void test(){    A *a = new B;    a->f();}

Для девиртуализации метода, компилятору нужно знать три вещи:

1. Значение виртуального указателя. Адрес конкретной виртуальной таблицы. Т.е. по сути, компилятор должен видеть значение, которое записывается в виртуальный указатель в конструкторе.
2. Адрес конкретного метода. Т.к. виртуальные таблицы константны: генерируются для каждого типа в момент компиляции и не могут меняться во время выполнения, то для получения адреса метода из таблицы, наблюдая значение виртуального указателя (конкретную таблицу), нам достаточно просто определения этой таблицы (virtual table definition).
3. Компилятор должен быть уверен, что с момента инициализации виртуального указателя (записи значения) в конструкторе и до момента вызова конкретного виртуального метода т.е. чтения виртуального указателя, его значение не переписывается (no clobbering).

Если все эти условия соблюдены, то компилятор может выполнить store to load propagation на виртуальном указателе и заменить виртуальный вызов прямым. Здесь важно понимать, что это оптимизация на уровне промежуточного представления (target-independed optimization) и код обрабатывается без какой-либо семантической нагрузки из C++.

Например, выше мы рассматривали вызов виртуального метода в конструкторе. Там все условия соблюдаются, поэтому Clang/LLVM выполнят девиртуализацию таких вызовов.

Для функции test после всех оптимизаций в IR будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O2):

test():    push    rax    mov     edi, 8    call    operator new(unsigned long)    # заинлайненый конструктор объекта B    # сохранение адреса виртуальной таблицы в виртуальный указатель    mov     qword ptr [rax], offset vtable for B+16    mov     rdi, rax    pop     rax    # прямой вызов f()    jmp     B::f()

В этом подходе есть ряд ограничений.

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

Для функции test будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O2 -fno-inline):

test():    push    rbx    mov     edi, 8    call    operator new(unsigned long)    mov     rbx, rax    mov     rdi, rax    # внешний конструктор    call    B::B() [base object constructor]    mov     rax, qword ptr [rbx]    mov     rdi, rbx    pop     rbx    # косвенный вызов f()    jmp     qword ptr [rax]B::B() [base object constructor]:    push    rbx    mov     rbx, rdi    call    A::A() [base object constructor]    mov     qword ptr [rbx], offset vtable for B+16    pop     rbx    ret

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

Вторая проблема заключается в отслеживании инварианта виртуального указателя. Следует отметить, что ни каких дополнительных знаний о виртуальном указателе у компилятора нет и отслеживание состояния сводится к отслеживанию инструкций записи. Эта задача лежит на модуле Alias Analysis (Pointer Analysis). Это набор алгоритмов, с помощью которых модуль в общем случае пытается определить: могут ли два указателя ссылаться на один и тот же объект в памяти. Для поиска предшествующих операций с памятью, от которых зависит заданная инструкция, LLVM может использовать интерфейс MemDep (Memory Dependence Analysis) или более эффективный MemSSA (Memory SSA). Одно из основных положение такого анализа это отслеживание: выходит ли указатель за пределы функции или юнита трансляции т.е. обращаются ли к памяти со стороны или мы работаем с памятью локально. Для локальной обработки алгоритмы могут достаточно точно определить какие указатели могут указывать на объект и соответственно какие инструкции этот объект меняют. В случае выхода указателя за пределы анализатор предполагает, что память может быть перезаписана.

Дополним пример выше:

struct A{    virtual void f();};struct B : A{    void f() override;};void test(){    A *a = new B;    a->f();    // второй вызов виртуального метода,     // компилятор не видит определение метода f()    a->f();}void foo(A *a);void test1(){    A *a = new B;    // вызов внешней функции и передача указателя    foo(a);    a->f();}

Будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O2):

test():    push    rbx    mov     edi, 8    call    operator new(unsigned long)    mov     rbx, rax    mov     qword ptr [rax], offset vtable for B+16    mov     rdi, rax    # прямой вызов метода f()    call    B::f()    mov     rax, qword ptr [rbx]    mov     rdi, rbx    pop     rbx    # косвенный вызов метода f()    jmp     qword ptr [rax]test1():    push    rbx    mov     edi, 8    call    operator new(unsigned long)    mov     rbx, rax    # встроенный конструктор    mov     qword ptr [rax], offset vtable for B+16    mov     rdi, rax    # вызов внешней функции    call    foo(A*)    mov     rax, qword ptr [rbx]    mov     rdi, rbx    pop     rbx    # косвенный вызов метода f()    jmp     qword ptr [rax]

Второй вызов метода f() в функции test() не будет оптимизирован. Так происходит потому, что анализатор не знает что на самом деле делает метод f() и у него нет другой альтернативы кроме как предположить худший вариант: представление объекта, на который указывает а может поменяться, смениться динамический тип и соответственно значение виртуального указателя. Аналогичная ситуация с функцией test1() и вызовом foo(a). Еще раз заметим, что с точки зрения LLVM виртуальный указатель это просто указатель с адресом, как любой другой. Ни какой семантики из C++ на него не наложено.

Ключевой вопрос здесь, каким образом мы может изменить динамический тип объекта и значение виртуального указателя в C++?

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

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

Существование объекта можно разделить на следующие этапы:

1. Память под объект была выделана, время жизни объекта еще не началось;
2. Процесс создания объекта (constructor);
3. Существование объекта;
4. Процесс уничтожения объекта (destructor);
5. Время жизни объекта закончилось, память или переиспользуется другим объектом или освобождена.

Если указатель ссылается на выделенную память, но процесс создания объекта еще не начался или указатель ссылается на объект, время жизни которого уже закончилось, то на указатель накладываются следующие ограничения и нарушение хотя бы одного из этих ограничений приводит к Undefined Behavior:

• Указатель не может выступать в качестве операнда delete expression, если время жизни объекта было закончено. Исключая объекты с тривиальным деструктором;
• Указатель не может использоваться для доступа к полям и методам класса;
• Указатель не может быть приведен к указателю на виртуальный базовый класс;
• Указатель не может выступать в качестве операнда static_cast. Исключая приведение к void* и/или дальнейшее приведение к char*, unsigned char* или std::byte*;
• Указатель не может выступать операндом dynamic_cast.

Т.е. каждое из этих условий требует доступ к объекту, который еще не был создан или уже был удален.

Здесь есть важное замечание. Если после завершения времени жизни объекта мы переиспользуем память и вновь созданный объект имеет заменяемый тип (transparently replaceable), то все указатели, ссылки и имена, которые ссылались на исходный объект, автоматически начинают указывать на новый и могут быть использованы для оперирования новым объектом. Два типа называются заменяемыми, в данном контексте, если выполнены следующие условия:

• Новый объект использует в точности всю память старого объекта;
• Объекты имеют одинаковый тип с точностью до cv-квалификаторов;
• Тип исходный объект не является константным и тип не содержит константных или ссылочных полей (в случае пользовательского типа данных).

Ниже мы увидим что transparently replaceable является крайне точным термином.

Вернемся к нашему примеру:

void B::f(){    // виртуальный метод класса меняет динамический тип объекта    // мы завершаем время жизни существующего объекта    // и создаем новый другого типа    new(this) A;}void test(){    A *a = new B;    a->f();    // неопределенное поведение    a->f();}

Код метода B::f(), с точки зрения описанных выше правил, корректен, но т.к. типы исходного и нового объектов не заменяемы, то все существующие указатели (включая this) мы можем использовать только ограниченным образом, т.е. только как указатели на область памяти, а не как указатели на конкретные объекты. Как следствие, второй вызов метода a->f() приводит к неопределенному поведению, т.к. указатель a ссылается на объект, чье время жизни было закончено.

Для полноты описания так же заметим, что placement new возвращает указатель, который может быть использован для манипулирования новым объектом.

Например:

void B::f(){    // виртуальный метод класса меняет динамический тип объекта    // мы завершаем время жизни существующего объекта    // и создаем новый, другого типа    A *a = new(this) A;    // a может может использоваться для доступа к методам и полям нового объекта    // однако вызов g(), используя this является Undefined Behavior,    // при этом this и a, по умолчанию, указываю на одну и ту же область памяти    a->g();    // создаем еще один объект с исходным типом    // использование this является корректным, а    // использование указателя a для доступа к полям Undefined Behavior    new (this) B;    g();}

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

Основная сложность представления в LLVM IR описанной семантики заключается в том, что указатели ссылающиеся на один и тот же адрес могут указывать на объекты с разным временем жизни и не должны рассматриваться как эквивалентные т.е. с точки зрения оптимизатора не могут участвовать в подстановке (substitution).
Реализация Clang/LLVM позволяющая выразить семантику выше, время жизни динамических объектов и инварианты виртуальных указателей, доступна с флагом -fstrict-vtable-pointers.

Инварианты виртуальных указателей

Мы будем рассматривать код:

struct A{    virtual void f();    virtual void g();};struct B : A{    void f() override;    void g() override;};A* get_object();void test(){    A *a = get_object();    a->f();    a->f();    a->f();    a->g();}

Используя традиционный, описанный выше, подход к девиртуализации, cо всеми оптимизациями в IR мы получим следующий код (x86-64 clang 10.0.0 -std=c++17 -O2, код немного упрощен, убраны несущественные детали, атрибуты, метаданные).

define dso_local void @test(){    ; запрос объекта    %1 = call %struct.A* @get_object()    %2 = bitcast %struct.A* %1 to void (%struct.A*)***    ; вызов метода f()    ; чтение виртуального указателя    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; чтение адреса метода f()    %4 = load void (%struct.A*)*, void (%struct.A*)** %3    ; косвенный вызов f()    call void %4(%struct.A* %1)    ; второй вызов метода f()    ; повторное чтение виртуального указателя    %5 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; повторное чтение адреса метода f()    %6 = load void (%struct.A*)*, void (%struct.A*)** %5    ; косвенный вызов f()    call void %6(%struct.A* %1)    ; третий вызов f()    ; еще одно чтение виртуального указателя    %7 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; еще одно чтение адреса метода f()    %8 = load void (%struct.A*)*, void (%struct.A*)** %7    ; косвенный вызов f()    call void %8(%struct.A* %1)    ; вызов метода g()    ; еще одно чтение виртуального указателя    %9 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; смещение адреса виртуальной таблицы до записи с адресом метода g()    %10 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %9, i64 1    ; чтение адреса метода g()    %11 = load void (%struct.A*)*, void (%struct.A*)** %10    ; косвенный вызов g()    call void %11(%struct.A* %1)}

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

LLVM расширяет список возможных метаданных инструкций чтения и записи новым элементом invariant.group. Метаданные инструкций это подсказка оптимизатору об уникальных свойствах инструкции. Наличие или отсутствие таких метаданных не меняет семантику программы.

Присутствие метаданных в инструкции invariant.group указывает оптимизатору, что чтение/запись с одним и тем же операндом или другими словами, если операнд принадлежит одной и той же инвариантной группе, возвращает/сохраняет одно и тоже значение. Чтобы выразить инвариант виртуального указателя, каждая инструкция чтения виртуального указателя (в рамках виртуального вызова) и каждая инструкция записи виртуального указателя (в рамках инициализации в конструкторе/деструкторе) сопровождается метаданными invariant.group.

Так же каждую инструкцию чтения виртуальной таблицы в процессе виртуального вызова LLVM сопровождает метаданными invariant.load. Эти метаданные указывают на то, что область памяти, на которую ссылается операнд инструкции чтения, содержит одно и тоже значение независимо от того в какой момент и где мы эти данные читаются. Это позволяет выразить тот факт, что содержимое виртуальной таблицы постоянно и в процессе выполнения меняется не может.

define dso_local void @test(){    ; запрос объекта    %1 = tail call %struct.A* @get_object()    %2 = bitcast %struct.A* %1 to void (%struct.A*)***    ; вызов метода f()    ; чтение виртуального указателя,    ; инструкция содержит метаданные invariant.group    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы,    ; инструкция содержит метаданные invariant.load    %4 = load void (%struct.A*)*, void (%struct.A*)** %3, !invariant.load !{}    tail call void %4(%struct.A* %1)    ; второй вызов метода f()    ; повторное чтение виртуального указателя, инструкция помечена invariant.group    ; оптимизатор может предположить что данные уже прочитаны в %3    %5 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы,    ; инструкция содержит метаданные invariant.load    ; оптимизатор знает что данные загружаемые инструкцией по переданному адресу    ; постоянны и не могут изменится в процессе выполнения    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}    tail call void %6(%struct.A* %1)    ; третий вызов f()    ; еще одно чтение виртуального указателя, инструкция помечена invariant.group    ; оптимизатор может предположить что данные уже прочитаны в %3    %7 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы,    ; инструкция содержит метаданные invariant.load    ; оптимизатор знает что данные загружаемые инструкцией по переданному адресу    ; постоянны и не могут изменится в процессе выполнения    %8 = load void (%struct.A*)*, void (%struct.A*)** %7, !invariant.load !{}    tail call void %8(%struct.A* %1)    ; вызов метода g()    ; еще одно чтение виртуального указателя, инструкция помечена invariant.group    ; оптимизатор может предположить что данные уже прочитаны в %3    %9 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    %10 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %9, i64 1    ; чтение адреса метода g() из виртуальной таблицы,    ; инструкция содержит метаданные !invariant.load    %11 = load void (%struct.A*)*, void (%struct.A*)** %10, !invariant.load !{}    tail call void %11(%struct.A* %1)}

Обработку этих метаданных берет на себя модуль MemDep. В итоге после оптимизации (-std=c++17 -O2 -fstrict-vtable-pointers) мы получаем следующее:

define dso_local void @test(){    ; запрос объекта    %1 = tail call %struct.A* @get_object()    %2 = bitcast %struct.A* %1 to void (%struct.A*)***    ; чтение виртуального указателя, избыточные чтения удалены    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы    %4 = load void (%struct.A*)*, void (%struct.A*)** %3, !invariant.load !{}    ; три косвенных вызова метода f()    tail call void %4(%struct.A* %1)    tail call void %4(%struct.A* %1)    tail call void %4(%struct.A* %1)    ; смещение адреса виртуальной таблицы до записи с адресом метода g()    %5 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %3, i64 1    ; чтение адреса метода g() из виртуальной таблицы,    ; виртуальный указатель уже прочитан    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}    ; косвенный вызов метода g()    tail call void %6(%struct.A* %1)}

И после генерации кода back-end'ом:

test():        push    r15        push    r14        push    rbx        call    get_object()        mov     rbx, rax        mov     rax, qword ptr [rax]        mov     r14, qword ptr [rax]        mov     r15, rax        mov     rdi, rbx        call    r14        mov     rdi, rbx        call    r14        mov     rdi, rbx        call    r14        mov     rdi, rbx        mov     rax, r15        pop     rbx        pop     r14        pop     r15        jmp     qword ptr [rax + 8]

Проблема внешнего конструктора

Проблема внешнего конструктора решается с помощью техники assumption loads. Это набор дополнительных инструкций, которые генерируются после вызова конструктора и информируют компилятор о фактическом значение виртуального указателя нового объекта. Напомним, что из-за внешнего конструктора традиционный подход к девиртуализации не справляется с вызовами.

Рассмотрим пример с отключенным инлайненгом (x86-64 clang 10.0.0 -std=c++17 -O2 -fno-inline -fstrict-vtable-pointers):

struct A{    virtual void f();};void test(){    A *a = new A;    a->f();}

define void @test(){    %1 = call dereferenceable(8) i8* @New(i64 8)    %2 = bitcast i8* %1 to %struct.A*    ; вызов конструктора объекта A::A()    call void @Constructor_A(%struct.A* nonnull %2)    %3 = bitcast i8* %1 to i8***    ; читаем адрес сохраненный в виртуальном указателе    ; важно что чтение также сопровождается метаданными invariant.group    %4 = load i8**, i8*** %3, !invariant.group !{}    ; сравниваем прочитанное значение с адресом виртуальной таблицы для класса A    %5 = icmp eq i8** %4, @VTABLE_A    ; вызываем llvm.assume и передаем результат сравнения.    call void @llvm.assume(i1 %5)    ; в итоге прямой вызов метода A::f()    call void @f(%struct.A* nonnull %2)    ret void}; конструктор класса Adefine void @Constructor_A(%struct.A* %0){    %2 = getelementptr %struct.A, %struct.A* %0, i64 0, i32 0    ; сохранение адреса виртуальной таблицы A в виртуальный указатель объекта    store i32 (...)** @VTABLE_A, i32 (...)*** %2, !invariant.group !{}    ret void}

После вызова конструктора генерируются три дополнительные инструкции:

1. Чтение виртуального указателя вновь созданного объекта. Чтение сопровождается метаданными invariant.group.
2. Сравнение загруженного адреса виртуальной таблицы с адресом предполагаемой таблицы (исходя из типа объекта);
3. Вызов и передача результата сравнения в @llvm.assume. Встроенная функция @llvm.assume не генерирует ни каких дополнительных инструкций. Семантически вызов похож на assert на уровне оптимизатора и позволяет предположить, что переданный результат сравнения всегда истинен, если условие нарушается, то дальнейшее поведение считается неопределенным.

В результате к моменту вызова у оптимизатора уже есть актуальное значение виртуального указателя: оптимизатор сделал предположение чему он равен. И вызов может быть девиртуализирован.

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

    %1 = call dereferenceable(8) i8* @New(i64 8)    %2 = bitcast i8* %1 to %struct.A*    %3 = bitcast i8* %1 to i8***    ; встроенный конструктор,    ; сохраняем адрес виртуальной таблицы в виртуальном указателе.    ; запись помечена invariant.group, это значит  что в рамках этой инвариантной группы    ; в этом виртуальном указателе может быть сохранен только @VTABLE_A    store i32 (...)** @VTABLE_A, i32 (...)*** %3, !invariant.group !{}    ; читаем адрес сохраненный в виртуальном указателе.    ; чтение сопровождается метаданными invariant.group    ; чтение принадлежит той же инвариантной группе, что и запись выше.    ; у оптимизатора уже есть информация, что по этому адресу может быть записан только @VTABLE_A    ; и чтение может быть заменено на @VTABLE_A    %4 = load i8**, i8*** %3, !invariant.group !{}    ; после оптимизации чтения это условие всегда true: @VTABLE_A == @VTABLE_A    %5 = icmp eq i8** %4, @VTABLE_A    ; вызов llvm.assume(true) можно удалить    call void @llvm.assume(i1 %5)

Барьеры оптимизации

Существует ряд семантических случаев, когда виртуальный указатель меняет свое значение:

• Конструкторы. Конструктор каждого класса в иерархии инициализирует виртуальный указатель адресом своей виртуальной таблицы;
• Деструкторы. Деструкторы каждого класса восстанавливают значение виртуального указателя для безопасного использования виртуальных методов;
• Placement new. Выражение завершает время жизни объекта (если используется тривиальный деструктор) и переиспользует выделенную под него память, создав там другой объект. В результате меняется динамический тип и соответственно значение виртуального указателя. Возвращает указатель, для доступа к новому объекту.

В рамках семантики инвариантных групп у инструкций чтения и записи нам нужны инструменты, чтобы сообщить оптимизатору, что информация об инварианте обновилась или ее не нужно учитывать. Необходимо предусмотреть случай сравнения двух указателей в рамках оптимизации. Указатели могут ссылаться на одну и туже область памяти, но на объекты с разным временем жизни. Равенство таких указателей не должна вводить в заблуждение оптимизатор: оптимизатор не должен иметь возможность выполнить подстановку (substitution). Необходимо выразить концепцию equal-but-not-equivalent.

LLVM вводит две дополнительные операции: strip и launder.

Операция strip

Операция strip может использоваться, когда нам нужен указатель на те же данные с возможностью доступа к ним, но без инвариантной информации установленной метаданными invariant.group.
Операция представлена новой встроенной функцией @llvm.strip.invariant.group. Функция возвращает новый указатель, который является псевдонимом (alias) переданному аргументу, т.е. указывает и может использоваться для доступа к той же памяти что и аргумент и убирает ассоциацию указателя с инвариантной группой.

Свойства операции:

• Операция является детерминированной и не обладает побочными эффектами. Т.е. возвращаемое значение зависит только от переданного аргумента. Такие операции часто называются чистыми (pure);
• Возвращает псевдоним аргумента (alias). Возвращает указатель, который указывает и может использоваться для доступа к той же памяти что и аргумент;
• strip(X) == strip(strip(X)). Т.к. операция не берет во внимание ассоциированные инвариантные данные.

Один из случаев использования операции strip это сравнение указателей:

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    if (a == b)        b->f();}

    ...    ; читаем адрес виртуальной таблицы а    %vtable_a = load void (%struct.A*)**, void (%struct.A*)*** %a, !invariant.group !{}    ...    ; if(a == b)    %res = icmp eq %struct.A* %a, %b    br %res, label %if, label %after    if:        ; если %b будет заменен на %a,        ; то оптимизатор заменить чтение адреса виртуальной таблицы %vtable_b        ; на уже прочитанный %vtable_a.        ; т.к. чтение сопровождается метаданными invariant.group        %vtable_b = load void (%struct.B*)**, void (%struct.B*)*** %b, !invariant.group !{}        ...    ...

Проблема в том, что LLVM основываясь на результате сравнения a и b может заменить SSA значение b на a (в проходе GVN). Это абсолютно легальная оптимизация. Но в рамках девиртуализации и обработки инвариантов, такая замена приведет к неопределенному поведению, потому что при втором вызове метода f() будет использоваться не та виртуальная таблица.

Решение заключается в сравнение указателей без учета инвариантной информации:

    ...    ; читаем адрес виртуальной таблицы a    %vtable_a = load void (%struct.A*)**, void (%struct.A*)*** %a, !invariant.group !{}    ...    ; if(a == b)    ; сравниваем указатели без инвариантов    ; strip_a и strip_b имеют доступ и указывают на ту же область,    ; на которую указывают a и b соответственно    %strip_a = call i8 * @llvm.strip.invariant.group(i8 * %a)    %strip_b = call i8 * @llvm.strip.invariant.group(i8 * %b)    %res = icmp eq %struct.A* %strip_a, %strip_b    br %res, label %if, label %after    if:        ; Равенство псевдонимов не является достаточной причиной для оптимизатора,        ; чтобы выполнить подстановку исходных указателей        %vtable_b = load void (%struct.B*)**, void (%struct.B*)*** %b, !invariant.group !{}        ...    ...

Операция launder

Операция launder используется, когда нам нужен указатель на те же данные с возможностью доступа к ним, но c очищенной информацией об инварианте.
Операция представлена новой встроенной функцией @llvm.launder.invariant.group. Функция возвращает новый указатель, который является псевдонимом (alias) переданному аргументу, т.е. указывает и может использоваться для доступа к той же памяти что и аргумент и ассоциирует указатель с новой инвариантной группой. Т.е. переданный в функцию указатель и новый указатель, в контексте обработки метаданных invariant.group на операциях чтения и записи, рассматриваются как два разных указателя.

Свойства операции:

• Операция по своей сути является недетерминированной. Ни какие два вызова не возвращают одинаковое значение;
• Возвращает псевдоним аргумента (alias). Возвращает указатель, который указывает и может использоваться для доступа к той же памяти что и аргумент;
• strip(x) == strip(launder(x)).

LLVM использует операцию launder во всех семантических случаях, когда виртуальный указатель меняет свое значение т.е. каждое новое значение виртуального указателя должно принадлежать своей инвариантной группе, это позволяет в процессе девиртуализации избежать неопределенного поведения. Также операция используется в ряде краевых случаев, таких как доступ к членам union.

В случае конструктора/деструктора, каждый класс-потомок передает в конструктор/деструктор базового класса launder(this):

; конструктор класса Adefine void @Constructor_A(%struct.A* %0){    %2 = getelementptr %struct.A, %struct.A* %0, i64 0, i32 0    ; запись адреса виртуальной таблицы A    store i32 (...)** @VTABLE_A, i32 (...)*** %2, !invariant.group, !{}    ret void}; конструктор класса Bdefine void @Constructor_B(%struct.B* %0){    %2 = bitcast %struct.B* %0 to i8*    ; запрос нового указателя с новой инвариантной группой launder(this)    %3 = call i8* @llvm.launder.invariant.group(i8* %2)    %4 = bitcast i8* %3 to %struct.A*    ; передача launder(this) в конструктор базового класса A    call void @Constructor_A(%struct.A* %4)    %5 = getelementptr %struct.B, %struct.B* %0, i64 0, i32 0, i32 0    ; запись адреса виртуальной таблицы B    store i32 (...)** @VTABLE_B, i32 (...)*** %5, !invariant.group, !{}    ret void}

Детально рассмотрим случай выражения placement new:

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    b->f();}

Если мы используем умалчиваемую реализацию оператора размещающего new, то указатель a будет побитово равен указателю b. Но в рамках объектной модели C++, a и b указывают на разные объекты: a указывает на объект типа A, время жизни которого завершено, b указывает на вновь созданный, в той же области памяти, объект типа B. Соответственно, в контексте девиртуализации вызов b->f() должен загружать правильную виртуальную таблицу: таблицу класса B и указатели a и b не должны рассматриваться как эквивалентные. С помощью операции launder оптимизатор может достичь описанной семантики.

define void @test(){    ; new expression    ; вызов оператора new    %1 = call dereferenceable(8) i8* @New(i64 8)    %2 = bitcast i8* %1 to %struct.A*    ; создание объекта типа A, вызов конструктора A    %3 = call %struct.A* @Constructor_A(%struct.A* nonnull %2)    %4 = bitcast i8* %1 to void (%struct.A*)***    ; чтение виртуального указателя созданного объекта типа A    ; т.к. чтение сопровождается метаданными invariant.group    ; для указателя регистрируется новая инвариантная группа    %5 = load void (%struct.A*)**, void (%struct.A*)*** %4, !invariant.group !{}    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}    ; косвенный вызов A::f(). После того как оптимизатор заинлайнет конструктор    ; (или сделает предположение о значение виртуального указателя, assumtion loads)    ; вызов будет девиртуализирован в прямой вызов A::f()    call void %6(%struct.A* nonnull %2)    ; placement new expression    ; создание нового указателя и    ; ассоциация его с новой инвариантной группой.    ; указатель ссылается и имеет доступ к области памяти,    ; которая была выделена ранее под объект типа A    %7 = call i8* @llvm.launder.invariant.group(i8* nonnull %1)    %8 = bitcast i8* %7 to %struct.B*    ; создание объекта типа B, вызов конструктора B    ; в конструктор передается новый указатель    ; это важно т.к. конструктор меняет значение виртуального указателя    %9 = call %struct.B* @Constructor_B(%struct.B* nonnull %8)    %10 = bitcast i8* %7 to void (%struct.B*)***    ; чтение виртуального указателя созданного объекта типа B    ; оптимизатор не сможет здесь использовать ранее загруженную таблицу для старого объекта    ; т.к. указатели принадлежат разным инвариантным группам.    %11 = load void (%struct.B*)**, void (%struct.B*)*** %10, !invariant.group !{}    %12 = load void (%struct.B*)*, void (%struct.B*)** %11, !invariant.load !{}    ; косвенный вызов B::f(). После того как оптимизатор заинлайнет конструктор    ; (или сделает предположение о значение виртуального указателя, assumtion loads)    ; вызов будет девиртуализирован в прямой вызов B::f()    call void %12(%struct.B* nonnull %8)    ret void}

Важно, что операции strip и launder возвращают псевдонимы (aliases) своих аргументов, это не дает оптимизатору выполнить неверную подстановку, но дает возможность делать предположения о значение, не позволяя подавлять существующие оптимизации. Вызовы соответствующих функций удаляются перед фазой генерации кода back-end'ом и не несут нагрузки на выполнение и размер объектного кода.

std::launder

Если посмотреть более внимательно на последний пример использования операции launder с placement new, то можно заметить, что на уровне LLVM IR, указатель b это не что иное, как launder(a). И семантика выражения размещающего new сводится к следующему:

1. Запрос нового указателя вызовом функции @llvm.launder.invariant.group на основе переданного аргумента.
2. Создание нового объекта в заданной области памяти: вызов конструктора. В нашем случае переиспользование памяти завершает время жизни, существующего в переданной области памяти, объекта. В конструктор передается новый указатель, т.к. конструктор меняет значение виртуального указателя (та же семантика, что и при вызове конструктора базового класса). В итоге новый указатель ссылается на новый объект со своим значением виртуального указателя и ассоциирован с "чистой" (новой) инвариантной группой. Этот указатель рассматривается как результат вычисления выражения placement new.

Вернемся к коду и к уже упомянутому состоянию Undefined Behavior:

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    // определенное поведение    b->f();    // неопределенное поведение    a->f();}

На состояния Undefined Behavior можно смотреть как на компромисс, договоренность между программистом и компилятором. Это набор дополнительных правил и ограничений, позволяющий компилятору генерировать более эффективный код. В нашем случае оптимизатор эксплуатирует объектную модель C++ и описанное неопределенное поведение, что бы реализовать девиртуализацию методов. Если девиртуализация не используется, то второй вызов a->f() будет иметь ожидаемое поведение: косвенный вызов B::f(). Но с описанной моделью девиртуализации, вызов a->f() будет оптимизирован в прямой вызов A::f(). Вызов b->f() всегда имеет ожидаемой поведение, т.к. указатель учитывает состояние инварианта и не позволяет оптимизатору выполнить подстановку (substitution), т.е. использовать, прочитанные для исходного объекта, данные в рамках вновь созданного объекта.

Операция launder позволяет правильно оперировать инвариантными группами в рамках девиртуализации. С++ дает возможность принудительно генерировать вызов операции в промежуточном представление.

Вызов std::launder это принудительная (ручная) генерация вызова функции @llvm.launder.invariant.group в IR. Точная реализация на стороне IR зависит от настройки компиляции и обрабатываемого типа. Если мы не используем описанную модель девиртуализации (флаг -fstrict-vtable-pointers) или обрабатываем не полиморфный тип, то в IR просто генерируется алиасный указатель.

Таким образом, исходя из семантики выражения placement new эти две реализации функции test генерируют один и тот же код и не приводят к неопределенному поведению:

void test(){    A *a = new A;    a->f();    new(a) B;    std::launder(a)->f();}

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    b->f();}

Использование std::launder

Мотивирующий пример из стандарта:

struct X{    const int n;};void test(){    X *p = new X{1};    const int a = p->n;    X *p1 = new (p) X{2};    // определенное поведение    const int b = p1->n;    // неопределенное поведение, значение p->n может быть 1.    const int c = p->n;    // определенное поведение    const int d = std::launder(p)->n;}

Выше мы описывали, что такое заменяемый тип (transparently replaceable) в терминах объектной модели C++. После переиспользования памяти, все имена, ссылки и указатели ссылающиеся на исходный объект, станут автоматически указывать на вновь созданный объект, только если типы исходного и нового объекта являются заменяемыми.

В этом примере как и в примере с девиртуализацией неопределенное поведение обусловлено тем, что типы не являются заменяемыми, из-за наличия константных полей. Это дает возможность оптимизатору предположить, что динамический тип объекта измениться не может и значение константного поля не меняется. Поэтому значение поля n можно прочитать только один раз и заменить все дальнейшие чтения этого поля через данный указатель на прочитанное значение. Ситуация аналогичная чтению виртуального указателя. Указатели p1 или std::launder(p) должны учитывать состояние инвариантов и не позволять оптимизатору выполнить подстановку (substitution), т.е. использовать, прочитанные для исходного объекта, данные (значение a) в рамках вновь созданного.

Более абстрактно семантику std::launder можно свести к следующему:

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

Из определения этой семантики можно сделать следующие выводы:

• std::launder не оказывает ни какого эффекта, если аргумент не указывает на объект, время жизни которого закончилось, после переиспользования памяти.
• В области памяти, на который ссылается аргумент функции, должeн существовать новый объект, который переиспользует память.

Ограничения на использование ссылок и констант в таком контексте было введено еще в C++03 3.8 7. Но, на данный момент ни один из популярных компиляторов (GCC, Clang, MSVC) не эксплуатирует это неопределенное поведение. Следует отметить только компилятор IBM XL, который выполняет подобную оптимизацию константных полей, но только в ограниченных случаях:

struct A{    const int x;    int y;};// оптимизация выполняется только для static storage durationA a = { 42, 0 };void foo();int test(){    // внешняя функция, компилятор не видит определения    foo();    // чтение a.х заменяется на 42    return a.x;}

Причин, почему компиляторы не делают такую const/reference оптимизацию несколько. До введения функции std::launder избежать неопределенного поведения можно было только использовав возвращаемое значение placement new. Но, на практике, не всегда легко это сделать, например:

template <typename T>union Storage{    constexpr Storage(T &&v)        : value(std::forward<T>(v))    {}    unsigned char dummy;    T value;};template <typename T>struct SimpleOptional{    constexpr SimpleOptional(T&& v)        : storage{std::forward<T>(v)}    {}    template <typename... Args>    void emplace(Args&&... args)    {        storage.value.~T();        ::new (&storage.value) T{std::forward<Args>(args)...};    }    constexpr const T& operator*() const    {        // чтение значение может привести к неопределенному поведению        // после переиспользования памяти        return storage.value;    }private:    Storage<T> storage;};struct A{    const int x;    int y;}void test(){    SimpleOptional<A> so = A{1, 0.5f};    const int n = (*so).x;    so.emplace(2, 0.4f);    // неопределенное поведение, x может быть равен 1 или 2    const int n1 = (*so).x;}

В данном случае, чтобы избежать неопределенного поведения придется отдельно хранить результат выражения placement new.

Более интересный пример это стандартные аллокаторы. Точнее метод construct, который используя placement new, возвращает void. Такой интерфейс аллокаторов приводит к неопределенному поведению при использование стандартных контейнеров, например, std::vector с элементами содержащими константные или ссылочные поля. Заметим, что до С++11 использование таких типов в стандартных контейнерах было невозможно. С приходом C++11 и move-семантики этого ограничение не стало.

Пример использования в контейнере:

template <typename T, typename A = std::allocator<T>>class vector{public:    using allocator_traits = typename std::allocator_traits<A>;    using pointer = typename allocator_traits::pointer pointer;    ...public:    ...    void push_back(const T& value)    {        // reserve        ...        // вызов std::allocator::construct,        // использование placement new и игнорирование возвращаемого значения        allocator_traits::construct(allocator, end, value);        ++end;    }    T& operator[] (size_t i)    {        // чтение значение может приводит к неопределенному поведению        // после переиспользования памяти в случае нарушения требований         // к заменяемым типам        return begin[i];    }    ...private:    pointer begin;    pointer end;    A allocator;    size_t capacity;};struct A{    const int x;    int y;};void test(){    vector<X> c;    c.push_back(X{1});    c.clear();    c.push_back(X{2});    // неопределенное поведение    assert(c[0].x == 2);}

Использование std::launder в общем случае так же не может решить проблему с использованием стандартных аллокаторов:

...    using pointer = typename allacoter_traits::pointer pointer;...    T& operator[] (size_t i)    {        // тип pointer в общем случае может не быть указателем        // в этом случае мы не можем использовать std::launder        return std::launder(begin)[i];    }

В результате использование стандартных аллокаторов с пользовательскими типами, содержащими константные или ссылочные поля и стандартных контейнеров будет приводить к неопределенному поведению. Эта одна из причин, почему начиная с C++17 метод construct помечен как deprecated и удален в C++20. И в конечном итоге в C++20 изменили требования к заменяемым типам, убрав ограничение на наличие константных и ссылочных подобъектов в пользовательских типах данных RU007. Поэтому пример выше формально больше не приводит к неопределенному поведению.

Заключение

К счастью, стандарт языка C++ не разрабатывается в вакууме. Автор std::launder и связанных с ним изменений является также тех.лидом в Clang и одним из авторов новой модели девиртуализации. Новые требования и std::launder хорошо ложатся в архитектуру Clang, чего нельзя сказать о GCC. В GCC эта фича до сих пор носит статус экспериментальной и не во всех случаях работает правильно. Например, Bug 95349.

Буду рад комментариям и предложениям (можно по почте yegorov.alex@gmail.com)
Спасибо!

Декораторы одна из самых необычных особенностей Python. Это инструмент, который полноценно может существовать только в динамически типизированном, интерпретируемом языке. В первой части статьи мой товарищ Witcher136 показал, как в С++ реализовать наиболее приближенную к эталонной (питоновской) версию декораторов.

Я же расскажу про то, как решил попытаться реализовать декораторы в компилируемом языке программирования, для чего в итоге написал написал собственный небольшой компилятор на Haskell на основе LLVM.

Оглавление

1. Как работают декораторы в Python
2. Haskell и LLVM собственный компилятор
3. Так как же скомпилировать декоратор?

Как работают декораторы в Python

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

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

Как работают декораторы в Python, в общем-то интуитивно понятно любому человеку, знакомому с этим языком:

Функции decorator, принимающей другую функцию как свой аргумент func, в момент применения декоратора в качестве данного аргумента передается декорируемая функция old. Результатом является новая функция new и с этого момента она привязывается к имени old

def decorator(func):    def new(*args, **kwargs):        print('Hey!')        return func(*args, **kwargs)    return new@decoratordef old():    pass# old() выведет "Hey!" - к имени old теперь приязан вызов new

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

Проблема 1. Декораторы это просто функции

Декораторы применяются в рантайме. В примере выше значение decorator может меняться вплоть до самого его использования, например вот так:

name = input('Введите имя декоратора')def first(func):    ...  # тело декоратораdef second (func):    ...  # тело декоратораif name == 'first':    decorator = firstelif name == 'second':    decorator = secondelse:    decorator = lambda f: f   # оставляем функцию в покое@decorator def old():    pass

С точки зрения нашего умозрительного компилятора, значение функции old может поменяться на что угодно в процессе выполнения программы. В некоторых языках (например, C++) замыкания реализованы так, что даже при одинаковой сигнатуре они будут разного типа (из-за разницы в захваченном ими окружении), что не позволит провернуть такой трюк. В Python же каждое замыкание носит всё свое окружение с собой в питоне всё, включая функции, это объекты, так что замыкания "могут себе это позволить", тем более потребление памяти и быстродействие не являются приоритетом для этого языка.

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

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

Проблема 2. Python мало интересуют типы

def decorator(func):    def two_args(x, y):        ...    return two_args@decoratordef one_arg(x):    ...

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

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

Это также подводит нас к обратной проблеме какой тип должен быть у аргумента декоратора в наших примерах это аргумент с названием func? Чаще всего этот аргумент, представляющий декорируемую функцию, вызвается внутри замыкания значит нам хотелось бы знать хотя бы тип возвращаемого значения, не говоря уже об аргументах. Если мы его строго зафиксируем с помощью объявления func как функции типа A, мы ограничили область применения декоратора функциями типа A. Если же мы и это объявляем как void* func, и предлагаем программисту самому везде приводить нужные типы, то проще писать на питоне.

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

Подведем итоги. Реализация декораторов в компилируемом языке создает следующие сложности:

• Тип декорируемой функции какие аргументы принимает декоратор?
• Тип итоговой функции какая сигнатура должна быть у результата работы декоратора?
• Применение на этапе компиляции создает дополнительные ограничения, применение в рантайме уменьшает гарантии, которые компилятор может дать относительно результата (либо требует продвинутой системы типов)

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

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

Про этот компилятор я и расскажу далее.

Haskell и LLVM собственный компилятор

Для создания компилятора я выбрал Haskell, как язык для написания фронтенда, и LLVM в качестве компиляторного бэкенда. Для Haskell есть замечательная библиотека llvm-hs, предоставляющая все необходимые биндинги к LLVM. В поставку самого языка также входит библиотека Parsec, предназначенная для создания парсеров, путем комбинации различных парсер-функций этой библиотеки (я думаю, что на этом моменте читатель догадался, что Parsec сокращение от parser combinators).

Я опущу описание синтаксиса получившегося языка, который я окрестил Grit, и всех его тривиальных деталей (язык достаточн похож на Си, чтоб не требовать лишних пояснений, по крайней мере по части синтаксиса) остановимся подробно только на интересных его особенностях. Исходный код компилятора можно найти здесь.

Grit expression-oriented (фразированный) язык

Любое выражение в Grit, будь то сложение, блок кода или if-else, возвращает результат, который можно использовать внутри любого другого выражения например, присвоить переменной или передать функции как аргумент.

int main() = {    int i = 0;    i = i + if(someFunction() > 0) {        1;    }    else {        0;    };};

В данном примере, i будет равен 1, если функция someFunction вернет положительное значение, и нулю, если вернется 0 или меньше.

Нет ключевого слова return

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

Это обсуловлено тем, что язык фразированный тело функции это блок кода, который является валидным выражением Grit, а значит он уже должен возвращать значение я решил, что разумнее всего сделать этим значением результат последнего выражения в блоке. А ключевое слово returns, описанное в примерах ниже просто синтаксический сахар, эквивалентный выражению переменная; в конце блока.

Обратите внимание, что поскольку блок кода является выражением, то тело функции как бы "присваивается" ей же после объявления сигнатуры функции идет знак "равно", затем блок кода и в конце точка с запятой такой же синтаксис, как у обычной операции присваивания.

int simple(int x) = {    /*       Данная фукция вернет результат сложения      своего аргумента x и переменной y    */    int y = someOtherFunction();    x + y;};/*  Для функций, состоящих из одного выражения, фигурные скобки можно опустить.  Эта функция вернет свой аргумент, увеличенный на единицу*/int incr(int x) = x + 1;int main() returns statusCode {    /*      В объявлении функции с помощью ключевого слова returns      можно указать название переменной, значение которой      будет возвращено после окончания работы функции.      Это переменная будет "объявлена" автоматически      с таким же типом, как у возвращаемого значения функции    */    int statusCode = 0;    int result = someFunction();    if (someFunction < 0) {        statusCode = 1;    };};

Auto компилятор Grit обладает базовой возможностью выведения типов

В языке Grit есть ключевое слово auto, означающее, что тип переменной (или функции) должен быть выведен автоматически.

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

auto half (int x) = x / 2;   // для функции incr будет выведен тип float

Фразированность (expression-oriented), отсутствие return из произвольного места (тело функции тоже выражение) и базовое выведение типов это самые интересные для нас особенности Grit. Я выделил их потому, что они напрямую используются в реализации декораторов в этом языке.

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

А для нас теперь пришло время наконец ответить на главный вопрос этой серии статей как скомпилировать декоратор?

Так как же скомпилировать декоратор?

Как было указано ранее, при разработке декораторов для компилируемого языка программирования, нужно определиться с двумя вещами будут они применяться в runtime или compile-time, и как определять типы аргументов и результата итоговой функции.

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

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

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

@auto flatten = {    auto result = @target;    if (result < 0) {        0;    }    else {         result;    };};

Это декоратор, который вызовет исходную функцию, и вернет 0, если ее результат меньше 0, иначе он вернет результат без изменений.

@auto flatten объявление декоратора с именем flatten и типом @auto то есть тип будет выведен в зависимости от функции, к которой он применен (@ указатель но то, что это объявление декоратора, а не функции).

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

Вы наверняка уже обратили внимание на необычную метку в теле декоратора @target. Это указание компилятору на то, что в это место надо вставить целиком тело декорируемой функции. Аргументы функции будут скопированы как аргументы для данного инстанса декоратора (что на уровне синтаксического дерева превращает его в новую функцию), а блок кода, являющийся телом исходной функции, вернет свой результат в место вызова, поскольку язык фразированный (этот механизм был описан ранее).
Таким образом, подобное изменение AST эквивалентно вызову исходной функции на месте @target, с правильными аргументами. После этого, исходную функцию можно просто заменить получившейся новой функцией, и все декоратор применен. Если же декораторов у функции несколько, то этот процесс можно повторять несколько раз.

@auto lockFunction = {    mutex.lock();    @target};

@auto optional = if (checkCondition()) {    @target;}else {    someDefaultValue;};

Рассмотрим этот механизм на примере сгенерированного компилятором Grit синтаксического дерева для простой программы с декораторами:

@auto flatten = {    auto result = @target;    if (result < 0) {        0;    }    else {         result;    };};@flattenint incr(int x) = x+1;

Здесь уже рассмотренный нами декоратор flatten применяется к функции, увеличивающей свой аргумент на единицу.

Так выглядит "сырое" внутреннее представление, до какой-либо обработки вообще:

Decorator "flatten" auto {  BinaryOp = (Def auto "result") (DecoratorTarget)  If (BinaryOp < (Var "result") (Int 0)) {    Int 0  }  else {    Var "result"  }}Function "incr" int ; args [Def int "x"] ; modifiers [Decorator "flatten"] ; returns Nothing {  BinaryOp + (Var "x") (Int 1)}

Не вдаваясь в конкретные обозначения, сразу видно две вещи определение декоратора это самостоятельная конструкция с типом Decorator, и функция incr на данном этапе существует в своем исходном виде, и хранит информацию о том что к ней применен модификатор Decorator "flatten". В теле декоратора же мы видим метку DecoratorTarget сюда будет вставленно тело функции incr.

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

Посмотрим на аннотированное, полностью обработанное и готовое к кодогенерации предсавление той же программы:

Function (int -> int) incr ["x"] {  BinaryOp i= (Def int "result") (    Block int {      BinaryOp i+ (Var int "x") (int 1)    }  )  If int (BinaryOp b< (Var int "result") (int 0)) {    int 0  }  else {    Var int "result"  }}

Здесь мы можем заметить несколько важных вещей:

• Определение декоратора было удалено после его применения на этапе обработки AST, он больше не нужен.
• Тело функции incr изменилось теперь оно такое же, каким было тело декоратора flatten, но на месте DecoratorTarget теперь Block {...} выражение вида "блок кода", совпадающее с исходным телом функции. Внутри этого выражения есть обращения к аргументам функции, и оно возвращает то же значение, которое вернула бы исходная функция это значение присваивается новой переменной int "result", с которой декоратор и работает дальше. BinaryOp i= это операция присваивания int-а, но в исходном коде тип result был указан как auto значит тип возвращаемого значения и переменных в теле функции, работающих с ним, был выведен правильно.

Таким образом, в процессе разработки этого компилятора, удалось вывести общий алгоритм применения декораторов для компилируемого, статически типизированного языка. Он не обладает всеми возможностями декораторов в Python, но приближается к ним настолько, насколько это возможно в таком языке, как Grit.

Разумеется, это не окончательная и не идеальная версия например, таким декораторам можно было бы добавить собственные, декораторные аргументы:

@auto lockF(mutex M) {    M.lock();    @target;};@lockF(мьютексКоторыйФункцияДолжнаЗахватить)int someFunction(...)

Это вполне сработало бы при текущем подходе самый простой вариант это при применении декоратора убрать аргумент mutex M, и в теле конкретного инстанса декоратора заменить обращения к этому аргументу обращениями к "мьютексКоторыйФункцияДолжнаЗахватить", который должен существовать в области видимости декорируемой функции исходя из объявления (кстати, такой способ создавать декораторы с аргументами выглядит гораздо привлекательнее того, как они реализованы в Python замыкание внутри замыкания внутри функции).

Кроме того, я экспереминтировал с меткой @args, дающей внутри декоратора доступ к аргументам целевой функции, и так же разварачивающейся в "обычный код" на этапе обработки синтаксического дерева. Например, @args.length количество аргументов, @args.1 ссылка на первый аргумент и так далее. Что-то из этого работает, что-то пока не совсем но принципиально сделать это возможно.

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

Код получившегося компилятора можно найти здесь, собирается он с помощью stack

P.S. Это был очень интересный и необычный для меня опыт надеюсь, что и вы смогли вынести для себя что-нибудь полезное из этого рассказа. Если нужна отдельная статья про написание компилятора на Haskell на основе LLVM пишите в комментарии.
На любые вопросы постараюсь ответить в комментариях, или в телеграмме @nu11_pointer_exception

int sum(int count){  int result = 0;  for (int j = 0; j < count; ++j)    result += j*j;  return result;}

sum(int):        test    edi, edi        jle     .LBB0_1        lea     eax, [rdi - 1]        lea     ecx, [rdi - 2]        imul    rcx, rax        lea     eax, [rdi - 3]        imul    rax, rcx        shr     rax        imul    eax, eax, 1431655766        add     eax, edi        shr     rcx        lea     ecx, [rcx + 2*rcx]        lea     eax, [rax + rcx]        add     eax, -1        ret.LBB0_1:        xor     eax, eax        ret

Анализ циклов скалярное развёртывание

void foo(int m, int *p){  for (int j = 0; j < m; j++)    *p++ = j;}

void foo(int m, int k, int *p){  for (int j = 0; < m; j++)    *p++ = j*j*j - 2*j*j + k*j + 7;}

void foo(int m, int k, int *p){  int t0 = 7;  int t1 = k-1;  int t2 = 2;  for (int j = 0; j < m; j++) {    *p++ = t0;    t0 = t0 + t1;    t1 = t1 + t2;    t2 = t2 + 6;  }}

void foo(int m, int k, int *p){  for (int j = 0; < m; j++)    *p++ = k*j + 7;}

Рекуррентные цепи

Построение реккурентных цепей

for (int j = 0; j < count; ++j)  result += j*j;

Выполняем оптимизации

int sum(int count){  int result = 0;  if (count > 0) {    int j = 0;    do {      result = result + j*j;      ++j;    } while (j < count);  }  return result;}

define i32 @sum(i32) {%2 = icmp sgt i32 %0, 0br i1 %2, label %3, label %6; <label>:3:br label %8; <label>:4:%5 = phi i32 [ %12, %8 ] br label %6; <label>:6:%7 = phi i32 [ 0, %1 ], [ %5, %4 ] ret i32 %7; <label>:8:%9 = phi i32 [ %13, %8 ], [ 0, %3 ]     ; {0,+,1}%10 = phi i32 [ %12, %8 ], [ 0, %3 ]    ; {0,+,0,+,1,+,2}%11 = mul nsw i32 %9, %9                ; {0,+,1,+,2}%12 = add nuw nsw i32 %11, %10          ; {0,+,1,+,3,+,2}%13 = add nuw nsw i32 %9, 1             ; {1,+,1}%14 = icmp slt i32 %13, %0br i1 %14, label %8, label %4}

result = count-1 + 3*(count-1)*(count-2)/2 + (count-1)*(count-2)(count-3)/3;

%4 = add i32 %0, -1  %5 = zext i32 %4 to i33  %6 = add i32 %0, -2  %7 = zext i32 %6 to i33  %8 = mul i33 %5, %7  %9 = add i32 %0, -3  %10 = zext i32 %9 to i33  %11 = mul i33 %8, %10  %12 = lshr i33 %11, 1  %13 = trunc i33 %12 to i32  %14 = mul i32 %13, 1431655766  %15 = add i32 %14, %0  %16 = lshr i33 %8, 1  %17 = trunc i33 %16 to i32  %18 = mul i32 %17, 3  %19 = add i32 %15, %18  %20 = add i32 %19, -1

sum(int):        test    edi, edi        jle     .LBB0_1        lea     eax, [rdi - 1]        lea     ecx, [rdi - 2]        imul    rcx, rax        lea     eax, [rdi - 3]        imul    rax, rcx        shr     rax        imul    eax, eax, 1431655766        add     eax, edi        shr     rcx        lea     ecx, [rcx + 2*rcx]        lea     eax, [rax + rcx]        add     eax, -1        ret.LBB0_1:        xor     eax, eax        ret

Производительность

int sum(int count){  int result = 0;  for (int j = 0; j < count; ++j)    result += j*j*j*j*j*j;  return result;}

/* Do not emit expensive expressions.  The rationale is that   when someone writes a code like   while (n > 45) n -= 45;   he probably knows that n is not large, and does not want it   to be turned into n %= 45.  */|| expression_expensive_p (def))

Литература:

#include <cstdio>int main() {  struct A;  printf("%zu\n", sizeof( void(A::*)() ));}

16

struct A;typedef void (A::*Ptr) ();Ptr ptr;void call(A *a) {  (a->*ptr)();}

clang++ code.cpp -c -emit-llvm -S -O3 -fno-discard-value-names

@ptr = dso_local local_unnamed_addr global { i64, i64 } zeroinitializer, align 8; Function Attrs: uwtabledefine dso_local void @_Z4callP1A(%struct.A* %a) local_unnamed_addr #0 {entry:  %.unpack = load i64, i64* getelementptr inbounds ({ i64, i64 }, { i64, i64 }* @ptr, i64 0, i32 0), align 8, !tbaa !2  %.unpack1 = load i64, i64* getelementptr inbounds ({ i64, i64 }, { i64, i64 }* @ptr, i64 0, i32 1), align 8, !tbaa !2  %0 = bitcast %struct.A* %a to i8*  %1 = getelementptr inbounds i8, i8* %0, i64 %.unpack1  %this.adjusted = bitcast i8* %1 to %struct.A*  %2 = and i64 %.unpack, 1  %memptr.isvirtual.not = icmp eq i64 %2, 0  br i1 %memptr.isvirtual.not, label %memptr.nonvirtual, label %memptr.virtualmemptr.virtual:                                   ; preds = %entry  %3 = bitcast %struct.A* %this.adjusted to i8**  %vtable = load i8*, i8** %3, align 1, !tbaa !5  %4 = add i64 %.unpack, -1  %5 = getelementptr i8, i8* %vtable, i64 %4, !nosanitize !7  %6 = bitcast i8* %5 to void (%struct.A*)**, !nosanitize !7  %memptr.virtualfn = load void (%struct.A*)*, void (%struct.A*)** %6, align 8, !nosanitize !7  br label %memptr.endmemptr.nonvirtual:                                ; preds = %entry  %memptr.nonvirtualfn = inttoptr i64 %.unpack to void (%struct.A*)*  br label %memptr.endmemptr.end:                                       ; preds = %memptr.nonvirtual, %memptr.virtual  %7 = phi void (%struct.A*)* [ %memptr.virtualfn, %memptr.virtual ], [ %memptr.nonvirtualfn, %memptr.nonvirtual ]  tail call void %7(%struct.A* %this.adjusted)  ret void}

• Взглянув на первую строчку, видно что указатель на метод является структурой `{ i64, i64 }`, а не обычным указателем. Эта структура содержит два i64 элемента, которые могут уместить в себя 2 обычных указателя. Видно почему мы не можем приводить указатели на методы в обычные. Мы не можем без потерь преобразовать 16 байт в 8 байт в общем случае.
• В блоке `entry`, начинающимся с 5 строки, видно что происходит корректирование указателя `this`. Это значит, что компилятор прибавляет к указателю на `this` значение второго элемента этой структуры, и позже в блоке `memptr.end` передает его в вызов метода.
• Нечто странное происходит происходит в блоке `entry` на 14 строке с первым элементом структуры. Компилятор вычисляет выражение аналогичное следующему: `bool isvirtual = val & 1`. Компилятор считает указатель на метод виртуальным, если число в нем нечетное, в противном случае невиртуальным.
• Если указатель на метод указывает на невиртуальный метод, то значение первого элемента считается обычным указателем на функцию, который позже вызывается. Эти предположения происходят в блоке `memptr.nonvirtual`.
• Если указатель на метод указывает на виртуальный метод, то тут сложнее. Вначале вычитается единица из первого элемента структуры, и вычисленное значение является отступом для виртуальной таблицы, указатель на которую берется из значения указателя на `this`. Это происходит в блоке `memptr.virtual`.

• Информацию является ли он виртуальным
• Указатель на адрес метода (если не виртуальный)
• Смещение в vtable (если виртуальный)
• корректирование `this`

A *a;a->method_name(1, 2, 3);method_name(a, 1, 2, 3);

struct A {  char a[123];};struct B {  char a[0];  void foo();  static void bar(B *arg);};struct C : A, B {};void (C::*a)() = &C::foo;void (C::*b)() = &B::foo;void (B::*c)() = &B::foo;void (*a1)(C*) = &C::bar; // errorvoid (*b1)(C*) = &B::bar; // errorvoid (*c1)(B*) = &B::bar; // ok

struct A {  char a[123];};struct B {  char a[0];  void foo();  static void bar(B *arg);};struct C : A, B {};void (C::*a)() = &C::foo;void (C::*b)() = &B::foo;void (B::*c)() = &B::foo;

clang++ code.cpp -c -emit-llvm -S -O3 -fno-discard-value-names

@a = dso_local global { i64, i64 } { i64 ptrtoint (void (%struct.B*)* @_ZN1B3fooEv to i64), i64 123 }, align 8@b = dso_local global { i64, i64 } { i64 ptrtoint (void (%struct.B*)* @_ZN1B3fooEv to i64), i64 123 }, align 8@c = dso_local global { i64, i64 } { i64 ptrtoint (void (%struct.B*)* @_ZN1B3fooEv to i64), i64 0 }, align 8

• Размер указателя относительно большой, даже если корректирование отсутствует каким либо образом в gcc и clang
• Каждый раз идет проверка виртуальности метода, даже если мы знаем что он не виртуальный

• Использовать статический метод, принимающий экземпляр класса
• Забыть про существование указателей на методы, и решить проблему как-то иначе в прочих случаях

• В интернете есть советы использовать std::bind, std::function и подобные библиотечные функции. Проверив их поведение, я не обнаружил существования каких либо оптимизаций для указателей на методы.
• У меня нет технической возможности проверить что происходит в компиляторах Microsoft, поэтому не особо про них рассказал. Однако протестировав онлайн компиляторы, я заметил что MSVC умеет анализировать структуру классов и удалять поле значения корректирования, если оно не требуется.

#include <string.h>#include <stdint.h>struct A;extern A* a;extern void(A::*func)();template<typename T>T assume_not_virual(T input) {  struct Ptr { uint64_t a, b; };  static_assert(sizeof(T) == sizeof(Ptr), "");  Ptr ptr;  memcpy(&ptr, &input, sizeof(input));  __builtin_assume(!(ptr.a & 1));  return input;}void call() {  (a->*assume_not_virual(func))();}

Всем привет!

Думаю, у многих сразу возник другой вопрос а зачем вообще нужна ещё одна статья про LLVM, ведь на хабре их и так больше сотни? Моей задачей было написать "введение в тему" for the rest of us профессиональных разработчиков, не планирующих создавать компиляторы и совершенно не интересующихся особенностями устройства LLVM IR. Насколько я знаю, подобного ещё не было.

Главное, что интересует практически всех и о чём я планирую рассказать вынесено в заголовок статьи. Зачем нужен LLVM, когда есть GCC и Visual C++? А если вы не программируете на C++, вам стоит беспокоиться? И вообще, LLVM это Clang? Или нет? И что эти четыре буквы на самом деле означают?

Что в имени тебе моём?

Начнём с последнего вопроса. Что скрывается за буквами L-L-V-M? Когда-то давно они были акронимом для "Low Level Virtual Machine", а в наше время означают ровным счётом ничего.

LLVM родился как исследовательский проект Криса Латнера (тогда ещё студента-магистра в Университете штата Иллинойс в Урбана-Шампейн) и Викрама Адве (тогда и по сию пору профессора в том же университете). Целью проекта было создание промежуточного представления (intermediate representation, IR) программ, позволяющего проводить "агрессивную оптимизацию в течении всего времени жизни приложения" что-то вроде Java байт-кода, только круче. Основная идея сделать представление, одинаково хорошо подходящее как для статической компиляции (когда компилятор получает на вход программу, написанную на языке высокого уровня, например C++, переводит её в LLVM IR, оптимизирует, и получает на выходе быстрый машинный код), так и динамической (когда runtime система получает на вход машинный код вместе с LLVM IR, сохранённым в объектном файле во время статической компиляции, оптимизирует его с учётом собранного к этому времени динамического профиля и получает на выходе ещё более быстрый машинный код, для которого можно продолжать собирать профиль, оптимизировать, и так до бесконечности).

Интересно? Хотите узнать подробности? Диссертация Криса Латнера доступна онлайн.

Вот картинка из неё, иллюстрирующая принципы работы "оптимизации в течении всего времени жизни приложения":

Эта картинка, конечно же, про LLVM но совершенно не про то, что под словом "LLVM" понимается сейчас. Больше того! на сайте llvm.org написано, что LLVM это не о виртуальных машинах, и вовсе даже не акроним, а просто такое вот название проекта.

Как так получилось? В 2005 году Крис защитил кандидатскую диссертацию и переехал из Иллинойса в Кремниевую долину...

Apple, Google и все-все-все

Примерно в то же время Apple начала задумываться о создании своего собственного компилятора Objective-C и решила сделать ставку на Криса Латнера и его (в то время по сути ещё академический) проект LLVM. Зачем Apple понадобился собственный компилятор? Прежде всего, Apple хорошо известна как компания, стремящаяся контролировать весь технологический стек. Кроме того, у Apple были большие проблемы с инструментами разработки для ранних Маков на основе PowerPC, когда выбранный партнёр (Symantec) не сумел выпустить хороший компилятор вовремя, что поставило под риск будущее всей компании.

В 2005 году Apple уже достаточно долгое время инвестировала в разработку GCC, но как и многие другие, была сильно недовольна лицензией GPL. Особенно GPLv3, на которую перешёл GCC начиная с версии GCC 4.3. Недовольство Apple было так велико, что последней версией GCC, поставляемой в составе XCode, так и осталась GCC 4.2. Главная проблема GPL для компаний, выпускающих секретное "железо": если бинарии для этого железа генерируются с помощью GCC, то исходный код компилятора, в том числе и секретную часть, надо открыть и ваше секретное железо теперь совсем не секретное! Проект LLVM всегда был под "либеральной" лицензией (вначале UIUC, потом Apache 2.0), которая не накладывает столь жёстких ограничений, и позволяет свободно комбинировать в одном продукте открытый и закрытый код.

Apple был нужен обычный статический компилятор, а не система для "оптимизации в течении всего времени жизни приложения", и поэтому Крис Латтнер переделал LLVM в бэк-энд для GCC. "Бэк-эндом" называется та часть компилятора, что выполняет оптимизации и генерирует машинный код; есть ещё "фронт-энд" принимающая на вход пользовательскую программу на языке высокого уровня и переводящая её в промежуточное представление, например LLVM IR. Комбинация GCC-фронт-энда и LLVM-бэк-энда работала неплохо, но не без проблем соединение двух больших и независимых проектов, преследующих разные цели, всегда чревато появлением лишних ошибок и обрекает на вечную игру в "догонялки". Вот почему уже в 2006 году Крис начал работать над новым проетом, получившим название "Clang".

Происхождение имени "clang" интуитивно понятно это комбинация слов "C" и "language". "C" указывает на семейство C-образных языков, куда кроме самого C входят также C++ и Objective-C. Кстати говоря, "clang" произносится как "к-ланг", а не как "си-ланг"! не повторяйте популярную ошибку!

Комбинация фронт-энда Clang и бэк-энда LLVM называется Clang/LLVM или просто Clang. Сейчас это один из самых популярных (если не самый популярный!) компилятор C++ в мире.

Большую роль в развитии и росте популярности LLVM и Clang сыграла компания Google. В отличии от Apple, Google выбрала LLVM в основном по техническим причинам GCC очень старый проект, который сложно модифицировать и расширять. Для Google всегда были важны надёжность и безопасность программ например, одно из правил компании требует обязательного добавления статической проверки в компилятор для каждой новой ошибки, обнаруженной в продакшене. Добавить подобного рода проверку в Clang гораздо проще. Ещё один аргумент в пользу Clang поддержка Windows. GCC органически не подходит для Windows, и хотя есть версия GCC и для этой операционной системы, серьёзную разработку с её помощью вести нельзя. Некоторые вещи, например поддержку отладочной информации в формате PDB, в GCC в принципе невозможно добавить всё из-за тех же лицензионных ограничений.

Внутренние команды Google всегда были вольны в праве выбора компилятора, и большая часть из них использовала GCC; кто-то применял коммерческие компиляторы от Intel и Microsoft. Постепенно практически весь Google всё-таки перешёл на Clang. Большими вехами стали появление полнокровной поддержки Windows (которую сделала сама Google, причём для компиляции всего-навсего двух программ: Chromium и Google Earth) и переход на LLVM в качестве основного компилятора операционной системы Android. Причину перехода лучше всего объяснили сами разработчики Android: "Пришло время перейти на единый компилятор для Andorid. Компилятор, способный помочь найти (и устранить) проблемы безопасности."

После того, как переход сделала Google, рост популярности LLVM было уже не остановить. Всё больше и больше компаний и академических организаций начали делать ставку на LLVM: ARM, IBM, Sony, Samsung, NXP, Facebook, Argonne National Lab это именно тот случай, когда "всех не перечесть". Некоторые компании продолжают поддерживать GCC, но в значительно большей степени инвестируют именно в LLVM например, так поступают Intel и Qualcomm. Наплыв инвестиций создал "восходящую спираль роста" когда новые улучшения LLVM привлекают новых пользователей, те инвестируют в дополнительные улучшения, те в свою очередь приводят ещё больше новых пользователей и инвестиций, и так далее.

LLVM против GCC

Возможно, к этому моменту вы уже начали задаваться вопросом: "ну хорошо, причины, побудившие к переходу Apple и Google, понятны но мне-то что за дело? Почему лично я должен переходить на LLVM? Чем GCC плох?"

Ответ абсолютно ничем! GCC продолжает быть отличным компилятором, в который вложены многие годы труда. Да, его сложно расширять, и да, над его развитием работает не так много людей, и да, лицензия GPL серьёзно сужает круг проектов, которые можно сделать на основе кодовой базы GCC но всё это проблемы разработчиков GCC, а не ваши, ведь так?

К сожалению, проблемы развития проекта GCC в итоге замечают и конечные пользователи ведь постепенно GCC начинает отставать от LLVM. Все основные "игроки" мира ARM (Google, Samsung, Qualcomm и собственно компания ARM) сфокусированы на развитии прежде всего LLVM а значит, поддержка новых процессоров на основе архитектуры ARM появляется в LLVM раньше и включает больше оптимизаций и более тщательный "тюнинг" производительности, чем в GCC.

То же самое касается поддержки языка C++. Ридард Смит, инженер компании Google, выступающий секретарём комитета ISO по стандартизации C++ иными словами, тот человек, кто собственно пишет текст всех дополнений стандарта своими руками является маинтейнером фронт-энда Clang. Многие другие заметные участники комитета также являются активными разработчиками Clang / LLVM. Сложите эти два факта, и вывод очевиден: поддержка новых дополнений в языке C++ раньше всего появляется именно в Clang'е.

Ещё одно важное преимущество Clang и как мы знаем, главная причина перехода команды Android на LLVM развитая поддержка статической верификации. Говоря простыми словами, Clang находит больше warning'ов, чем GCC, и делает это лучше. Кроме того, есть специальный написанный на основе Clang'а инструмент, под названием Clang Static Analyzer, включающий в себя богатую коллекцию сложных проверок, анализирующих больше чем одну строку кода, и выявляющих проблемы использования языка С++, работы с нулевыми указателями и нарушения безопасности (https://clang.llvm.org/docs/analyzer/checkers.html).

В проект LLVM входит много разных инструментов, являющихся лидерами в своей области: коллекция динамических верификаторов под названием "санитайзеры", рантайм-библиотека OpenMP (лучшая на рынке), lld (сверх-быстрый линковщик), libc++ (наиболее полная реализация стандартной библиотеки C++). Все они могут использоваться независимо от LLVM в том числе и с GCC тоже, как минимум в теории. На практике же у каждого компилятора есть множество небольших отличий и особенностей, и потому все эти инструменты лучше всего работают именно с LLVM ведь они разрабатываются, тестируются и выпускаются все вместе.

Clang разрабатывался как полностью совместимая замена GCC, так что в стандартном проекте для перехода достаточно просто поменять имя компилятора. На практие возможны сюрпризы от новых ошибок на этапе компиляции до неожиданных падений при тестировании. Обычно это означает, что в проекте есть код, полагающийся на аспекты стандартов C и C++ с "неопределённым поведением" которое может трактоваться компиляторами GCC и Clang по разному.

Например, бесконечные циклы. Как вы думаете, что должно случиться после компиляции и выполнения такой программы?

    #include <stdio.h>    static void die() {      while(1)        ;    }    int main() {      printf("begin\n");      die();      printf("unreachable\n");    }

Попробуйте откомпилировать её с помощью "gcc -O2" и "clang -O2" результат может вас удивить. Причина в "неопределённом поведении" для бесконечных циклов в стандарте языка C (есть лишний час в запасе? можете узнать подробности). Раз поведение "неопределено", компилятор волен делать с бесконечными циклами вообще всё, что угодно даже "выпускать из ноздрей летающих демонов"! (это выражение стало мемом в сообществе C разработчиков). Как можно убедиться, Clang и GCC просто поступают по разному. Конечно же, основывать логику программы на неопределённом поведении не лучшая практика (кто захочет испускать демонов из носа?) и такой код должен исправляться, как и любая другая ошибка.

Я рекомендую попробовать заменить "gcc" на "clang" (или "g++" на "clang++" в случае C++) в каком-то из ваших проектов. Кто знает? может вам удастся увидеть летающих демонов?

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

"Зонтик" LLVM

Проект LLVM вырос за рамки компилятора C++. Один из важных принципов разработки LLVM написание кода как набора переиспользуемых библиотек, которые можно соединять разным образом и для разных целей привёл к появлению множества интересных новых инструментов. Часть из них была добавлена к проекту, так что LLVM со временем превратился в "зонтик" для нескольких совершенно разных под-проектов. Ещё больше инструментов развиваются за пределами проекта LLVM, но полагаются на библиотеки LLVM для анализа и оптимизации программ, а также генерации кода.

Я уже упоминал Clang Static Analyzer, санитайзеры, OpenMP, libc++ и lld это инструменты, более всего интересные C++ разработчикам. Компилятор языка Rust также написан на LLVM решение, позволившее Rust задействовать всю мощь LLVM оптимизатора для генерации быстрого кода для множества аппаратных платформ с самого начала существования языка! Помимо C++ и Rust, LLVM используется в компиляторах (как статических, так и динамических) для таких разных языков как D, Fortran, Haskell, Kotlin, Lua, PHP, Python. Создателю нового языка достаточно написать фронт-энд, переводящий программы в формат LLVM IR, чтобы воспользоваться оптимизатором и генератором кода мирового уровня! Лёгкость использования LLVM в этом качестве дала толчок появлению новых разработок в области языков программирования.

Одна из важных областей применения LLVM это тензорные компиляторы, многократно ускоряющие задачи машинного обучения. Два из самых популярных ML фреймворков TensorFlow компании Google и Pythorch от Facebook полагаются именно на LLVM для генерации быстрого кода.

Сейчас LLVM стал настолько популярен, что он встречается практически повсюду. Если вы запускаете приложение или ML модель (на телефоне, десктопе или серверной ферме), то почти наверняка ваше приложение или модель каким-то образом прошло через один из инструментов, использующих LLVM.

Всё это сделало LLVM критически важным проектом для основных игроков в индустрии ведь каждый новый патч в "core" библиотеки LLVM влияет на сотни инструментов! Список спонсоров LLVM Developers' Meeting читается как справочник "кто есть кто" мира IT. Компания, в которой я работаю, Huawei, также является спонсором ведь как любая большая и разносторонняя организация, мы используем LLVM в большом числе своих продуктов.

Надеюсь, эта небольшая статья справилась со своей задачей, и вы стали лучше понимать что такое LLVM и почему этот проект так важен. Возможно даже решили попробовать один из LLVM-инструментов в своём проекте?

Я был и остаюсь вовлечён в разработку LLVM в течении многих лет (сначала в Intel, затем в NXP и теперь в Huawei), так что этот проект очень близок моему сердцу. Раскрою карты! у статьи была и вторая, секретная цель: заразить энтузиазмом и верой в LLVM всех читателей. Что скажите? удалось? :-)

Это очередная статья из цикла BPF для самых маленьких (0, 1, 2) и первая из серии практических статей про трассировку Linux современными средствами.

Из нее вы узнаете о программе и языке bpftrace самом простом способе погрузиться в мир BPF с практической точки зрения, даже если вы не знаете про BPF ровным счетом ничего. Утилита bpftrace позволяет при помощи простого языка прямо из командной строки создавать программы-обработчики и подсоединять их к огромному количеству событий ядра и пространства пользователя. Посмотрите на КПДВ ниже поздравляю, вы уже умеете трейсить системные вызовы при помощи bpftrace!

В отличие от предыдущих статей серии, эта относительно короткая и ее основная часть написана в формате туториала, так что уже после пяти минут чтения вы сможете создавать обработчики и собирать статистику о любом событии в ядре Linux прямо из командной строки. В конце статьи рассказывается об альтернативах ply и BCC. Минуты во фразе после пяти минут чтения подразумеваются меркурианские. Появление уникальных навыков после пяти минут чтения не гарантируется.

Содержание

• Установка bpftrace
• Какие события мы можем трейсить?
• Bpftrace: tutorial
  
  • Базовые навыки
  • Структура программ bpftrace
  • Храним состояние: переменные и мапы
  • Считаем и агрегируем события
  • Веселые Картинки: flame graphs
  • Пора закругляться
• BCC: утилиты и фреймворк
  
  • Пишем новую утилиту BCC
• Ply: bpftrace для бедных

Установка bpftrace

Короткая версия. Попробуйте выполнить команду sudo apt install bpftrace (скорректированную под ваш дистрибутив). Если bpftrace установился, то переходите к следующему разделу.

Длинная версия. Хотя bpftrace и доступен в качестве пакета в популярных дистрибутивах, но не во всех, а кроме этого он может быть собран криво, например, без поддержки BTF. Поэтому давайте посмотрим на то, как добыть bpftrace альтернативными средствами.

При каждом обновлении master-ветки репозитория bpftrace собирается и публикуется новый docker image с упакованным внутри bpftrace. Таким образом, мы можем просто скачать и скопировать бинарник:

$ docker pull quay.io/iovisor/bpftrace:latest$ cd /tmp$ docker run -v $(pwd):/o quay.io/iovisor/bpftrace:latest /bin/bash -c "cp /usr/bin/bpftrace /o"$ sudo ./bpftrace -Vbpftrace v0.11.4

Если bpftrace ругается на слишком старую версию glibc, то вам нужен другой docker image со старой glibc.

Проверим, что программа работает. Для этого запустим пример из КПДВ, который трейсит системный вызов execve(2) и в реальном времени показывает какие программы запускаются в системе, и кем:

$ sudo ./bpftrace -e 'tracepoint:syscalls:sys_enter_execve { printf("%s -> %s\n", comm, str(uptr(args->filename))); }'Attaching 1 probe...bash -> /bin/echobash -> /usr/bin/lsgnome-shell -> /bin/shsh -> /home/aspsk/bin/geeqiesh -> /usr/local/sbin/geeqie...

Наконец, когда мы убедились, что все работает, давайте положим бинарник в правильное место:

$ sudo mv /tmp/bpftrace /usr/local/bin

Если вам этого мало, то можете скачать исходники, запустить чуть больше проверок, собрать свое ядро с поддержкой BTF, а также свою версию bpftrace, при помощи docker или локально. Инструкции по самостоятельной сборке bpftrace см. в официальной документации.

Важная деталь. Если bpftrace и/или ядро собрано без поддержки BTF, то для полноценной работы нужно установить kernel headers. Если вы не знаете как это сделать, то в документации bpftrace есть универсальный дистрибутивонезависимый рецепт.

Мы не будем в этой статье подробно рассказывать про BTF, скажем только, что BTF убирает зависимость от kernel headers, позволяет писать более простые программы, а также расширяет набор событий, к которым мы можем подключиться. Если внешние обстоятельства требуют от вас изучения BTF прямо сейчас, то начните с этой статьи и продолжите этой и этой.

Какие события мы можем трейсить?

Вы сидите в лесу с фотоаппаратом на удобном раскладном стуле. Идет мелкий дождь, но он вам не страшен, ведь шалаш из еловых веток надежно укрывает вас как от дождя, так и от случайных взглядов. Рядом стоит термос с пуэром, йогурт и поднос с копчеными селедками. Но тут вы вдруг задумываетесь: а зачем я сюда пришел и что я буду снимать?! Когда вы просыпаетесь, на лице краснеет слепок клавиатуры, а в терминале написано

$ sudo apt install bpftraceThe following NEW packages will be installed:  bpftracePreparing to unpack .../bpftrace_0.11.0-1_amd64.deb ...Unpacking bpftrace (0.11.0-1) ...Setting up bpftrace (0.11.0-1) ...Processing triggers for man-db (2.9.3-2) ...$

Итак, bpftrace у нас уже установлен. Какие события мы можем инструментировать? Давайте посмотрим на них по очереди, а заодно познакомимся с синтаксисом языка bpftrace. Вот спойлер-оглавление данной секции:

• Специальные события: BEGIN, END
• События, основанные на kprobes: kprobe, kretprobe, uprobe, uretprobe
• События, основанные на BPF trampolines: kfunc, kretfunc
• События, основанные на tracepoints: tracepoint
• Статическая отладка в пространстве пользователя: usdt
• События, основанные на подсистеме perf: software, hardware, profile, interval, watchpoint

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

Bpftrace: hello world

Язык bpftrace создавался по аналогии с языком awk и поэтому в нем есть два специальных события, BEGIN и END, которые случаются в момент запуска и выхода из bpftrace, соответственно. Вот первая простая программа:

# bpftrace -e 'BEGIN { printf("Hello world!\n"); }'Attaching 1 probe...Hello world!^C

Программа сразу после старта напечатала "Hello world!". Заметьте, что нам пришлось нажимать Ctrl-C, чтобы завершить работу bpftrace это его поведение по умолчанию. Мы можем завершить работу bpftrace из любого события при помощи функции exit. Продемонстрируем это, а заодно добавим и обработку END:

# bpftrace -e ' BEGIN { printf("Hello world!\n"); exit(); } END { printf("So long\n"); } 'Attaching 2 probes...Hello world!So long

Kprobes динамическая инструментация ядра

Ядро это большая программа, функции этой программы, как водится, состоят из инструкций, а механизм ядра под названием kprobes (Kernel Probe ядерный зонд) позволяет нам поставить точку останова практически на любой инструкции, а точнее, по началу конкретной функции или коду внутри нее. В контексте данной статьи нам, вообще говоря, не важно как именно создаются обработчики kprobes, но вы можете узнать об этом из предыдущих статей этой серии, ссылки на которые есть в конце, а также из будущих статей, в которых мы разберем все технические подробности трассировки Linux с BPF.

В качестве примера давайте посмотрим на то, как часто и кем вызывается функция schedule:

$ sudo bpftrace -e '    k:schedule { @[comm] = count(); }    i:s:2 { exit();}    END { print(@, 10); clear(@); }'Attaching 3 probes...@[Timer]: 147@[kworker/u65:0]: 147@[kworker/7:1]: 153@[kworker/13:1]: 158@[IPC I/O Child]: 170@[IPC I/O Parent]: 172@[kworker/12:1]: 185@[Web Content]: 229@[Xorg]: 269@[SCTP timer]: 1566

Мы также сказали программе выйти через две секунды и в конце напечатать только десять верхних элементов словаря @.

Много ли функций можно потрейсить при помощи кей-проб? Это легко проверить:

$ sudo bpftrace -l 'k:*' | wc -l61106

Это почти все функции загруженного в данный момент ядра. Исключения составляют функции, которые компилятор решил встроить в код и немногочисленные функции, которые запрещено трейсить при помощи kprobe, например, функции, которые реализуют сам механизм kprobes.

kretprobes

Для каждой kprobe мы можем создать обработчик kretprobe. Если kprobe запускается в момент входа в функцию, то kretporobe запускается в момент выхода из функции. При этом код возврата функции содержится в специальной встроенной переменной retval.

Например, вот что на отрезке в две секунды возвращала функция vfs_write на моей системе (в виде логарифмической гистограммы):

$ sudo bpftrace -e 'kr:vfs_write { @ = hist(retval); } i:s:2 { exit(); }'Attaching 2 probes...@:[1]                  606 |@@@@@@@@@@@@@@@@@@@@@@@@@                           |[2, 4)                 0 |                                                    |[4, 8)                 0 |                                                    |[8, 16)             1223 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|[16, 32)               0 |                                                    |[32, 64)              25 |@                                                   |

uprobes и uretprobes

Кроме инструментации функций ядра, мы можем инструментировать каждую программу (и библиотеку), работающую в пространстве пользователя. Реализуется это при помощи тех же kprobes. Для этого в bpftrace определены события uprobes и uretprobes вызов и возврат из функции.

Вот как мы можем подглядывать за тем, что печатают пользователи баша (в квадратных скобках печатается UID пользователя):

$ sudo bpftrace -e 'uretprobe:/bin/bash:readline { printf("readline: [%d]: \"%s\"\n", uid, str(uptr(retval))); }'Attaching 1 probe...readline: [1000]: "echo "hello habr""readline: [0]: "echo "hello from root""^C

Динамическая инструментация ядра, версия 2

Для счастливых обладателей CONFIG_DEBUG_INFO_BTF=y в конфиге ядра существует более дешевый, по сравнению с kprobes, способ динамической инструментации ядра, основанный на bpf trampolines. Так как BTF в дистрибутивных ядрах обычно выключен, я про эти события дальше не рассказываю. Если интересно, то смотрите сюда и/или задавайте вопросы в комментариях.

Tracepoints статическая инструментация ядра

Если что-то можно сделать динамически, то, с большой вероятностью, это же можно сделать статически чуть быстрее и удобнее. Механизм ядра под названием tracepoints предоставляет набор статических точек останова ядра для наиболее важных функций. Вы можете посмотреть на свой набор так:

$ sudo bpftrace -l 't:*'

Их сильно меньше, чем kprobes:

$ sudo bpftrace -l 't:*' | wc -l1782

но самой важной особенностью tracepoints является то, что они предоставляют стабильный API: вы можете быть уверены, что tracepoint, на основе которой вы написали свой код для отладки или сбора информации, не пропадет или не поменяет семантику в самый неудобный момент. Еще одним удобным отличием является то, что bpftrace может нам рассказать о том, какие аргументы передаются в конкретный tracepoint, например:

$ sudo bpftrace -lv tracepoint:thermal:thermal_temperaturetracepoint:thermal:thermal_temperature    __data_loc char[] thermal_zone;    int id;    int temp_prev;    int temp;

В случае kprobe, если у вас не включен BTF, вам придется читать исходники ядра, причем той версии, которую вы используете. А с BTF вы можете смотреть и на строение kprobes и kfuncs.

usdt статическая инструментация в пространстве пользователя

Статическая инструментация программ пользователя позволяет напихать в программу статических точек останова в момент компиляции. Давайте сразу посмотрим на пример (который я стянул почти без изменений отсюда):

#include <sys/sdt.h>#include <sys/time.h>#include <unistd.h>int main(int argc, char **argv){    struct timeval tv;    for (;;) {        gettimeofday(&tv, NULL);        DTRACE_PROBE1(test, probe, tv.tv_sec);        sleep(1);    }}

Мы добавили одну статическую точку останова под названием test:probe, в которую передаем один аргумент tv.tv_sec текущее время в секундах. Чтобы скомпилировать эту программу, нужно поставить пакет systemtap-sdt-dev (или аналогичный для вашего дистрибутива). Дальше мы можем посмотреть на то, что получилось:

$ cc /tmp/test.c -o /tmp/test$ sudo bpftrace -l 'usdt:/tmp/test'usdt:/tmp/test:test:probe

Запустим /tmp/test в одном терминале, а в другом скажем

$ sudo bpftrace -e 'usdt:/tmp/test:test:probe { printf("московское время %u\n", arg0); }'Attaching 1 probe...московское время 1612903991московское время 1612903992московское время 1612903993московское время 1612903994московское время 1612903995...

Здесь arg0 это значение tv.tv_sec, которое мы передаем в breakpoint.

События Perf

Программа bpftrace поддерживает множество событий, предоставляемых подсистемой ядра Perf. Мы сейчас коротко посмотрим на следующие типы событий, поддерживаемые bpftrace:

• software: статически-сгенерированные софтверные события
• hardware: железные PMCs
• interval: интервальное событие
• profile: интервальное событие для профилирования

События типа `software`

В ядре определяется несколько статических событий perf, посмотреть их список можно так:

# bpftrace -l 's:*'software:alignment-faults:software:bpf-output:software:context-switches:software:cpu-clock:software:cpu-migrations:software:dummy:software:emulation-faults:software:major-faults:software:minor-faults:software:page-faults:software:task-clock:

События такого типа могут происходить очень часто, поэтому на практике указывается количество сэмплов, например, команда

# bpftrace -e 'software:cpu-migrations:10 { @[comm] = count(); }'Attaching 2 probes...^C@[kworker/u65:1]: 1@[bpftrace]: 1@[SCTP timer]: 2@[Xorg]: 2

Подсчитает каждое десятое событие миграции процесса с одного CPU а другой. Значение событий из списка выше объясняется в perf_event_open(2), например, cpu-migrations, которую мы использовали выше можно найти в этой man-странице под именем PERF_COUNT_SW_CPU_MIGRATIONS.

События типа `hardware`

Ядро дает нам доступ к некоторым hardware counters, а bpftrace может вешать на них программы BPF. Точный список событий зависит от архитектуры и ядра, например:

bpftrace -l 'h*'hardware:backend-stalls:hardware:branch-instructions:hardware:branch-misses:hardware:bus-cycles:hardware:cache-misses:hardware:cache-references:hardware:cpu-cycles:hardware:frontend-stalls:hardware:instructions:hardware:ref-cycles:

Посмотрим на то как мой процессор предсказывает инструкции перехода (считаем каждое стотысячное событие, см. PERF_COUNT_HW_BRANCH_MISSES):

bpftrace -e 'hardware:branch-misses:100000 { @[tid] = count(); }'Attaching 3 probes...@[1055]: 4@[3078]: 4@[1947]: 5@[1066]: 6@[2551]: 6@[0]: 29

События типа `interval` и `profile`

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

Мы уже использовали интервал раньше, чтобы выйти из программы. Давайте посмотрим на этот пример еще раз, но чуть пропатчим его:

$ sudo bpftrace -e '    kr:vfs_write { @ = hist(retval); }    interval:s:2 { print(@); clear(@); }'

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

Аналогично можно использовать и profile:

# bpftrace -e '  profile:hz:99 { @[kstack] = count(); }  i:s:10 { exit(); }  END { print(@,1); clear(@); }'Attaching 3 probes...@[    cpuidle_enter_state+202    cpuidle_enter+46    call_cpuidle+35    do_idle+487    cpu_startup_entry+32    start_secondary+345    secondary_startup_64+182]: 14455

Здесь мы запускаем profile на каждом ядре 99 раз в секунду, через десять секунд выстрелит интервал и вызовет exit(), а секция END напечатает только верхний элемент словаря @ самый часто встречающийся ядерный стек (по которому мы видим, что моя система, в основном, бездействует).

Bpftrace: tutorial

Базовые навыки

Начнем с простого, запустим bpftrace без аргументов:

# bpftrace

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

Посмотрим внимательнее на аргумент -l. Он позволяет найти события по шаблону. (Если что-то дальше не ясно, то читайте про события в предыдущем разделе, который вы пропустили.) Вот как можно искать события среди всех возможных:

# bpftrace -l '*kill_all*'kprobe:rfkill_allockprobe:kill_allkprobe:btrfs_kill_all_delayed_nodes

А здесь мы ищем события только среди tracepoints:

# bpftrace -l 't:*kill*'tracepoint:cfg80211:rdev_rfkill_polltracepoint:syscalls:sys_enter_killtracepoint:syscalls:sys_exit_killtracepoint:syscalls:sys_enter_tgkilltracepoint:syscalls:sys_exit_tgkilltracepoint:syscalls:sys_enter_tkilltracepoint:syscalls:sys_exit_tkill

Подмножество tracepoint:syscalls, на которое мы только что наткнулись, можно использовать для самостоятельных экспериментов по изучению bpftrace. Для каждого системного вызова X определены две точки останова:

tracepoint:syscalls:sys_enter_Xtracepoint:syscalls:sys_exit_X

Поиграемся с каким-нибудь системным вызовом, например, execve(2). Для того, чтобы посмотреть на то, как использовать какой-либо tracepoint можно использовать дополнительный аргумент -v, например:

# bpftrace -lv 't:s*:sys_*_execve'tracepoint:syscalls:sys_enter_execve    int __syscall_nr;    const char * filename;    const char *const * argv;    const char *const * envp;tracepoint:syscalls:sys_exit_execve    int __syscall_nr;    long ret;

(заметьте как ловко мы дважды использовали *, чтобы не писать syscalls полностью и чтобы не перечислять sys_enter_execve и sys_exit_execve по отдельности). Параметры, перечисленные в выводе -lv доступны через встроенную переменную args:

# bpftrace -e '    t:s*:sys_enter_execve { printf("ENTER: %s\n", str(uptr(args->filename))); }    t:s*:sys_exit_execve { printf("EXIT: %s: %d\n", comm, args->ret); }'Attaching 2 probes...ENTER: /bin/lsEXIT: ls: 0ENTER: /bin/lssEXIT: bash: -2

Этот короткий листинг позволяет разглядеть несколько интересных вещей.

В первом обработчике мы печатаем аргумент args->filename. Так как передается он нам как указатель, нам нужно вычитать строку при помощи встроенной функции str, но просто так ее использовать нельзя: указатель этот указывает в пространство пользователя, а значит мы должны об этом специально сказать при помощи функции uptr. Сам bpftrace постарается угадать принадлежность указателя, но он не гарантирует результат. Также, к сожалению, вызов bpftrace -lv не расскажет нам о семантике указателя, для этого придется изучать исходники, в данном случае, мы посмотрим на определение системного вызова execve (обратите внимание на квалификатор типа __user).

Во втором обработчике мы используем встроенную переменную comm, которая возвращает текущее имя потока. Код возврата системного вызова доступен через переменную args->ret. Как известно, этот системный вызов "не возвращается" в текущую программу, так как его работа заключается собственно в замене кода программы новым. Однако, в случае ошибки он-таки вернется, как мы и можем видеть в выводе выше: в первом случае я запустил /bin/ls из баша и exec запустился нормально и вернул 0 (внутри процесса ls прямо перед запуском кода /bin/ls), а во втором случае я запустил несуществующую программу /bin/lss и exec вернул -2 внутри процесса bash.

Упражнение. Возьмите ваш любимый системный вызов и напишите несколько программ, аналогичных приведенной выше. Попробуйте напечатать все аргументы системного вызова и значение, которое он возвращает. Не забудьте использовать uptr, если нужно.

Структура программ `bpftrace`

Язык bpftrace создавался по аналогии с языком awk (см. также главу 6 в книжке The AWK Programming Language) и имеет очень похожую структуру. Программы состоят из списка блоков вида

<probe> <filter> { <action> }

Например,

# bpftrace -e 'BEGIN { printf("Hello\n") } END { printf("World\n") }'

Здесь <probe> это BEGIN и END, а <action> это printf. Поле
<filter> является опциональным и используется для фильтрации событий,
например, программа

# bpftrace -e 'p:s:1 /cpu == 0/ { printf("Привет с CPU%d\n", cpu); }'Attaching 1 probe...Привет с CPU0Привет с CPU0^C

будет передавать привет, только если запускается на CPU 0.

Упражнение. Что выведет эта команда на вашей машине, если убрать фильтр /cpu == 0/?

На практике <filter> удобно использовать для синхронизации между двумя событиями. Например, вы хотите подсчитать время выполнения системного вызова write на вашей системе. Для этого мы можем использовать пару трейспоинтов sys_enter_write и sys_exit_write и считать время выполнения по тредам:

# cat /tmp/write-times.btt:syscalls:sys_enter_write {  @[tid] = nsecs}t:syscalls:sys_exit_write /@[tid]/ {  @write[comm] = sum((nsecs - @[tid]) / 1000);  delete(@[tid]);}END {  print(@write, 10);  clear(@write);  clear(@);}

Эта программа уже довольно длинная, поэтому мы записали ее в отдельный файл. Запустить ее можно так:

# bpftrace /tmp/write-times.bt

В первом событии, sys_enter_write, мы запоминаем время запуска системного вызова write в наносекундах в словаре @, ключом к которому служит tid.

Во втором событии, sys_exit_write, мы при помощи фильтра /@[tid]/ проверяем, запускался ли обработчик первого события для данного потока. Нам нужно это делать, ведь мы могли запустить программу в тот момент, когда какой-то поток был внутри системного вызова write. Дальше мы записываем потраченное время (в микросекундах) в отдельный словарь @write и удаляем элемент @[tid].

Наконец, после того как мы нажимаем ^C, запускается секция END, в которой мы печатаем десять самых прожорливых процессов и чистим словари @write и @, чтобы bpftrace не выводил их содержимое.

Упражнение. Так что же именно может пойти не так, если убрать фильтр /@[tid]/?

Храним состояние: переменные и мапы

Внутри программ bpftrace вы можете использовать обычные для языка C конструкции, например, :?, ++, --. Вы можете использовать блоки if {} else {}. Можно составлять циклы при помощи while и экзотического unroll (который появился в то время, когда в архитектуре BPF циклы были запрещены). Содержание же во все эти конструкции добавляют переменные и структуры ядра, доступные из контекста.

Переменные бывают двух типов: локальные и глобальные. Локальные переменные начинаются со знака доллара $ и доступны в пределах заданного события, оба следующих варианта сработают:

# bpftrace -e 'BEGIN { $x = 1; printf("%d\n", ++$x); exit(); }'# bpftrace -e 'BEGIN { if (1) { $x = 1; } printf("%d\n", ++$x); exit(); }'

а следующее нет:

# bpftrace -e 'BEGIN { $x = 1; exit(); } END { printf("%d\n", $x); }'

Глобальные переменные, с которыми мы уже встречались выше, начинаются со знака @ и доступны между событиями. Вы можете использовать "безымянную" глобальную переменную @, как мы делали выше для хранения начала вызова write (@[tid]). (Глобальные переменные в bpftrace хранятся в мапах специальных размеченных областях памяти. Они, между прочим, глобальные в более общем смысле: любая программа с рутовым доступом на системе может их читать и писать. Но для данной статьи это не так важно, смотрите предыдущие серии, если вам интересны подробности.)

И теперь, мы переходим к самому главному: зачем нам нужны переменные и что мы в них будем записывать? Каждое событие bpftrace запускается с определенным контекстом. Для kprobes нам доступны аргументы вызываемой функции, для tracepoints аргументы, передаваемые в tracepoint, а для событий Perf, как и для других программ, глобальные переменные. Мы уже видели как мы можем работать с tracepoints, в этой и следующих секциях мы посмотрим на kprobes, а в секции Веселые Картинки мы посмотрим на события Perf.

Аргументы kprobes доступны внутри программы как arg0, arg1, и т.д. Аргументы передаются без типа, так что вам придется к нужному типу их приводить вручную. Пример:

#include <linux/skbuff.h>#include <linux/ip.h>k:icmp_echo {  $skb = (struct sk_buff *) arg0;  $iphdr = (struct iphdr *) ($skb->head + $skb->network_header);  @pingstats[ntop($iphdr->saddr), ntop($iphdr->daddr)]++;}

Эта программа строит статистику о том, кто пингует данный хост. Мы цепляемся к kprobe на входе в функцию icmp_echo, которая вызывается на приход ICMPv4 пакета типа echo request. Ее первый аргумент, arg0 в нашей программе, это указатель на структуру типа sk_buff, описывающую пакет. Из этой структуры мы достаем IP адреса и увеличиваем соответствующий счетчик в глобальной переменной @pingstats. Все, теперь у нас есть полная статистика о том, кто и как часто пинговал наши IP адреса! Раньше для написания такой программы вам пришлось бы писать модуль ядра, регистрировать в нем обработчик kprobe, а также придумывать механизм взаимодействия с user space, чтобы хранить и читать статистику.

Посмотрим на нее еще раз. Вначале мы включили два хедера ядра, для этого нужно установить пакет с kernel headers. Эти хедеры нужны нам для определения структур sk_buff и iphdr, которые мы собираемся разыменовывать. (Если бы у нас был собран BTF, то нам не нужно было бы это делать ни устанавливать пакет, ни включать хедеры.) В первой строчке программы мы приводим единственный аргумент функции icmp_echo к указателю на sk_buff и сохраняем его в локальной переменной $skb. На второй строчке мы разыменовываем $skb и находим место в памяти, где хранится сетевой заголовок, который мы, в свою очередь, приводим к указателю на iphdr. На третьей строчке мы используем сетевой заголовок и встроенную функцию ntop языка bpftrace, которая преобразует бинарный IP адрес в строку.

Упражнение. Возьмите любую интересующую вас функцию ядра и попробуйте разыменовать ее аргументы. Не забывайте про uptr и kptr. Например: возьмите функцию vfs_write ядра, ее первый аргумент это указатель на структуру struct file, определенную в заголовке <linux/fs.h>. Попробуйте напечатать интересующие вас флаги файла до и после вызова vfs_write. (Hint: как вы можете передать указатель на struct file внутрь kretprobe?)

Упражнение. Напишите программу bpftrace, которая будет печатать имя и пароль пользователя, всякий раз, как он запускает sudo.

Считаем и агрегируем события

В предыдущей программе про ping мы сделали ошибку не защитились от того, что программа может быть запущена на разных CPU. Для более точного подсчета мы можем использовать функцию count. Следующий пример иллюстрирует проблему:

# bpftrace -e 'p:hz:5000 { @x++; @y = count(); } i:s:10 { exit(); }'Attaching 2 probes...@x: 760528@y: 799002

В течение 10 секунд по 5000 раз в секунду на каждом из 16 ядер моей системы мы увеличиваем значения двух счетчиков @x и @y. Операция ++ выполняется безо всяких блокировок и поэтому значение счетчика не совсем точное. Операция count() на самом деле выполняется тоже безо всяких блокировок, но использует CPU-локальные переменные: для каждого из CPU хранится свой счетчик, значения которых при печати суммируются.

Кроме подсчета событий в bpftrace есть несколько полезных функций, которые могут быстро показать какие-то баги в работающей системе. Главный инструмент тут это гистограммы. Посмотрим на простой пример.

# bpftrace -e 'kr:vfs_write { @ = hist(retval); } i:s:10 { exit() }'Attaching 2 probes...@:[1]             14966407 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|[2, 4)                 0 |                                                    |[4, 8)                 0 |                                                    |[8, 16)             1670 |                                                    |[16, 32)               0 |                                                    |[32, 64)             123 |                                                    |[64, 128)              0 |                                                    |[128, 256)             0 |                                                    |[256, 512)             0 |                                                    |[512, 1K)              0 |                                                    |[1K, 2K)               0 |                                                    |[2K, 4K)               0 |                                                    |[4K, 8K)               0 |                                                    |[8K, 16K)        7531982 |@@@@@@@@@@@@@@@@@@@@@@@@@@                          |

В течении десяти секунд мы строим гистограмму возвращаемых значений функции vfs_write, и мы можем заметить, что кто-то уверенно пытается писать по одному байту! Давайте чуть усовершенствуем программу (то заняло у меня около 20 секунд):

# bpftrace -e '    kr:vfs_write /retval == 1/ { @[pid, comm] = hist(retval); }    i:s:10 { exit() }    END { print(@, 1); clear(@); }'Attaching 3 probes...@[133835, dd]:[1]             14254511 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

Для начала, мы смотрим только на записи, в которых retval равен единице. Для того, чтобы различить процессы мы добавляем ключи идентификатор и имя процесса. Наконец, в END мы печатаем только процесс, который сделал больше всего записей. Что же он делает? Думаю вы уже догадались:

# tr '\000' ' ' < /proc/133835/cmdlinedd if=/dev/zero of=/dev/null bs=1

Упражнение. Найдите ссылку на официальный туториал по bpftrace в конце статьи и выполните все шаги, в которых встречаются гистограммы.

Веселые Картинки: flame graphs

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

profile:hz:rateprofile:s:rateprofile:ms:rateprofile:us:rate

В первом случае мы задаем частоту события в HZ, а в следующих частоту события в секундах, миллисекундах и микросекундах, соответственно.

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

bpftrace -e 'profile:hz:99 { print(kstack); exit() }'Attaching 1 probe...        cpuidle_enter_state+202        cpuidle_enter+46        call_cpuidle+35        do_idle+487        cpu_startup_entry+32        rest_init+174        arch_call_rest_init+14        start_kernel+1724        x86_64_start_reservations+36        x86_64_start_kernel+139        secondary_startup_64+182

здесь в момент сэмплирования мы попали на ядро-бездельника.

Для практического профилирования, однако, смотреть на миллионы стеков ядра не очень удобно. Поэтому БГ разработал механизм агрегации под названием flame graphs, превращающий текст в удобную кликабельную картинку.

Для начала, нам нужно запустить bpftrace следующим образом:

# bpftrace -e 'profile:hz:333 { @[kstack] = count(); } i:s:10 { exit() }' > /tmp/raw# wc -l /tmp/raw3374 /tmp/raw

Здесь мы по 333 раза в секунду сэмплируем стек ядра и считаем сколько раз мы увидели разные стеки (мы используем kstack как ключ в словаре @, ведь kstack это просто строка).

Далее нам нужно склонировать репозиторий FlameGraph и запустить пару скриптов:

$ git clone https://github.com/brendangregg/FlameGraph.git$ cd FlameGraph$ ./stackcollapse-bpftrace.pl /tmp/raw > /tmp/ready$ ./flamegraph.pl /tmp/ready > /tmp/kstack.svg

Первый скрипт приводит вывод bpftrace к каноническому виду, а второй строит по нему картинку (кликните на нее, чтобы открылся gist с SVG):

Здесь моя система наполовину бездействует, а на половине CPU крутится все тот же dd, копирующий /dev/zero в /dev/null по одному байту. Кликайте на картинку, чтобы посмотреть подробности.

Упражнение. Снимки стека можно делать не только при помощи bpftrace. Загляните в в репозиторий FlameGraph и сделайте снимок своей системы другим способом.

Пора закругляться

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

BCC: утилиты и фреймворк

Благодаря проекту BCC люди, роботы и не определившиеся могут использовать возможности BPF без необходимости утруждать себя программированием проект содержит почти 100 готовых утилит. Эти утилиты не случайные примеры, а рабочие инструменты, используемые повседневно в недрах Netflix, Facebook и других компаний добра. См. ссылки на книжки БГ в конце статьи, в которых подробно описано большинство утилит и подробно обсуждается почему и зачем они нужны.

Утилиты написаны на основе libbcc и libbpf и представляют из себя код на питоне, в который встроены куски псевдо-C кода, так что их легко редактировать и расширять даже на боевой машине. Также вы можете писать новые утилиты по аналогии с существующими, см. следующий подраздел.

Утилиты BCC должны быть более-менее опакечены в популярных дистрибутивах. Например, на убунте достаточно поставить пакет bpfcc-tools. После этого мы можем сразу ими пользоваться. Например, команда

# funccount-bpfcc 'vfs_*' -d 5Tracing 67 functions for "b'vfs_*'"... Hit Ctrl-C to end.FUNC                                    COUNTb'vfs_statfs'                               1b'vfs_unlink'                               1b'vfs_lock_file'                            2b'vfs_fallocate'                           31b'vfs_statx_fd'                            32b'vfs_getattr'                             80b'vfs_getattr_nosec'                       88b'vfs_open'                               108b'vfs_statx'                              174b'vfs_writev'                            2789b'vfs_write'                             6554b'vfs_read'                              7363Detaching...

посчитает сколько раз были вызваны функции ядра с префиксом vfs_ на интервале в пять секунд. Чуть интереснее подсунуть программе параметр -p, в котором передается PID процесса. Например, вот что делает мой mplayer, пока я это пишу:

# funccount-bpfcc 'vfs_*' -d 5 -p 29380Tracing 67 functions for "b'vfs_*'"... Hit Ctrl-C to end.FUNC                                    COUNTb'vfs_write'                              208b'vfs_read'                               629Detaching...

Пишем новую утилиту BCC

Давайте напишем простую утилиту BCC. Эта утилита будет считать сколько раз в секунду были вызваны функции ядра mutex_lock и mutex_unlock. Ее полный код приведен далее, также вы можете прочитать его здесь.

#! /usr/bin/python3from bcc import BPFfrom ctypes import c_intfrom time import sleep, strftimefrom sys import argvb = BPF(text="""BPF_PERCPU_ARRAY(mutex_stats, u64, 2);static inline void inc(int key){    u64 *x = mutex_stats.lookup(&key);    if (x)        *x += 1;}void do_lock(struct pt_regs *ctx) { inc(0); }void do_unlock(struct pt_regs *ctx) { inc(1); }""")b.attach_kprobe(event="mutex_lock", fn_name="do_lock")b.attach_kprobe(event="mutex_unlock", fn_name="do_unlock")print("%-8s%10s%10s" % ("TIME", "LOCKED", "UNLOCKED"))while 2 * 2 == 4:    try:        sleep(1)    except KeyboardInterrupt:        exit()    print("%-8s%10d%10d" % (          strftime("%H:%M:%S"),          b["mutex_stats"].sum(0).value,          b["mutex_stats"].sum(1).value))    b["mutex_stats"].clear()

Вначале мы подключаем нужные библиотеки. Понятно, что самая интересная часть тут это импорт класса BPF:

from bcc import BPF

Этот класс позволяет нам определить программы BPF, которые мы будем подключать к событиям. В качестве параметра класс BPF принимает текст программы на псевдо-C. В нашем случае это

BPF_PERCPU_ARRAY(mutex_stats, u64, 2);static inline void inc(int key){    u64 *x = mutex_stats.lookup(&key);    if (x)        *x += 1;}void do_lock(struct pt_regs *ctx)   { inc(0); }void do_unlock(struct pt_regs *ctx) { inc(1); }

Этот код написан на магическом C, вы не сможете скомпилировать его в таком виде, но при инициализации класса BPF некоторые части будут заменены реальным кодом на C.
Так или иначе, вначале мы определяем массив mutex_stats из двух элементов типа u64, наших счетчиков. Заметьте, что мы использовали PERCPU массив, это означает, что для каждого логического CPU будет создан свой массив. Далее мы определяем функцию inc, принимающую в качестве аргумента индекс в массиве mutex_stats. Эта функция увеличивает значение соответствующего счетчика.
Наконец, тривиальные функции do_lock и do_unlock увеличивают каждая свой счетчик.

На этом с ядерной частью почти покончено во время инициализации класс BPF обратится к библиотеке libllvm, чтобы скомпилировать код, и потом зальет его в ядро. Осталось только подключить программы к интересующим нас kprobes:

b.attach_kprobe(event="mutex_lock", fn_name="do_lock")b.attach_kprobe(event="mutex_unlock", fn_name="do_unlock")

Пользовательская часть кода занимается исключительно сбором информации:

print("%-8s%10s%10s" % ("TIME", "LOCKED", "UNLOCKED"))while 2 * 2 == 4:    try:        sleep(1)    except KeyboardInterrupt:        exit()    print("%-8s%10d%10d" % (          strftime("%H:%M:%S"),          b["mutex_stats"].sum(0).value,          b["mutex_stats"].sum(1).value))    b["mutex_stats"].clear()

После печати заголовка бесконечный цикл раз в секунду печатает значение счетчиков и обнуляет массив mutex_stats. Значение счетчиков мы получаем при помощи метода sum массива mutex_stats, который суммирует значения счетчиков для каждого CPU:

sum(index) {    result = 0    для каждого CPU {        result += cpu->mutex_stats[index]    }    return result}

Вот и все. Программа должна работать примерно так:

$ sudo ./bcc-tool-exampleTIME        LOCKED  UNLOCKED18:06:33     11382     1299318:06:34     11200     1278318:06:35     18597     2255318:06:36     20776     2551618:06:37     59453     6820118:06:38     49282     5806418:06:39     25541     2742818:06:40     22094     2528018:06:41      5539      725018:06:42      5662      735118:06:43      5205      690518:06:44      6733      8438

Где-то в 18:06:35 я переключился из терминала на вкладку с youtube в Firefox, поставил youtube на паузу и затем в 18:06:40 переключился назад в терминал. Итого, программа показала, что при просмотре youtube вы заставляете ядро локать примерно сорок тысяч мьютексов в секунду.

Напоследок хочется сказать, что если вы предпочитаете писать на C, то смотрите в сторону libbpf и CO-RE. Использование libbpf напрямую позволяет избавиться от тяжелых зависимостей времени запуска, типа libllvm, ускоряет время работы, а также экономит дисковое пространство. В частности, некоторые утилиты BCC уже переписаны на libbpf + CO-RE прямо внутри проекта BCC, см. libbpf-tools. За подробностями обращайтесь к статье BCC to libbpf conversion guide (или ждите следующую статью из этой серии).

Ply: bpftrace для бедных

Утилита ply, написанная шведом Tobias Waldekranz в доисторическом 2015 году, является в определенном смысле прямым предком bpftrace. Она поддерживает awk-подобный язык для создания и инструментации ядра программами BPF, например,

ply 'tracepoint:tcp/tcp_receive_reset {    printf("saddr:%v port:%v->%v\n", data->saddr, data->sport, data->dport);}'

Отличительной особенностью ply является минимизация зависимостей: ей нужна только libc (любая). Это удобно, если вы хотите с минимальными усилиями поиграться в BPF на встроенных системах. Для того, чтобы отрезать все зависимости, в ply встроен компилятор ply script language -> BPF.

Однако, не умаляя достоинств ply, стоит отметить, что разработка проекта к настоящему времени заглохла ply работает, поддерживается, но новые фичи не появляются. Вы все еще можете использовать ply, например, для того, чтобы потестировать сборку ядра на встроенной системе или для тестирования прототипов, но я бы советовал сразу писать программы на C с использованием libbpf для эмбедщиков это не составит труда, см., например, статью Building BPF applications with libbpf-bootstrap.

Ссылки

Предыдущие серии:

• BPF для самых маленьких, часть 0: classic BPF
• BPF для самых маленьких, часть 1: extended BPF
• BPF для самых маленьких, часть 2: разнообразие типов программ BPF

Ссылки на ресурсы по bpftrace, BCC и вообще отладке Linux:

• The bpftrace One-Liner Tutorial. Это туториал по bpftrace, в котором перечисляются основные возможности. Представляет из себя список из двенадцати однострочных, или около того, программ.

  
  

• bpftrace Reference Guide. Все, что вы хотели знать про использование bpftrace, но боялись спросить. Если вам этого документа мало, то идите читать про внутренности bpftrace.

  
  

• BCC Tutorial. Если вы освоились с bpftrace и хотите копнуть глубже (но еще не готовы к освоению libbpf и настоящим приключениям), то смотрите на этот туториал по BCC, на BCC Reference Guide, а также на книжки, перечисленные ниже.

  
  

• Brendan Gregg, BPF Performance Tools. БГ распознал потенциал BPF в деле трассировки Linux сразу после его появления и в данной книжке описывает результаты работы последних пяти лет сотню или больше отладочных утилит из проекта BCC. Книжка является отличным справочным дополнением по BPF к следующей.

  
  

• Brendan Gregg, Systems Performance: Enterprise and the Cloud, 2nd Edition (2020). Это второе издание знаменитой Systems Performance. Главные изменения: добавлен материал по BPF, выкинут материал по Solaris, а сам БГ стал на пять лет опытнее. Если книжка BPF Performance Tools отвечает на вопрос как?, то эта книжка отвечает на вопрос почему?, а также рассказывает о других техниках (не BPF единым жив человек).

  
  

__int128 add1(__int128 a, __int128 b) {    return b + a;}

__int128 add1(__int128 a, __int128 b) {    return a + b;}

long long add1(long long a, long long b) {    return a + b;}