Интермодульный анализ проектов на языках C и C++ в деталях. Часть 2

В первой части мы обсудили основы компиляции проектов на языках Си и Си++. Мы также поговорили о линковке и оптимизации. Во второй части мы углубимся в межмодульный анализ и обсудим его другое назначение. Но в этот раз мы не будем говорить об оптимизациях исходного кода — мы выясним, как улучшить качество статического анализа на примере PVS-Studio.

Статический анализ

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

Наши разработчики уже давно реализовали интермодулярный анализ в анализаторе C#. Это стало возможным благодаря инфраструктуре, предоставляемой платформой Roslyn.

Но когда мы только начали реализовывать интермодульный анализ для C и C++, мы столкнулись с рядом проблем. И сейчас я хотел бы поделиться некоторыми решениями, которые мы использовали — надеюсь, они будут вам полезны.

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

Анализатор выполняет синтаксический и семантический анализ текста программы, а затем применяет диагностические правила. Перевод и семантический анализ — особенно анализ потока данных — выполняются за один проход. Такой подход экономит память и хорошо работает.

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

В качестве примера рассмотрим следующий рисунок:

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

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

Это хорошее решение. На таком представлении легче выполнять семантический анализ, поскольку оно имеет довольно ограниченный набор операций с памятью. Например, в LLVM IR сразу понятно, когда считывается или записывается память стека. Это происходит с помощью инструкций load/store. Однако в нашем случае для реализации промежуточного представления пришлось бы внести серьезные изменения в архитектуру анализатора. Это заняло бы слишком много времени, которого у нас не было.

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

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

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

Семантический анализ

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

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

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

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

Объект потока данных

А теперь мы подходим к самой интересной части. Вот он! Data Flow Object (.dfo) — наш формат представления данных бинарного семантического анализа.

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

Похоже на компоновщик, не так ли? Именно по этой причине мы не стали изобретать велосипед — мы просто создали свой формат DFO, который похож на ELF. Давайте рассмотрим его поближе.

Файл разделен на секции: DFO-секция, .symbol, .facts и .data.

Секция DFO содержит дополнительную информацию:

• Magic — идентификатор формата;
• Версия — название говорит о ее назначении;
• Смещение секции — адрес, с которого начинается секция;
• Флаги — дополнительный флаг. Пока не используется;
• Section count — количество секций.

Далее идет секция с символами.

Заголовок содержит информацию о количестве записей в таблице. Каждая запись содержит искаженное имя, местоположение символа в файле исходного кода, информацию о связи и длительность хранения.

Наконец, раздел Факты.

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

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

additionalBytes = (align - data.size() % align) % align

Допустим, у нас уже есть данные в файле — и они записаны следующим образом:

Тогда мы хотим вставить туда целое число типа int.

Align(x) = alignof(decltype(x)) = 4 bytes
Size(x) = sizeof(x) = 4 bytes
data.size = 3 bytes
additionalBytes = (align - data.size() % align) % align = 
= (4 - 3 % 4) % 4 = 1 byte;

Мы получаем сдвиг на 1 байт. Теперь мы можем вставить целое число.

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

Однако здесь есть несколько подводных камней.

Некоторое время назад мой коллега написал статью «Linux kernel turns 30: поздравления от PVS-Studio». Довольно интересная статья! Почитайте, когда у вас будет время. После того, как мой коллега начал анализировать ядро Linux, он получил общий .dfo файл размером 30 ГБ! Мы попытались выяснить причину и обнаружили ошибку. К этому времени мы уже знали, как определить категорию связи символов. Однако мы все равно записали их все в общий файл .dfo. Мы сделали это, чтобы сделать анализ более точным в конкретных единицах перевода, в которых были определены эти символы. Давайте посмотрим на рисунок:

Как я уже упоминал, для каждой единицы перевода создаются файлы .dfo. Затем они объединяются в один файл. После этого PVS-Studio использует только этот файл и исходные файлы для дальнейшего анализа.

Но когда мы проверяли ядро Linux, то обнаружили, что символов с внутренней связью больше, чем с внешней. Это привело к такому большому файлу .dfo. Решение было очевидным. Нужно было объединить только символы с внешней связью на этапе слияния. И во время второго прохода анализатора мы последовательно загрузили 2 файла .dfo — объединенный файл и файл, полученный после первого этапа. Это позволило нам объединить все символы с внешней связью, полученные после анализа всего проекта, и символы с внутренней связью для конкретной единицы перевода. Таким образом, размер файла не превысил 200 МБ.

