Предлагаем вашему вниманию интересную историю о поиске бага внутри анализатора PVS-Studio. Да, мы тоже допускаем ошибки, но мы готовы засучить рукава и залезть в самую глубину "кроличьей норы".


1005_StoriesFromSupport_ru/image1.png


Небольшое предисловие


Наш коллега уже рассказывал про нашу техническую поддержку. Но всегда интересно послушать какие-то истории, и они у нас есть.


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


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


  • отдел разработки C и C++ анализатора;
  • отдел разработки C# анализатора;
  • отдел Tools & DevOps;
  • отдел web-разработки;
  • отдел разработки CRM-системы.

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



Третий отдел занимается разработкой и поддержкой всех связующих компонентов для наших анализаторов:


  • интеграция с популярными IDE – Visual Studio 2010-2022, IntelliJ IDEA, Rider, CLion;
  • интеграция с платформой непрерывного контроля качества SonarQube;
  • интеграция с игровыми движками Unreal Engine и Unity;
  • утилита для конвертации отчёта анализатора в различные форматы – SARIF, TeamCity, HTML, FullHTML и др.;
  • утилита для оповещения команд разработчиков о найденных подозрительных местах в коде.

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


Теперь же познакомимся поближе именно с поддержкой C++ отдела. Обращения в поддержку по C и C++ анализатору можно разделить на следующие виды:


  1. Диагностическое правило выдаёт ложноположительное срабатывание. Разработчику сильно повезёт, если пользователь присылает пример для воспроизведения. В большинстве случаев присланные по переписке примеры максимально упрощаются, и поправить диагностику иногда становится испытанием.
  2. Анализатор не выдаёт срабатывание на пользовательском примере. Здесь возможны два исхода:
    • анализатор молчит специально. Здесь вы можете подробнее ознакомиться с причинами, почему он это делает в некоторых ситуациях;
    • пользователь прав. Мы получаем от него необходимые уточнения по примеру, а дальше решаем: либо дорабатываем существующую диагностику, либо пишем новую.
  3. Анализатор не разобрал какую-либо конструкцию языка C и C++. Грамматики этих языков позволяют писать очень запутанный код, и порой анализатор не справляется. В таких ситуациях пользователи присылают нам ошибки V001. Чтобы исправлять такие проблемы, обычно мы запрашиваем минимально воспроизводимые примеры или промежуточные файлы для анализа (*.i и *.cfg файлы).
  4. Падение ядра C и C++ анализатора. От ошибок не застрахован никто, падения иногда происходят. С нашим анализатором тоже (V003). Здесь очень помогают пользователи, присылая стектрейсы, дампы памяти или промежуточные файлы для анализа.
  5. Не работает один из многих сценариев использования продукта. Проблемы подобного рода обладают широчайшим разнообразием, и описать их всех в паре предложений не удастся.

История, о которой говорится в заголовке статьи, началась как раз с письма пользователя в поддержку. Клиент жаловался на зависание инкрементального анализа, поэтому далее речь пойдёт именно о последнем варианте.


Инкрементальный анализ, который не смог


1005_StoriesFromSupport_ru/image2.png


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


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

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


Command "/usr/bin/c++ -DBOOST_ASIO_DYN_LINK ...." returned code 3.

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


Многим C++ разработчикам знакома боль при компиляции проектов с подключенными библиотеками Boost – время сборки сильно повышается. Препроцессирование также страдает от этого. Как видно из вышеприведенной команды, пользователь использует в проекте Boost. Ранее нам также поступали письма с подобной проблемой: при высокой загрузке процессора файлы не успевают препроцессироваться.


У нас уже достаточно давно витала в воздухе идея убрать это жёсткое ограничение с препроцессированием в 30 секунд. И снова похожий кейс. Решено – убираем таймаут. Можно высылать пользователю бету и ждать ответа.


Уже мы собирались забыть о пофикшенном баге, как пользователь отписывает нам о результатах с новой бетой:


  • ранее анализ доходил до конца, но была куча V008 в отчёте;
  • теперь анализ зависает на этапе парсинга тех же самых файлов (примерно на 86 % прогресса).

Что же это за парсинг файлов такой?

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


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


Что ж, проблема оказалась более сложной, продолжаем копать.


1005_StoriesFromSupport_ru/image3.png


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


