Виктория Ханиева

22 Июл 2018

Теги:

#Cpp #GameDev

Система в шоке: интересные ошибки в исходных кодах легендарного System Shock

22 Июл 2018

Автор: Виктория Ханиева

"How can you challenge a perfect immortal machine?"
Логический или побитовый операнд?
Особый цикл
Учтено далеко не всё
Проверка на выход за границу массива + проверка на ненулевой указатель
Как можно больше комментирования
Побитовый сдвиг отрицательного числа
Ловушка копипасты
Break
Приоритет операций и неблагополучный макрос
Переполнение при сдвиге
Заключение

Меня зовут Виктория, и недавно я влилась в команду PVS-Studio в качестве С++ программиста. Один из способов познакомиться с анализатором и его диагностиками - это проверить какой-то проект и подробно разобраться в предупреждениях, которые он выдаёт. А раз я этим занялась, то будет не лишним оформить результаты проверки в виде статьи. Поэтому предлагаю вашему вниманию обзор кода System Shock. Приятного чтения.

"How can you challenge a perfect immortal machine?"

Не так давно был опубликован исходный код легендарной игры System Shock. Того самого киберпанк-шутера, повлиявшего в свое время на дальнейшее развитие всего направления приключенческих боевиков и ставшего предтечей такой игры, как Bioshock, а также вдохновившего многие сюжетные и игровые решения: Metal Gear Solid, Resident Evil и даже Half-Life. Возможно, это было сделано для привлечения внимания к многообещающему ремейку оригинальной первой части, дела у которого похоже идут не лучшим образом. Поэтому, когда передо мной встал выбор, какой проект проверить с помощью PVS-Studio, я не смогла пройти мимо такого титана игровой индустрии.

Конечно же сложно избежать ошибок в столь крупном проекте. Есть достаточное количество примеров, когда даже крайне надежные системы несут в себе различные недостатки. Чего стоит только ошибка, из-за которой $370 000 000 взлетели на воздух.

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

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

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

Логический или побитовый операнд?

Предупреждение PVS-Studio: V560 A part of conditional expression is always true: 0xffff0000. INTERP.C 355

temp = (((ulong) _view_position.gX)>>16);  // get high 16 bits
if (((temp<<scale) && 0xffff0000)!=0) goto Exit; // overflow
temp = (((ulong) _view_position.gY)>>16);  // get high 16 bits
if (((temp<<scale) && 0xffff0000)!=0) goto Exit; // overflow
temp = (((ulong) _view_position.gZ)>>16);  // get high 16 bits
if (((temp<<scale) && 0xffff0000)!=0) goto Exit; // overflow

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

Особый цикл

Предупреждение PVS-Studio: V607 Ownerless expression 'i > 0'. TMAP.C 221

for (i=nverts; i--; i>0)
{
  ....
}

В данном случае ошибка состоит в самом синтаксисе оператора for: перепутано положение 2-го и 3-го подвыражений. И это не единственная ошибка такого рода:

Предупреждение PVS-Studio: V607 Ownerless expression 'i >= 0'. INTERP.C 366

for (i=N_RES_POINTS-1; i--; i>=0)
  ....;

Аналогичные предупреждения:

Предупреждения PVS-Studio:

V607 Ownerless expression 'i > 0'. TMAP.C 532
V607 Ownerless expression 'i > 0'. POLYGON.C 77
V607 Ownerless expression 'i > 0'. POLYGON.C 268

Учтено далеко не всё

Предупреждения PVS-Studio:

V614 Potentially uninitialized pointer 'pc1' used. AI.C 597
V614 Potentially uninitialized pointer 'pc2' used. AI.C 609

typedef enum ObjClass {
  CLASS_GUN,
  CLASS_AMMO,
  CLASS_PHYSICS,
  ....
  CLASS_CRITTER,
  ....
} ObjClass;
errtype do_random_loot(ObjID corpse){
 int *pc1, *pc2;
   if (....)
   {
     switch (objs[corpse].obclass)
     {
       case CLASS_CONTAINER:
       ....
       *pc1 = 0;
       *pc2 = 0;
       break;
       case CLASS_SMALLSTUFF:
       ....
        pc1 = &objSmallstuffs[osid].data1;
        pc2 = &objSmallstuffs[osid].data2;
        break;
      }
      if (*pc1 == 0)
      {
        ....
      }
      if (*pc2 == 0)
      {
        ....
      }
   }
....
}

Переменным pc1 и pc2 не во всех случаях были присвоены значения, так как не все варианты поведения были приняты во внимание. Так, конкретно здесь, objs[corpse].obclass может принимать куда больше значений, чем CLASS_CONTAINER или CLASS_SMALLSTUFF. Если objs[corpse].obclass примет иные значения, то указатели pc1 и pc2 останутся неинициализированными, и их разыменование ниже приведет к неопределенному поведению.