Но что делать, если есть 2 символа с одинаковым именем и подписью, и один из них имеет внешнюю привязку? Это определенно нарушение УСО. Не стоит, чтобы скомпилированная программа содержала такое. А конфликт между символами может возникнуть, если анализатор начнет проверять файлы, которые на самом деле не слиты. Например, CMake генерирует общий файл compile_commands.json для всего проекта, не принимая во внимание команды компоновщика. Мы обсудим это подробно чуть позже. К счастью, даже если УСО нарушено, мы все равно можем продолжить анализ (при условии, что семантическая информация символов совпадает). В этом случае можно просто выбрать один из символов. Если информация не совпадает, то нам придется удалить из таблицы все символы с этой сигнатурой. Тогда анализатор потеряет часть информации — однако он все равно сможет продолжить анализ. Например, это может произойти, когда один и тот же файл включается в анализ несколько раз, при условии, что его содержимое меняется в зависимости от флагов компиляции (например, с помощью #ifdef).

Глубокий анализ

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

Мы остановились на том, что можно передавать информацию из одного файла в другой. Но что, если цепочка данных длиннее? Рассмотрим пример:

Нулевой указатель передается через main -> f1 -> f2. Анализатор может запомнить, что f1 получает указатель, и что указатель разыменовывается в f2. Но анализатор не заметит, что f2 получает нулевой указатель. Чтобы заметить это, анализатор сначала должен выполнить интермодулярный анализ функций main и f1, чтобы понять, что указатель ptr является нулевым. Затем анализатор должен снова проверить функции f1 и f2. Но в текущей реализации этого не произойдет. Давайте посмотрим на следующую схему:

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

Но как определить, какие единицы перевода мы должны проанализировать еще раз? Здесь поможет анализ внешних вызовов функций. Для этого нам нужно построить граф вызовов. Вот только у нас его нет. Мы хотим создать граф вызовов в будущем, но на момент написания этой статьи такой функциональности нет. Кроме того, как правило, программа содержит достаточно много внешних вызовов. И мы не можем быть уверены, что это будет эффективно. Единственное, что мы можем сделать, это еще раз проанализировать все единицы перевода и переписать факты. Каждый проход увеличивает глубину анализа на 1 функцию. Да, это занимает некоторое время. Но мы можем делать это хотя бы раз в неделю по выходным. Это лучше, чем ничего. Если в будущем мы создадим промежуточное представление, то решим эту проблему.

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

Инкрементный анализ

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

Первая строка показывает статус всего проекта. Вторая строка иллюстрирует файлы, которые были изменены. После этого

• генерируются файлы .dfo для измененных исходных файлов;
• полученные файлы объединяются с единым файлом;
• происходит полный анализ всех файлов проекта.

Анализ проектов, состоящих из нескольких частей

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

PVS-Studio поддерживает 2 формата проектов на C и C++ — Visual Studio (.vcxproj) и JSON Compilation Database. У нас нет проблем с Visual Studio (.vcxproj). Этот формат предоставляет всю необходимую информацию для определения компонентов проекта. Но формат JSON Compilation Database немного сложнее…

Формат JSON Compilation Database (он же compile_commands.json) предназначен для инструментов анализа кода, таких как clangd, например. И до сих пор у нас не было с ним проблем. Однако есть один нюанс — все команды компиляции в нем записаны в плоской структуре (одним списком). И, к сожалению, в эти команды не входят команды для компоновщика. Если один файл используется в нескольких частях проекта, то команды для него будут записаны одна за другой без какой-либо дополнительной информации. Проиллюстрируем это на примере. Для генерации compile_commands.json мы будем использовать CMake. Предположим, у нас есть общий проект и 2 его компонента:

// CMakeLists.txt
....
project(multilib)
....
add_library(lib1 A.cpp B.cpp)
add_library(lib2 B.cpp)

> cmake -DCMAKE_EXPORT_COMPILE_COMMADS=On /path/to/source-root

// compile_commands.json

[
  {
    "file": "....\A.cpp",
    "command": "clang-cl.exe ....\A.cpp -m64 .... -MDd -std:c++latest",
    "directory": "...\projectDir"
  },
  {
    "file": "....\B.cpp",
    "command": "clang-cl.exe ....\B.cpp -m64 .... -MDd -std:c++latest",
    "directory": "...\projectDir "
  },
  {
    "file": "....\B.cpp",
    "command": "clang-cl.exe ....\B.cpp -m64 .... -MDd -std:c++latest",
    "directory": "....\projectDir "
  }
]

Как видите, когда мы компилируем весь проект, полученный compile_commands.json содержит команду для B.cpp. Причем эта команда повторяется дважды. В этом случае анализатор загрузит символы одной из команд, так как они идентичны. Но если сделать содержимое файла B.cpp зависимым от флагов компиляции (например, с помощью директив препроцессора), то такой гарантии не будет. На момент написания этой статьи данная проблема не была решена должным образом. Мы планируем это сделать, но пока приходится работать с тем, что есть.

В качестве альтернативы я обнаружил возможность управлять содержимым compile_commands.json через CMake. Однако этот подход не очень гибкий. Нам приходится вручную изменять CMakeLists.txt. В CMake 3.20 и более новых версиях можно указать свойство EXPORT_COMPILE_COMMANDS для цели. Если оно установлено в TRUE, команды будут записываться в конечный файл для цели. Таким образом, добавив несколько строк в CMakeLists.txt, мы можем сгенерировать необходимый набор команд:

CMakeLists.txt:
....
project(multilib)
....

set(CMAKE_EXPORT_COMPILE_COMMANDS FALSE) #disable generation for all targets

add_library(lib1 A.cpp B.cpp)
add_library(lib2 B.cpp)

#enable generatrion for lib2
set_property(TARGET lib2 PROPERTY EXPORT_COMPILE_COMMANDS TRUE)

Затем мы запускаем анализ файла compile_commands.json:

pvs-studio-analyzer analyze -f /path/to/build/compile_commands.json ....

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

PVS-Studio предоставляет возможность запуска анализа с помощью базы данных компиляции непосредственно через CMake. Для этого необходимо использовать специальный модуль CMake. Подробнее об этом можно узнать в документации. На момент написания этой статьи мы еще не реализовали поддержку интермодульного анализа. Однако это направление весьма перспективно.

Другим вариантом может быть отслеживание команд компоновщика, как мы это делаем для команд компиляции, с помощью утилиты CLMonitor или через strace. Возможно, мы сделаем это в будущем. Однако у такого подхода есть и недостаток — чтобы отследить все вызовы, необходимо собрать проект.

Подключение семантического модуля для сторонней библиотеки

Представьте себе следующую ситуацию. У вас есть основной проект, который необходимо проанализировать. К проекту подключены предварительно скомпилированные сторонние библиотеки. Будет ли интермодульный анализ работать с ними? К сожалению, ответ «нет». Если в вашем проекте нет команд компиляции для сторонних библиотек, то семантический анализ не будет работать с ними, так как доступ возможен только к заголовочным файлам. Однако существует теоретическая возможность заранее подготовить модуль семантической информации для библиотеки и подключить его к анализу. Для этого нужно объединить этот файл с основным файлом проекта. На момент написания статьи это можно сделать только вручную. Однако в будущем мы хотим автоматизировать этот процесс. Вот основная идея:

1. Нам нужно заранее подготовить объединенный .dfo файл для сторонней библиотеки, проанализировав ее код.
2. Выполните первый этап межмодульного анализа и подготовьте .dfo файлы для каждой единицы перевода основного проекта.
3. Объедините все семантические модули проекта с файлом сторонней библиотеки. Если это не нарушает ODR, то все пройдет гладко.
4. Выполните третий этап межмодульного анализа.

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

Оптимизации

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

Интернализация строк

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

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

Теперь все секции, кроме секции данных, содержат только соответствующие адреса строк.

Префиксное дерево

Несмотря на то, что строки теперь уникальны, данные в них по-прежнему дублируются. Например, на рисунке ниже все пути имеют одну и ту же первую часть, или префикс:

И такая ситуация повторяется довольно часто. Однако триэ решает эту проблему.

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

Заключение

Интермодульный анализ предоставляет множество ранее недоступных возможностей и помогает найти интересные ошибки, которые трудно обнаружить при обычном просмотре кода. Тем не менее, нам предстоит еще многое сделать для оптимизации и расширения функциональности. Вы можете попробовать интермодулярный анализ прямо сейчас. Он доступен в PVS-Studio v7.14 и более новых версиях. Скачать последнюю версию анализатора можно на нашем сайте. Хотите узнать больше об интермодульном анализе? Прочитайте предыдущую статью, если вы еще этого не сделали. Если у вас есть какие-либо проблемы или идеи, не стесняйтесь писать нам, мы обязательно постараемся помочь. Обратите внимание, что при запросе пробной версии по указанной ссылке вы можете получить лицензию Enterprise на 30 дней. Мы надеемся, что этот режим поможет исправить ошибки в вашем проекте.