Как обнаружить переполнение 32-битных переменной в длинных циклах в 64-битной программе

Одна из проблем, с которой сталкиваются разработчики 64-битных приложений, это переполнение 32-битных переменных в очень длинных циклах. С этой задачей хорошо справляется анализатор кода PVS-Studio (набор диагностик Viva64). На тему переполнения переменных в циклах есть ряд вопросов на сайте StackOverflow.com. Но поскольку мои ответы могут счесть исключительно рекламными, а не как полезную информацию, я решил описать возможности PVS-Studio в статье.

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

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

Итак, проблема. В 64-битной программе происходит переполнение целочисленных 32-битных типов. Речь идёт о таких типах как int, unsigned, long (если это Win64 ^[1]). Необходимо как-то выявить все такие опасные места. Это может сделать анализатор PVS-Studio, о чем мы и поговорим.

Рассмотрим различные варианта переполнения переменных, связанных с длинными циклами.

Первая ситуация. Описана на сайте StackOverflow здесь: "How can elusive 64-bit portability issues be detected? ^[2]". Имеется код следующего вида:

int n;
size_t pos, npos;
/* ... initialization ... */
while((pos = find(ch, start)) != npos)
{
    /* ... advance start position ... */
    n++; // this will overflow if the loop iterates too many times
}

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

В 64-битной программе длина строки уже может быть больше INT_MAX и соответственно переменная n может переполниться. Это приведёт к неопределённому поведению программы. Не надо думать, что переполнение просто превратит число 2147483647 в -2147483648. Это именно неопределённое поведение и предсказать последствия невозможно. Для тех, кто не верит, что переполнение знаковой переменной приводит к неожиданным изменениям в работе программы, предлагаю познакомиться с моей статьёй "Undefined behavior ближе, чем вы думаете ^[3]".

Итак, нужно обнаружить, что переменная n может переполниться. Нет ничего проще. Запускаем PVS-Studio и получаем предупреждение:

V127 ^[4] An overflow of the 32-bit 'n' variable is possible inside a long cycle which utilizes a memsize-type loop counter. mfcapplication2dlg.cpp 190

Если изменить тип переменной n на size_t, то ошибка, а соответственно и сообщение анализатора, исчезнет.

Там же приводится ещё один пример кода, который требуется выявить:

int i = 0;
for (iter = c.begin(); iter != c.end(); iter++, i++)
{
    /* ... */
}

Запускаем PVS-Studio и вновь получаем предупреждение V127:

V127 An overflow of the 32-bit 'i' variable is possible inside a long cycle which utilizes a memsize-type loop counter. mfcapplication2dlg.cpp 201

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

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

• Статья PVS-Studio для Visual C++ ^[5].
• Статья Практика использования анализатора PVS-Studio ^[6].
• Документация ^[7].

Отмечу также, что мы имеем опыт портирования ^[8] большого проекта в 9 млн. строк кода на 64-битную платформу. И PVS-Studio отлично показал себя в работе над этим проектом.

Перейдем к следующей теме на сайте StackOverflow: "Can Klocwork (or other tools) be aware of types, typedefs and #define directives? ^[9]".

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

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

Подошел человек к решению задачи неправильно. В этом он не виноват. Он просто не знает о существовании PVS-Studio. Сейчас вы поймете почему я так говорю.

Итак, он планирует искать:

for (int i = 0; i < 10; i++)
    // ...

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

Править все циклы подряд, заменяя int, например, на intptr_t тоже плохой вариант. Это очень много работы и изменений в коде.

Анализатор PVS-Studio может помочь. Приведённый выше цикл он не найдёт. Потому, что его и не надо искать. В нём просто нет места для ошибки. Цикл выполняет 10 итераций. И никакого переполнения в нем быть не может. Так что нечего программисту тратить время на этот участок кода.

Зато анализатор укажет вот на такие циклы:

void Foo(std::vector<float> &v)
{
  for (int i = 0; i < v.size(); i++)
    v[i] = 1.0;
}

Анализатор выдаст сразу 2 предупреждения. Первое предупреждает о том, что в выражении 32-битный тип сравнивается с memsize-типом ^[10]:

V104 ^[11] Implicit conversion of 'i' to memsize type in an arithmetic expression: i < v.size() mfcapplication2dlg.cpp 210

И действительно, тип переменной i не подходит для организации длинных циклов.

Второе предупреждение говорит, что странно в качестве индекса использовать 32-битную переменную. Если массив большой, то код ошибочен.

V108 ^[12] Incorrect index type: v[not a memsize-type]. Use memsize type instead. mfcapplication2dlg.cpp 211

Корректный код должен выглядеть так:

void Foo(std::vector<float> &v)
{
  for (std::vector<float>::size_type i = 0; i < v.size(); i++)
    v[i] = 1.0;
}

Код стал длинным и некрасивым, поэтому появляется соблазн использовать ключевое слово auto, но этого делать нельзя — измененный таким образом код вновь некорректен:

for (auto i = 0; i < v.size(); i++)
  v[i] = 1.0;

Так как константа 0 имеет тип int, то и переменная i будет иметь тип int. И мы вернулись к тому, с чего начали. Кстати раз зашла речь о новых возможностях стандарта языка С++, предлагаю взглянуть на статью "C++11 и 64-битные ошибки ^[13]".

Думаю, можно пойти на компромисс и написать не идеальный, но правильный код:

for (size_t i = 0; i < v.size(); i++)
  v[i] = 1.0;

Примечание. Конечно, ещё более правильным будет использовать итераторы или алгоритм fill(). Но мы говорим о поисках переполнения 32-битных переменных в старых программах. Поэтому я и не рассматриваю такие варианты исправления кода. Это уже совсем другая тема.

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

void Foo(int n)
{
  float A[100];
  for (int i = 0; i < n; i++)
    A[i] = 1.0;
}

Заключение

Анализатор PVS-Studio является лидером по поиску 64-битных ошибок. Изначально, он как раз и создавался для помощи программистам в портирования их программ на 64-битные системы. В то время он ещё назывался Viva64. Это уже потом, он превратился в анализатор общего назначения, но существовавшие 64-битные диагностики никуда не исчезли и всё также готовы вам помочь.

Скачать демонстрационную версию можно здесь ^[14].

Подробнее о разработке 64-битных программ ^[15].

Автор: PVS-Studio

Источник ^[16]