64-битный конь, который умеет считать

Аннотация

Статья посвящена особенностям поведения компилятора Visual C++ при генерации 64-битного кода и связанными с этим потенциальными ошибками.

Введение

Феномен "Умного Ганса", коня мистера фон Остена, был описан в 1911 году [1]. Умный Ганс был знаменит тем, что умел читать и решал математические задачки, выстукивая ответ передним копытом. Конечно, было много скептиков. Поэтому способности Ганса проверялись комиссией экспертов, которая установила, что конь демонстрирует их без помощи мистера фон Остена. Но как мог существовать такой — человеческий! — уровень интеллекта у простой лошади? Психолог О. Пфангст с чрезвычайной тщательностью выполнил серию экспериментов, в результате которых обнаружил, что Ганс получал едва уловимые неумышленные подсказки от тех, кто задавал ему вопросы. Например, после того как Ганса о чем-то спрашивали, люди устремляли свой взгляд на его переднее копыто, с помощью которого конь "отвечал". Но как только Ганс ударял копытом нужное число раз, спрашивающие совсем чуть-чуть поднимали свои глаза или голову в ожидании завершения его ответа. И конь, который был натренирован замечать и использовать эти почти неуловимые для наблюдателей движения, воспринимал их как сигналы к прекращению своих действий. Со стороны это всегда выглядело как правильный ответ на вопрос.

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

1. Потенциальные ошибки

Я явлюсь автором и соавтором ряда статей, посвященных проблематике разработки 64-битных приложений. Статьи вы можете найти на нашем сайте. В этих статьях, я стараюсь использовать термин "потенциальная ошибка" или "скрытая ошибка", а не просто "ошибка" [2, 3, 4].

Я объясняю это тем, что один и тот же код можно рассматривать как корректным, так и некорректным в зависимости от его назначения. Простой пример - использование для индексации элементов массива переменной типа int. Если с помощью этой переменной мы обращаемся к массиву графических окон, то все корректно. Не бывает нужно, да и не получится работать с миллиардами окон. А вот индексация с использованием переменной типа int к элементам массива в 64-битных математических программах или базах данных, вполне может представлять собой проблему, когда количество элементов выйдет из диапазона 0..INT_MAX.

Но есть и еще одна, куда более тонкая причина называть ошибки "потенциальными". Дело в том, проявит себя ошибка или нет, зависит не только от входных данных, но и от настроения оптимизатора компилятора. Я долго обходил эту тему, поскольку большинство этих ошибок хорошо проявляют себя в debug-версии, и "потенциальны" только в release-версиях. Однако не всякую программу, собранную как debug, можно отлаживать на больших объемах данных. Возникает ситуация, когда debug-версия тестируется только на самых простых наборах данных. А нагрузочное тестирование и тестирование конечными пользователями на реальных данных, выполняется на release-версиях, где ошибки могут быть временно скрыты. Поэтому я решил поделиться теми знаниями, которые есть. Надеюсь, я смогу убедить, что при переносе программы на другую платформу опасно полагаться только на проверки этапа исполнения (юнит-тесты, динамический анализ, ручное тестирование). Вы скажете, все это чтобы продвигать инструмент Viva64. Да, для этого, но все-таки послушайте страшные истории, которые я сейчас буду вам рассказывать. Я люблю их рассказывать.

2. С чего все началось

- А почему у тебя в коде подряд два одинаковых JMP'а стоят?

- А вдруг первый не сработает.

Впервые я столкнулся с особенностями оптимизации компилятора Visual C++ 2005 при подготовке программы PortSample. Это проект, который входит в состав дистрибутива Viva64 и предназначен для демонстрации всех ошибок, которые диагностирует анализатор Viva64. Примеры, которые содержатся в этом проекте должны корректно работать в 32-битном режиме и приводить к ошибкам в 64-битном варианте. В отладочной версии все работало замечательно, а вот с release версией возникли затруднения. Тот код, который в 64-битном режиме должен был зависать или приводить к падению - успешно работал! Причина оказалась в оптимизации. Решением стало дополнительное избыточное усложнение кода примеров и расстановка ключевых слов "volatile", которые вы во множестве сможете наблюдать в проекте PortSample.

То же самое относится и к Visual C++ 2008. Код будет конечно несколько разным, но все что будет написано в этой статье можно отнести как к Visual C++ 2005, так и к Visual C++ 2008. И далее в статье различий делаться не будет.

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

3. Фантомы

Глава будет длинная и скучная, поэтому начну с анекдота, который является ее кратким содержанием:

Шел Илья Муромец по лесу и вышел на поляну, на которой Змей Горыныч сидел. Подбежал Илья Муромец к Змею Горынычу и срубил ему единственную голову. А у Змея Горыныча вместо этой головы две выросло. Срубил Илья две головы, выросло 4. Срубил 4, выросло 8... И так продолжалось это час, два, три ... А потом срубил Илья Муромец Змею Горынычу 32768 голов и умер Змей Горыныч, ибо был он 16-ти разрядный.

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

int index = 0;
size_t arraySize = ...;
for (size_t i = 0; i != arraySize; i++)
  array[index++] = BYTE(i);

Данный код корректно заполняет весь массив значениями, даже если размер массива гораздо больше INT_MAX. Теоретически это невозможно, поскольку переменная index имеет тип int. Через некоторое время из-за переполнения должен произойти доступ к элементам по отрицательному индексу. Однако оптимизация приводит к генерации следующего кода:

0000000140001040  mov         byte ptr [rcx+rax],cl 
0000000140001043  add         rcx,1 
0000000140001047  cmp         rcx,rbx 
000000014000104A  jne         wmain+40h (140001040h)

Как видите, используются 64-битные регистры и переполнение не происходит. Но сделаем совсем маленькое исправление кода:

int index = 0;
for (size_t i = 0; i != arraySize; i++)
{
  array[index] = BYTE(index);
  ++index;
}

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

0000000140001040  movsxd      rcx,r8d 
0000000140001043  mov         byte ptr [rcx+rbx],r8b 
0000000140001047  add         r8d,1 
000000014000104B  sub         rax,1 
000000014000104F  jne         wmain+40h (140001040h)

Происходит то самое переполнение, которое должно было быть и в предыдущем примере. Значение регистра r8d = 0x80000000 расширяется в rcx как 0xffffffff80000000. И как следствие - запись за пределами массива.

Рассмотрим другой пример оптимизации и как легко все испортить. Пример:

unsigned index = 0;
for (size_t i = 0; i != arraySize; ++i) {
  array[index++] = 1;
  if (array[i] != 1) {
    printf("Error\n");
    break;
  }
}

Ассемблерный код:

0000000140001040  mov         byte ptr [rdx],1 
0000000140001043  add         rdx,1 
0000000140001047  cmp         byte ptr [rcx+rax],1 
000000014000104B  jne         wmain+58h (140001058h) 
000000014000104D  add         rcx,1 
0000000140001051  cmp         rcx,rdi 
0000000140001054  jne         wmain+40h (140001040h) 

Компилятор решил использовать 64-битный регистр rdx для хранения переменной index. В результате код может корректно обрабатывать массивы размером более UINT_MAX.

Но мир хрупок. Достаточно немного усложнить код и он станет неверен:

volatile unsigned volatileVar = 1;
...
unsigned index = 0;
for (size_t i = 0; i != arraySize; ++i) {
  array[index] = 1;
  index += volatileVar;
  if (array[i] != 1) {
    printf("Error\n");
    break;
  }
}

Использование вместо index++ выражения "index += volatileVar;" приводит к тому, что в коде начинают участвовать 32-битные регистры, из-за чего происходят переполнения:

0000000140001040  mov    ecx,r8d 
0000000140001043  add    r8d,dword ptr [volatileVar (140003020h)] 
000000014000104A  mov    byte ptr [rcx+rax],1 
000000014000104E  cmp    byte ptr [rdx+rax],1 
0000000140001052  jne    wmain+5Fh (14000105Fh) 
0000000140001054  add    rdx,1 
0000000140001058  cmp    rdx,rdi 
000000014000105B  jne    wmain+40h (140001040h) 

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

ptrdiff_t UnsafeCalcIndex(int x, int y, int width) {
  int result = x + y * width;
  return result;
}
...
int domainWidth = 50000;
int domainHeght = 50000;
for (int x = 0; x != domainWidth; ++x)
  for (int y = 0; y != domainHeght; ++y)
    array[UnsafeCalcIndex(x, y, domainWidth)] = 1;

Данный код не может корректно заполнить массив, состоящий из 50000*50000 элементов. Невозможно это по той причине, что при вычислении "int result = x + y * width;" должно происходить переполнение.

Благодаря чуду массив все же корректно заполняется в release-варианте. Функция UnsafeCalcIndex встраивается внутрь цикла, используются 64-битные регистры:

0000000140001052  test        rsi,rsi 
0000000140001055  je          wmain+6Ch (14000106Ch) 
0000000140001057  lea         rcx,[r9+rax] 
000000014000105B  mov         rdx,rsi 
000000014000105E  xchg        ax,ax 
0000000140001060  mov         byte ptr [rcx],1 
0000000140001063  add         rcx,rbx 
0000000140001066  sub         rdx,1 
000000014000106A  jne         wmain+60h (140001060h) 
000000014000106C  add         r9,1 
0000000140001070  cmp         r9,rbx 
0000000140001073  jne         wmain+52h (140001052h)

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