exclude-path=*/generated/sip*
exclude-path=*/pacs/soapserver/generated/*
exclude-path=*/soap_engine/*
exclude-path=*/tech1utils/tests/googlemock/*
exclude-path=*/sdk-common/*
exclude-path=*/tech1grabbers/SDKs/*
# ....
# 200+ similar entries
# ....
exclude-path=/mnt/nvme/jenkins/workspace/..../lpr-ide.cpp

Настройка exclude-path позволяет подавлять предупреждения на код из third-party библиотек и тестов. В типовой ситуации пользователи указывают либо несколько путей до конкретных директорий, либо используют шаблон поиска. И количество записей редко превышает 30-40 штук. Здесь же было 200+ различных путей с исключенными файлами, включая шаблоны поиска. Мы заподозрили, что наш алгоритм исключения файлов из анализа, написанный 10+ лет назад, уже просто не мог быстро "переварить" такое количество записей в конфигурационном файле.


Почему оно тормозит?

Алгоритм исключения файлов из анализа работал так:


  1. Собираем платформо-специфичные пути до директорий с системными библиотеками. В C и C++ анализаторе уже "вшиты" некоторые стандартные пути, например:
    • "?:\\program files (x86)\\microsoft visual studio *\\vc\\*"
    • "/usr/include/"
    • "/usr/local/Cellar"
    • и другие пути, примерно до 30 штук.
  2. Объединяем их с путями, заданными пользователем.
  3. Сопоставляем входной путь с каждым из собранного списка:
    • если исключаемый путь содержит символы "?" или "*", то используем платформо-специфичную функцию для поиска по шаблону. На Windows – это PathMatchSpec, на *nix-подобных ОС – fnmatch;
    • иначе проверяем, начинается ли входной путь с пути из собранного списка. При сравнении строк используется платформо-специфичная функция сравнения. Как мы помним, на Windows сравнение путей происходит без учёта регистра, на *nix-подобных ОС – преимущественно с учётом регистра.

Как можно легко заметить, алгоритм крайне не оптимизирован. Каждый путь из собранного списка сначала подвергается сканированию на наличие wildcard-символов – это полный проход по строке в худшем случае. Затем выбирается способ сравнения, и в худшем случае мы имеем уже 2 прохода по пути. И эти два прохода выполняются на все строки в списке.


Первая оптимизация, которая сразу пришла в голову, – это заранее разделить исключаемые пути на шаблоны поиска (глобы) и обычные пути. Так в анализаторе родился новый класс — PathMatcher, который содержит 2 контейнера. Один контейнер для шаблонов и один для стандартных путей:


class PathMatcher
{
// ....
private:
  using GlobsCollection = std::set<std::string, std::less<>>;
  using PathsCollection = ???;

  GlobsCollection m_globs; // шаблоны
  PathsCollection m_paths; // обычные пути
};

Если с шаблонами поиска всё достаточно просто – их можно хранить в стандартном контейнере std::set для устранения дубликатов – то с путями есть нюанс. Да, здесь также можно воспользоваться ассоциативным контейнером вроде std::set, но в большинстве случаев переданные пользователем пути будут содержать какой-то общий префикс и различаться в самом конце:


/home/user/folderToExclude/fileToExclude.cpp
/home/user/folderToExclude/
|______общий префикс______|

Всё намекает на структуру данных "префиксное дерево". Это позволяет оптимизировать как потребление памяти, так и поиск максимально длинного префикса. Поискав уже готовые реализации, мы остановились на Tessil/hat-trie. Для того чтобы различать файлы от директорий, мы применяем tsl::htrie_map, у которого ключом будет наш путь, а значением – тип файла.


Теперь алгоритм работает примерно так:


  1. При переборе конфигурационного файла мы определяем, в какой контейнер внутри класса PathMatcher класть исключенный путь:
    • если был найден wildcard-символ, то кладём в контейнер для шаблонов;
    • иначе кладём в префиксное дерево.
  2. Сопоставляем входной путь с путями внутри класса PathMatcher так:
    • ищем общий префикс с путями в префиксном дереве. Если он находится, то файл исключается из анализа;
    • иначе мы перебираем все шаблоны и вызываем платформо-специфичные функции для сравнения с входным файлом.

После оптимизации алгоритма на тестовом примере с 200+ исключёнными путями в конфигурационном файле анализатор в несколько раз быстрее стал приступать к парсингу и анализу файлов. Это определенно был успех. Дальше оставалось дело за малым – собрать бету, выдать пользователю и радоваться маленькой победе.


Убийца – дворецкий!


1005_StoriesFromSupport_ru/image4.png


Но праздновать победу (закрывать тикет) было ещё рано. Пользователь опять пишет о том же самом зависании.


Что ж, быстрые правки не помогли, приходится ещё сильнее погружаться в эту проблему. В этот раз мы решили попросить пользователя запустить нашу утилиту под strace и прислать все сформированные логи. Если кто не знает, утилита strace позволяет отследить все системные вызовы программы и многое другое. Кстати, мы же используем её для одного из вариантов внедрения анализатора в свой проект (трассировка вызовов компиляторов).


Вот команда, которой пользователь формировал логи:


strace -y -v -s 4096 -ff -o strace-logs/log.txt -- pvs-studio-analyzer ....

Он оставил программу поработать примерно на 20 минут перед убийством процесса. Поскольку во время зависания утилита strace продолжала писать информацию в логи, то их размер получился внушительный – 22795 файлов с суммарным весом в 278 ГБ (!) без сжатия.


Сначала посмотрели выхлоп strace. И сразу же увидели огромное количество вызовов nanosleep. Это означало, что дочерние процессы, порождаемые утилитой pvs-studio-analyzer, почему-то сидели в бесконечном ожидании. Мы прошерстили логи сверху вниз и таки нашли проблему:


1005_StoriesFromSupport_ru/image6.gif


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


В ОС Linux при открытии файла ему присваивается специальный номер – дескриптор, который затем используется для работы с ним: чтения, записи, просмотра атрибутов и т.д. Количество таких дескрипторов ограничено и определяется настройками системы.


Кстати, проблему воспроизвести очень легко. Для воспроизведения проблемы достаточно написать следующий CMakeLists.txt:


cmake_minimum_required(VERSION 3.5)
project(many-files LANGUAGES C CXX)

set(SRC "")

foreach(i RANGE 10000)
  set(file "${CMAKE_CURRENT_BINARY_DIR}/src-${i}.c")
  file(TOUCH "${file}")
  set(SRC "${SRC};${file}")
endforeach()

add_library(many-files STATIC
            ${SRC})

Далее формируем кеш в директории с CMakeLists.txt и запускаем утилиту pvs-studio-analyzer версии ниже 7.18:


cmake -S . -B build -DCMAKE_EXPORT_COMPILE_COMMANDS=On
pvs-studio-analyzer analyze -f ./build/compile_commands.json -j -i -o pvs.log

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


Кто же был виновен?

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


Некоторые исходные файлы могут быть многократно скомпилированы в разных проектах с разными флажками в пределах одного "решения". При формировании препроцессированного файла с постфиксом ".PVS-Studio.i" нам приходится отрезать расширение у имени исходного файла. Это сделано из-за того, что некоторые препроцессоры отказываются препроцессировать файл, если итоговый содержит в имени постфиксы вроде ".cpp", ".cxx" и др.


Это может привести к коллизии, если, например, препроцессируются два файла – "source.cpp" и "source.cxx". Для устранения состояния гонки мы производим блокировку результирующего пути – создаётся и открывается особый файл ".pvslock". Если происходит коллизия, то к имени следующего препроцессированного файла добавится число 1, 2, 3 и т. д.


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


Проблема была в том, что при перемещении объекта на первом этапе мы забывали снять блокировку. Это приводило к росту числа открытых временных файлов ".pvslock", и при превышении определенного числа файловых дескрипторов программа зависала.


Правка была достаточно простой – при перемещении объекта в кеш теперь снимается блокировка и файл ".pvslock" закрывается и уничтожается.


Мы исправили обработку ресурсов в программе, и проблема ушла. Подозреваем, что такая ошибка ранее ни у кого не возникала, т. к. Linux-версию анализатора больше используют на сборочных серверах в обычном режиме. Инкрементальный анализ чаще используют в связке с IDE, из которых на Linux мы полноценно поддерживаем только JetBrains CLion. Судя по всему, до того момента не находился пользователь с необходимостью анализировать проект в инкрементальном режиме с большим количеством файлов.


Третий раз выкатив клиенту бету, мы, наконец, решили проблему с зависанием.


Заключение


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


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


Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: ссылка.


Похожие статьи


  1. Один день из жизни разработчика PVS-Studio.
  2. Для тех, кто хочет поиграть в детектива: найди ошибку в функции из Midnight Commander.
  3. Когда дворецкий — жертва.
  4. Программные ошибки, которых не бывает.
  5. Как PVS-Studio оказался внимательнее, чем три с половиной программиста.
  6. В очередной раз анализатор PVS-Studio оказался внимательнее человека.

Комментарии (5)


  1. ImNotARobot
    28.10.2022 16:39
    +3

    Дано: анализатор, который зависает на 86 % прогресса. Что мы делаем? Правильно, оптимизации, а то алгоритм старый... Чтобы что? Чтобы быстрее доходило до зависания?

    Странный у вас подход обработки багов. Хорошо хоть пользователь идёт на встречу и проверяет ваши (заведомо неработающие) попытки фикса.


    1. Koshey_Immortal Автор
      28.10.2022 17:07
      +17

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


    1. Mingun
      28.10.2022 17:08
      +2

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


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


  1. propell-ant
    28.10.2022 18:24
    +5

    Забавно, я где-то год назад воевал с проблемой exclude в MSBuild. Там дескрипторы не утекали, но алгоритмическая сложность обработки exclude была, видимо, квадратичной.
    На двух-трех записях тормозов не видно, а на десяти сборка длилась по 30 минут (на проекте из чуть больше тысячи файлов).
    Докопал до какого-то обсуждения в форуме, где человек нашел место в исходнике, где был рекурсивный обход всех файлов, и на каждом брался полный путь и делался паттерн-мэтч.
    К слову, фича-реквест на exclude при поиске по всем файлам проекта в VisualStudio провисел лет десять, прежде чем его прикрутили в VS2019.


  1. Tatikoma
    29.10.2022 01:41
    +2

    Удалось ли по результатам добавить инспекцию, которая выявляет данный конкретный баг в исходном коде?