Проверка на выход за границу массива + проверка на ненулевой указатель

Предупреждение PVS-Studio: V781 The value of the 'num_args' variable is checked after it was used. Perhaps there is a mistake in program logic. Check lines: 224, 225. FIX24TST.C 224

#define MAX_ARGS 8
....
bool args_neg[MAX_ARGS];
....
void parse (char *str, bool command)
{
  ....
  args_neg[num_args] = neg = FALSE;
  if (num_args == MAX_ARGS) break;
  ....
}

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

Предупреждение PVS-Studio: V781 The value of the 'model_num' variable is checked after it was used. Perhaps there is a mistake in program logic. Check lines: 567, 569. RENDTOOL.C 567

uchar model_base_nums[MAX_VTEXT_OBJS];....
void load_model_vtexts(char model_num){
  short curr = model_base_nums[model_num];
  ....
  if (model_num >= MAX_VTEXT_OBJS)
    return;
}

Предупреждение PVS-Studio: V595 The 'ch' pointer was utilized before it was verified against nullptr. Check lines: 200, 202. HOTKEY.C 200

  hotkey_link *chain = (hotkey_link*)(ch->keychain.vec);
  if (ch == NULL) return FALSE;

И ещё несколько аналогичных предупреждений, для которых я не буду приводить код:

Предупреждения PVS-Studio:

V595 The 'ch' pointer was utilized before it was verified against nullptr. Check lines: 381, 392. EVENT.C 381
V595 The 'dp' pointer was utilized before it was verified against nullptr. Check lines: 2508, 2522. INVENT.C 2508
V595 The 'mug' pointer was utilized before it was verified against nullptr. Check lines: 702, 704. EMAIL.C 702

Как можно больше комментирования

Предупреждение PVS-Studio: V547 Expression 'len <= 0' is always true. COMPOSE.C 235

len = 0;
//  len = ....;
//  ....
if (len <= 0)
{
  ....
}

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

Предупреждение PVS-Studio: V785 Constant expression in switch statement. BitmapTest.C 198

c = 0;
//if (....) c = evt.message & charCodeMask;
switch (c) {
case 'i':
  ....
  break;
....
case 'O': 
  ....
  break;
default:
  break;
}

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

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

Предупреждение PVS-Studio: V614 Uninitialized variable 'err' used. EVENT.C 953

errtype err;
....
// err = ui_init_cursors();
....
if (err != OK) return err;

Из-за того, что закомментировали код, переменная err будет не инициализирована, и её использование приводит к неопределенному поведению.

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

// I'll give you fish, I'll give you candy, 
// I'll give you, everything I have in my hand

// it's a wonderful world, with a lot of strange men
// who are standing around, and they all wearing towels

// Returns whether or not in the humble opinion of the
// sound system, the sample should be politely obliterated 
// out of existence

// that kid from the wrong side came over my house again,
// decapitated all my dolls
// and if you bore me, you lose your soul to me 
// - "Gepetto", Belly, _Star_

//  And here, ladies and gentlemen, 
// is a celebration of C and C++ and their untamed passion...
//  ==================
TerrainData  terrain_info;
//  Now the actual stuff...
//  =======================

// this is all outrageously horrible, as we dont know what
// we really need to deal with here

// And if you thought the hack for papers was bad,
// wait until you see the one for datas... - X

Это конечно не ошибка, но мне показалась, что читателю будет интересно познакомиться с некоторыми из комментариев :).

Побитовый сдвиг отрицательного числа

Предупреждение PVS-Studio: V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('((rand() % 4000) - 2000)' = [-2000..1999]). STAR.C 407

v.gX = ((rand()%4000) - 2000) << 8;
v.gY = ((rand()%4000) - 2000) << 8;
v.gZ = ((rand()%4000) - 2000) << 8;

Один из примеров неопределенного поведения в побитовых операциях. Здесь, rand()%4000 возвращает значение в промежутке [0...3999]. Далее этот интервал сдвигается на 2000, и мы получаем значение в диапазоне [-2000..1999].

Согласно стандарту С и С++, побитовый сдвиг отрицательного числа приводит к неопределенному поведению.

Аналогичный случай:

Предупреждение PVS-Studio: V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('(axis_x - 1)' = [-1..2147483646]). ALLOC.C 122

short g3_init(short max_points,int user_x_axis,int user_y_axis,int
user_z_axis){
  ....
  long axis_x;
  ....
  if (user_x_axis<0)
  {
    user_x_axis = -user_x_axis;         
  }
  ....
  axis_x = user_x_axis;  
  ....
  axis_x_ofs = ((axis_x-1)<<1) + (axis_x-1);
  ....
}