Немного модифицируем (усложним) функцию UnsafeCalcIndex. Обратите внимание, что логика функции ничуть не изменилась:

ptrdiff_t UnsafeCalcIndex(int x, int y, int width) {
  int result = 0;
  if (width != 0)
    result = y * width;
  return result + x;
}

Результат - аварийное завершение программы, при выходе за границы массива:

0000000140001050  test        esi,esi 
0000000140001052  je          wmain+7Ah (14000107Ah) 
0000000140001054  mov         r8d,ecx 
0000000140001057  mov         r9d,esi 
000000014000105A  xchg        ax,ax 
000000014000105D  xchg        ax,ax 
0000000140001060  mov         eax,ecx 
0000000140001062  test        ebx,ebx 
0000000140001064  cmovne      eax,r8d 
0000000140001068  add         r8d,ebx 
000000014000106B  cdqe             
000000014000106D  add         rax,rdx 
0000000140001070  sub         r9,1 
0000000140001074  mov         byte ptr [rax+rdi],1 
0000000140001078  jne         wmain+60h (140001060h) 
000000014000107A  add         rdx,1 
000000014000107E  cmp         rdx,r12 
0000000140001081  jne         wmain+50h (140001050h)

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

4. Диагностика потенциальных ошибок

Программа - это последовательность обработки ошибок. (с) Неизвестный автор

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

Как и в истории с конем, первое впечатление может быть обманчиво. И то, что ваша программа успешно начала обрабатывать большой объем данных, вам может только казаться. Необходима куда более тщательная проверка, которая сможет точно показать, считает ваш 64-битный конь на самом деле или нет.

Чтобы быть уверенным в корректности 64-битной программы, самым минимальным шагом будет использование на всех этапах тестирования не только release, но и debug версии. Учтите, что это является необходимым, но вовсе не достаточным условием. Если в тестах не используются наборы данных, которые, например, не задействуют большой объем оперативной памяти, то ошибка может не проявить себя и в release и в debug-версии [5]. Необходимо расширение юнит-тестов, расширение наборов данных для нагрузочного и ручного тестирования. Необходимо заставить алгоритмы обрабатывать новые сочетания данных, которые доступны только на 64-битных системах [6].

Альтернативный путь диагностики 64-битных ошибок состоит в использовании инструментов статического анализа. Он куда более радикален и надежен, чем гадание о том, достаточно добавлено тестов или нет. Он удобен, так как не требует использования debug-версии для перемалывания гигабайт данных.

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

Из инструментария для поиска 64-битных фантомов я конечно предложу инструмент который мы разрабатываем - Viva64. Кстати, скоро этот инструмент войдет в состав PVS-Studio, которая будет объединять все наши инструменты статического анализа.

Чтобы быть более объективным и меня поменьше выгоняли с сайтов с этой статьей, как рекламной, упомяну некоторые другие инструменты. Следует назвать Gimpel PC-Lint и Parasoft C++test. В них также реализованы правила для проверки 64-битных ошибок, хотя в этом они обладают меньшими диагностическими возможностями, чем узкоспециализированный инструмент Viva64 [7]. Еще существует Abraxas CodeCheck, в новой версии которого (14.5) также реализованы функции диагностики 64-битных ошибок, но более подробными сведениями я не располагаю.

Заключение

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

Библиографический список

  • Роджер Р. Хок. 40 исследований, которые потрясли психологию. 4-е межд. изд. СПб.: Прайм-Еврознак, 2006, ISBN: 5-93878-237-6.
  • Андрей Карпов. 64 бита, /Wp64, Visual Studio 2008, Viva64 и все, все, все... http://www.viva64.com/ru/a/0021/
  • Андрей Карпов, Евгений Рыжков. Статический анализ кода для верификации 64-битных приложений. http://www.viva64.com/ru/a/0007/
  • Андрей Карпов. 7 шагов по переносу программы на 64-битную систему. http://www.viva64.com/ru/a/0042/
  • Андрей Карпов, Евгений Рыжков. 20 ловушек переноса Си++ - кода на 64-битную платформу. http://www.viva64.com/ru/a/0004/
  • Андрей Карпов, Евгений Рыжков. Поиск ловушек в Си/Си++ коде при переносе приложений под 64-битную версию Windows. http://www.viva64.com/ru/a/0012/
  • Андрей Карпов. Сравнение диагностических возможностей анализаторов при проверке 64-битного кода. http://www.viva64.com/ru/a/0024/