Значение axis_x в результате преобразований может принимать значения из промежутка [0.. 2147483647]. В случае, если axis_x = 0, (axis_x-1) примет значение -1, что приведет к описанному выше неопределенному поведению.

И идентичные случаи для осей Y и Z:

Предупреждения PVS-Studio:

V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('(axis_y - 1)' = [-1..2147483646]). ALLOC.C 123
V610 Undefined behavior. Check the shift operator '<<'. The left operand is negative ('(axis_z - 1)' = [-1..2147483646]). ALLOC.C 124

Ловушка копипасты

Предупреждение PVS-Studio: V751 Parameter 'Y' is not used inside function body. BTEST.C 67

fix Terrain( fix X, fix Y, int deriv ) {
  if( deriv == 0 )
    return fix_mul(...., (X - ....) );
  if( deriv == 1 )
    return fix_mul(...., (X - ....) );
  if( deriv == 2 ) return 0;
    return 0;
}

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

Break

Предупреждение PVS-Studio: V796 It is possible that 'break' statement is missing in switch statement. OLH.C 142

switch (objs[obj].obclass)
{
  case CLASS_DOOR:
    ....
    break;
  case CLASS_BIGSTUFF:
    ....
    if (....)
    {
      ....
      break;
    }
  case CLASS_SMALLSTUFF:
    ....
    if (....)
    {
      ....
      break;
    }
  // smallstuff falls through to default. 
  default:
    ....
    break;
}

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

Подобное предупреждение:

Предупреждение PVS-Studio:

V796 It is possible that 'break' statement is missing in switch statement. GAMEREND.C 777

Приоритет операций и неблагополучный макрос

Предупреждение PVS-Studio: V634 The priority of the '-' operation is higher than that of the '<<' operation. It's possible that parentheses should be used in the expression. FRCLIP.C 256

#define span_right(y,s) \
  (x_span_lists[((y)<<SPAN_SHIFT)+(s<<1)+SPAN_RIGHT])
void fr_span_parse(void)
{
....
if (....span_right(y,(*cur_span_cnt)-1)....)>frpipe_dist)
  ....
....
}

При работе препроцессора, получится код следующего вида:

x_span_lists[((y)<<SPAN_SHIFT)+((*cur_span_cnt)-1<<1)+SPAN_RIGHT]

Макросы являются отличным способом выстрелить себе в ногу. Приоритет оператора сдвига ниже, чем приоритет оператора вычитания. Поэтому, конкретно в этом случае ошибки нет. Программисту повезло, что оператор сдвига применяется к выражению (*cur_span_cnt)-1, а не к литералу 1.

Однако, если написать ....span_right(y,(*cur_span_cnt) & 1)...., то код будет работать совсем не так, как рассчитывает программист. Поэтому, необходимо заключать все аргументы макросов в скобки. Правильный вариант макроса:

#define span_right(y,s) \
  (x_span_lists[((y)<<SPAN_SHIFT)+((s)<<1)+SPAN_RIGHT])

Переполнение при сдвиге

Предупреждение PVS-Studio: V610 Undefined behavior. Check the shift operator '<<'. The right operand ('i' = [1..64]) is greater than or equal to the length in bits of the promoted left operand. CARDMFD.C 121

ulong bits;
....
for (i = 1; i <= sizeof(ulong)*8; i++)
{
  if (bits & (1 << i))
  {
    ...
  }
}

Это сложная для объяснения ошибка, которую лучше рассматривать отдельно для 32-битных и 64-битных систем.

В 32-битной системе последний шаг цикла вызывает неопределенное поведение, так как сдвиг осуществляется более чем на 31 бит. Пояснение: числовой литерал 1 имеет 32-битный тип int.

В 64-битной системе будет ещё интереснее. Да, проект System Shock никогда не компилировался для 64-битных систем, но давайте все-таки рассмотрим и этот вариант.

Если тип long является 32-битным (модель данных LLP64), то ситуация точно такая же, как в 32-битной программе: возникнет неопределенное поведение. Однако, на практике, такой код может вести себя, как и ожидалось, в силу везения :).

Если же long является 64-битным (LP64), то вероятность, что неопределённое поведение приведёт к верному выполнению задуманного значительно меньше :). Числовой литерал 1 имеет 32-битный тип int. Значит невозможно получить в результате сдвига значение вне диапазона [INT_MIN..INT_MAX]. Конечно, неопределённое поведение - это всё что угодно, но ждать хорошего исхода явно не стоит.

Правильный вариант кода:

for (i = 1; i < sizeof(ulong)*8; i++)
{
  if (bits & (1ul << i))
  {
    ...
  }
}

Здесь литерал 1 заменен на 1ul, а оператор <= заменён на оператор <.

Заключение

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

#Cpp #GameDev