AlexanderKurenev 25 июн 2021 в 15:14

Йо-хо-хо, и бутылка рому! Разбираем ошибки игрового движка Storm Engine

11 мин

4.4K

Блог компании PVS-StudioC++*Разработка игр*

PVS-Studio – это инструмент статического анализа, позволяющий находить ошибки в исходном коде программ. В качестве знакомства с возможностями анализатора вашему вниманию предлагается результат проверки PVS-Studio исходного кода игрового движка Storm Engine.

Storm Engine

Storm Engine - игровой движок, разрабатывавшийся с января 2000 года компанией Акелла для серии игр Корсары. 26 марта 2021 года исходный код движка открыт под лицензией GPLv3 и доступен на GitHub. Проект написан на C++.

Всего в проекте было обнаружено 235 предупреждений уровня High и 794 предупреждения уровня Medium. Многие из этих предупреждений указывают на ошибки, которые могут привести к неопределенному поведению программы. Другие предупреждения выявляют логические ошибки в коде – программа будет работать стабильно, но результаты этой работы будут отличаться от ожидаемых.

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

Найденные ошибки

Лишние проверки

Предупреждение PVS-Studio: V547 Expression 'nStringCode >= 0xffffff' is always false. dstring_codec.h 84

#define DHASH_SINGLESYM 255
....
uint32_t Convert(const char *pString, ....)
{
  uint32_t nStringCode;
  ....
  nStringCode = ((((unsigned char)pString[0]) << 8) & 0xffffff00) |
                  (DHASH_SINGLESYM)
  ....
  if (nStringCode >= 0xffffff)
  {
    __debugbreak();
  }
  return nStringCode;
}

Проведем оценку выражения, которое будет присвоено переменной nStringCode. Тип unsigned char принимает значения [0, 255], поэтому (unsigned char)pString[0] всегда меньше 2^8, после сдвига на *8 *получаем не более 2^16, конъюнкция не увеличивает это значение. После увеличиваем значение выражения не более чем на 255. Итого значение переменной nStringCode не превышает 2^16+256, что всегда меньше, чем 0xffffff = 2^24-1, и проверка оказалась всегда ложной. Таким образом, проверка на самом деле ни от чего не защищает, и её можно удалить из кода:

#define DHASH_SINGLESYM 255
....
uint32_t Convert(const char *pString, ....)
{
  uint32_t nStringCode;
  ....
  nStringCode = ((((unsigned char)pString[0]) << 8) & 0xffffff00) |
                (DHASH_SINGLESYM)
....
  return nStringCode;
}

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

Предупреждение PVS-Studio: V560 A part of conditional expression is always true: 0x00 <= c. utf8.h 187

inline bool IsValidUtf8(....)
{
  int c, i, ix, n, j;
  for (i = 0, ix = str.length(); i < ix; i++)s
  {
    c = (unsigned char)str[i];
    if (0x00 <= c && c <= 0x7f)
      n = 0;
    ....
  }
  ....
}

Переменной c было присвоено значение беззнакового типа, поэтому проверка 0x00 <= c бессмысленна, и ее можно убрать. Сокращенный код:

inline bool IsValidUtf8(....)
{
  int c, i, ix, n, j;
  for (i = 0, ix = str.length(); i < ix; i++)s
  {
    c = (unsigned char)str[i];
    if (c <= 0x7f)
      n = 0;
    ....
  }
  ....
}

Выход за границу массива

Предупреждение PVS-Studio: V557 Array overrun is possible. The value of 'TempLong2 - TempLong1 + 1' index could reach 520. internal_functions.cpp 1131

DATA *COMPILER::BC_CallIntFunction(....)
{
  if (TempLong2 - TempLong1 >= sizeof(Message_string))
  {
    SetError("internal: buffer too small");
    pV = SStack.Push();
    pV->Set("");
    pVResult = pV;
    return pV;
  }
  memcpy(Message_string, pChar + TempLong1, 
         TempLong2 - TempLong1 + 1);
  Message_string[TempLong2 - TempLong1 + 1] = 0;
  pV = SStack.Push();
}

В этом примере анализатор помогает найти off-by-one error.

Сначала проверяется, что значение TempLong2 - TempLong1 меньше размера строки Message_string, а затем выполняется присваивание по индексу TempLong2 - TempLong1 + 1. В случае, если TempLong2 - TempLong1 + 1 == sizeof(Message_string), проверка будет пройдена, внутренняя ошибка сгенерирована не будет, а при выполнении присваивания произойдет обращение к незарезервированной памяти, что приведет к неопределенному поведению программы. Необходимо поменять проверку:

DATA *COMPILER::BC_CallIntFunction(....)
{
  if (TempLong2 - TempLong1 + 1 >= sizeof(Message_string))
  {
    SetError("internal: buffer too small");
    pV = SStack.Push();
    pV->Set("");
    pVResult = pV;
    return pV;
  }
  memcpy(Message_string, pChar + TempLong1, 
         TempLong2 - TempLong1 + 1);
  Message_string[TempLong2 - TempLong1 + 1] = 0;
  pV = SStack.Push();
}

Присваивание переменной самой себе

Предупреждение PVS-Studio: V570 The 'Data_num' variable is assigned to itself. s_stack.cpp 36

uint32_t Data_num;
....
DATA *S_STACK::Push(....)
{
  if (Data_num > 1000)
  {
    Data_num = Data_num;
  }
  ....
}

Возможно, данный фрагмент кода был добавлен для отладки и впоследствии не был удален. Переменной *Data_num *вместо нового значения присваивается ее собственное значение. Сложно точно сказать, какое значение программист хотел присвоить. Вероятно, здесь должно быть присваивание значения другой переменной с похожим названием, но по невнимательности название было перепутано. Другой вариант – значение переменной хотели ограничить константой 1000, но опечатались. В любом случае это ошибка, и ее нужно исправить.

Разыменование нулевого указателя

Предупреждение PVS-Studio: V595 The 'rs' pointer was utilized before it was verified against nullptr. Check lines: 163, 164. Fader.cpp 163

uint64_t Fader::ProcessMessage(....)
{
  ....
  textureID = rs->TextureCreate(_name);
  if (rs)
  {
    rs->SetProgressImage(_name);
    ....
}

Здесь сначала происходит разыменование указателя rs, а потом этот указатель проверяется на равенство nullptr. Если указатель может быть равен nullptr, то разыменование нулевого указателя приведет к неопределенному поведению, поэтому проверку нужно делать до первого разыменования:

uint64_t Fader::ProcessMessage(....)
{
  ....
  if (rs)
  {
    textureID = rs->TextureCreate(_name);
    rs->SetProgressImage(_name);
    ....
}

Если же гарантируется, что всегда rs != nullptr, то проверка if (rs) лишняя, и ее надо убрать:

uint64_t Fader::ProcessMessage(....)
{
  ....
  textureID = rs->TextureCreate(_name);
  rs->SetProgressImage(_name);
  ....
}

Есть и ещё один вариант. На самом деле, хотели проверить переменную textureID.

Всего в проекте встретилось 14 предупреждений V595.

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

Предупреждение PVS-Studio: V595 The 'pACh' pointer was utilized before it was verified against nullptr. Check lines: 1214, 1215. sail.cpp 1214

void SAIL::SetAllSails(int groupNum)
{
  ....
  SetSailTextures(groupNum, core.Event("GetSailTextureData", 
                 "l", pACh->GetAttributeAsDword("index",  -1)));
  if (pACh != nullptr){
  ....
}

При вычислении аргументов метода *Event *происходит разыменования указателя pACh, который в следующей строке кода проверяется на равенство nullptr. Если указатель может быть нулевым, то вызов функции SetSailTextures, порождающий разыменование pACh, должен выполняться после проверки:

void SAIL::SetAllSails(int groupNum)
{
  ....
  if (pACh != nullptr){
    SetSailTextures(groupNum, core.Event("GetSailTextureData", 
                    "l", pACh->GetAttributeAsDword("index",  -1)));
  ....
}

Если же гарантируется, что pACh – ненулевой, то проверку нужно убрать:

void SAIL::SetAllSails(int groupNum)
{
  ....
  SetSailTextures(groupNum, core.Event("GetSailTextureData", 
                  "l", pACh->GetAttributeAsDword("index",  -1)));
  ....
}

Ошибка new[] – delete

Предупреждение PVS-Studio: V611 The memory was allocated using 'new T[]' operator but was released using the 'delete' operator. Consider inspecting this code. It's probably better to use 'delete [] pVSea;'. Check lines: 169, 191. SEA.cpp 169

struct CVECTOR
{
  public:
    union {
      struct
      {
        float x, y, z;
      };
      float v[3];
  };
};
....
struct SeaVertex
{
  CVECTOR vPos;
  CVECTOR vNormal;
  float tu, tv;
};
....
#define STORM_DELETE (x)
{ delete x; x = 0; }

void SEA::SFLB_CreateBuffers()
{
    ....
    pVSea = new SeaVertex[NUM_VERTEXS];
}
SEA::~SEA() {
....
STORM_DELETE(pVSea);
....
}

Использование макросов – практика, требующая особой внимательности. В данном случае использование макроса привело к ошибке: выделенная оператором new[] память освобождается неправильным оператором delete вместо правильного *delete[]*. Как результат, деструкторы элементов массива *pVSea *вызваны не будут. Иногда это может не проявляться – например, когда все деструкторы элементов массива и их полей тривиальны.

Однако если ошибка не проявляется на runtime – не значит, что ее нет. Дело в том, что реализация оператора new[] может быть устроена так, что в начало участка памяти, выделенного под массив, дополнительно помещается размер этого участка и количество элементов в массиве. Тогда при вызове несовместимого оператора delete информация о размере блока и числе элементов, вероятно, будет интерпретирована неправильно, и результат такой операции не определен. Также не исключена ситуация, когда память для отдельных элементов и массивов выделяется из разных пулов памяти. Тогда попытка вернуть выделенную для массива память в пул, предназначенный для скаляров, приведет к катастрофе.

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

V611 The memory was allocated using 'new T[]' operator but was released using the 'delete' operator. Consider inspecting this code. It's probably better to use 'delete [] m_pShowPlaces;'. Check lines: 421, 196. ActivePerkShower.cpp 421
V611 The memory was allocated using 'new T[]' operator but was released using the 'delete' operator. Consider inspecting this code. It's probably better to use 'delete [] pTable;'. Check lines: 371, 372. AIFlowGraph.h 371
V611 The memory was allocated using 'new T[]' operator but was released using the 'delete' operator. Consider inspecting this code. It's probably better to use 'delete [] vrt;'. Check lines: 33, 27. OctTree.cpp 33
V611 The memory was allocated using 'new T[]' operator but was released using the 'delete' operator. Consider inspecting this code. It's probably better to use 'delete [] flist;'. Flag.cpp 738
V611 The memory was allocated using 'new T[]' operator but was released using the 'delete' operator. Consider inspecting this code. It's probably better to use 'delete [] rlist;'. Rope.cpp 660

Анализ кода показал, что макрос STORM_DELETE используется во многих из найденных случаев. Однако простое изменение оператора delete на оператор delete[] приведет к новым ошибкам, потому что этот макрос используется также и для освобождения памяти, выделенной оператором new. Поэтому исправить код нужно, добавив новый макрос STORM_DELETE_ARRAY, который использует правильный оператор delete[]:

struct CVECTOR
....
struct SeaVertex
{
  CVECTOR vPos;
  CVECTOR vNormal;
  float tu, tv;
};
....
#define STORM_DELETE (x)
{ delete x; x = 0; }

#define STORM_DELETE_ARRAY (x)
{ delete[] x; x = 0; }

void SEA::SFLB_CreateBuffers()
{
    ....
    pVSea = new SeaVertex[NUM_VERTEXS];
}
SEA::~SEA() 
{
  ....
  STORM_DELETE_ARRAY(pVSea);
  ....
}

Присваивание дважды подряд

Предупреждение PVS-Studio: V519 The 'h' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 385, 389. Sharks.cpp 389

inline void Sharks::Shark::IslandCollision(....)
{
  if (h < 1.0f)
  {
    h -= 100.0f / 150.0f;
    if (h > 0.0f)
    {
      h *= 150.0f / 50.0f;
    }
    else
      h = 0.0f;
    h = 0.0f;
    vx -= x * (1.0f - h);
    vz -= z * (1.0f - h);
}

В этом фрагменте кода в случае h < 1.0f сначала производятся вычисления над переменной h, а затем ей присваивается значение 0. Как результат – переменная h всегда равна 0, что является ошибкой, и последнее присваивание переменной h нужно убрать:

inline void Sharks::Shark::IslandCollision(....)
{
  if (h < 1.0f)
  {
    h -= 100.0f / 150.0f;
    if (h > 0.0f)
    {
      h *= 150.0f / 50.0f;
    }
    else
      h = 0.0f;
    vx -= x * (1.0f - h);
    vz -= z * (1.0f - h);
}

Разыменование указателя, полученного из функции realloc или malloc

Предупреждение PVS-Studio: V522 There might be dereferencing of a potential null pointer 'pTable'. Check lines: 36, 35. s_postevents.h 36

void Add(....)
{
  ....
  pTable = (S_EVENTMSG **)realloc(
                         pTable, nClassesNum * sizeof(S_EVENTMSG *));
  pTable[n] = pClass;
  ....
};

Функция realloc в случае, когда недостаточно памяти для расширения блока до заданного размера, возвращает NULL. Если произойдет такая ситуация, то при вычислении выражения *pTable[n] *произойдет разыменование нулевого указателя, что приведет к неопределенному поведению программы. Кроме того, из-за того, что указатель pTable будет перезаписан, адрес исходного блока памяти может быть утерян. Необходимо добавить проверку и использовать дополнительный указатель:

void Add(....)
{
  ....
  S_EVENTMSG ** newpTable 
    = (S_EVENTMSG **)realloc(pTable, 
                             nClassesNum * sizeof(S_EVENTMSG *));
  if(newpTable) 
  {
    pTable = newpTable;
    pTable[n] = pClass;
    ....
  }
  else
  {
  // Обрабатываем ситуацию, когда realloc не смог сделать реаллокацию
  }
};

Встречаются подобные ошибки и в использовании функции malloc:

Предупреждение PVS-Studio: V522 There might be dereferencing of a potential null pointer 'label'. Check lines: 116, 113. geom_static.cpp 116

GEOM::GEOM(....) : srv(_srv)
{
  ....
  label = static_cast<LABEL *>(srv.malloc(sizeof(LABEL) *
                               rhead.nlabels));
  for (long lb = 0; lb < rhead.nlabels; lb++)
  {
    label[lb].flags = lab[lb].flags;
    label[lb].name = &globname[lab[lb].name];
    label[lb].group_name = &globname[lab[lb].group_name];
    memcpy(&label[lb].m[0][0], &lab[lb].m[0][0], 
           sizeof(lab[lb].m));
    memcpy(&label[lb].bones[0], &lab[lb].bones[0],
           sizeof(lab[lb].bones));
    memcpy(&label[lb].weight[0], &lab[lb].weight[0], 
           sizeof(lab[lb].weight));
  }
}

Здесь нужно добавить проверку:

GEOM::GEOM(....) : srv(_srv)
{
  ....
  label = static_cast<LABEL *>(srv.malloc(sizeof(LABEL) *
                               rhead.nlabels));
  for (long lb = 0; lb < rhead.nlabels; lb++)
  {
    if(label)
    {
      label[lb].flags = lab[lb].flags;
      label[lb].name = &globname[lab[lb].name];
      label[lb].group_name = &globname[lab[lb].group_name];
      memcpy(&label[lb].m[0][0], &lab[lb].m[0][0],
               sizeof(lab[lb].m));
      memcpy(&label[lb].bones[0], &lab[lb].bones[0],
             sizeof(lab[lb].bones));
      memcpy(&label[lb].weight[0], &lab[lb].weight[0], 
             sizeof(lab[lb].weight));
    }
  ....
  }
}

Всего анализатор выявил 18 ошибок подобного типа.

О том, к чему могут привести такие ошибки и почему так важно их не допускать, вы можете прочитать в этой статье.

Остаток по модулю 1

Предупреждение PVS-Studio: V1063 The modulo by 1 operation is meaningless. The result will always be zero. WdmSea.cpp 205

void WdmSea::Update(float dltTime)
{
  long whiteHorses[1];
  ....
  wh[i].textureIndex = rand() % (sizeof(whiteHorses) / sizeof(long));
}

В данном случае вычисляется размер массива *whiteHorses, *равный 1, и по нему берется модуль, что бессмысленно – результатом всегда будет 0. Возможно, ошибка в объявлении переменной *whiteHorses *– размер массива должен быть изменен. Не исключаю, что в этом коде и вовсе нет ошибки, и бессмысленная на данный момент конструкция *rand() % (sizeof(whiteHorses) / sizeof(long)) *сохранена осознанно с оглядкой на будущие изменения. Если ожидается, что размер массива whiteHorses в будущем будет изменен и надо будет генерировать случайный индекс в нем, то этот код имеет право на жизнь и в правках не нуждается. Независимо от того, прав ли программист в этом фрагменте кода или ошибся, на него стоит обратить внимание и перепроверить, о чем справедливо сообщает анализатор.

std::vector vs std::deque

Кроме явных ошибок и неточностей в коде, анализатор PVS-Studio помогает оптимизировать написанный код.

Предупреждение PVS-Studio: V826 Consider replacing the 'aLightsSort' std::vector with std::deque. Overall efficiency of operations will increase. Lights.cpp 471

void Lights::SetCharacterLights(....)
{
  std::vector<long> aLightsSort;
  for (i = 0; i < numLights; i++)
    aLightsSort.push_back(i);
  for (i = 0; i < aMovingLight.size(); i++)
  {
    const auto it = std::find(aLightsSort.begin(),aLightsSort.end(), 
                              aMovingLight[i].light);
    aLightsSort.insert(aLightsSort.begin(), aMovingLight[i].light);
  }
}

Здесь создается *std::vector aLightsSort, *в начало которого потом вставляются элементы.

Почему плохо вставлять много раз в начало std::vector? Потому что каждая, абсолютно каждая такая вставка приводит к релокации (reallocation) буфера вектора. Будет выделен новый буфер, в начало него будет записано вставляемое значение и скопированы значения из старого буфера. А почему бы нам просто не записать новое значение перед нулевым элементом старого буфера? А потому что std::vector так не умеет.

Зато так умеет std::deque. Буфер этого контейнера реализован в виде кольцевого буфера, что позволяет вставлять и удалять элементы и в начало, и в конец без копирования. Вставка в начало std::deque выглядит ровно так, как мы и хотим – просто вставить новое значение перед нулевым элементом.

Поэтому в данном фрагменте кода стоит заменить *std::vector *на std::deque:

void Lights::SetCharacterLights(....)
{
  std::deque<long> aLightsSort;
  for (i = 0; i < numLights; i++)
    aLightsSort.push_back(i);
  for (i = 0; i < aMovingLight.size(); i++)
  {
    const auto it = std::find(aLightsSort.begin(),aLightsSort.end(), 
                              aMovingLight[i].light);
    aLightsSort.push_front(aMovingLight[i].light);
  }
}

Заключение

PVS-Studio выявил множество ошибок и недочетов в исходном коде Storm Engine. Многие предупреждения указывали на код, помеченный самими разработчиками как требующий доработки – возможно, эти ошибки были найдены как раз инструментами статического анализа, а может быть, их обнаружили на обзоре кода (code review). Другие предупреждения указывали на непомеченный комментариями код (а значит и не были найдены программистами) – в частности все, разобранные в статье, – и указывали на ошибки, требующие исправлений. Если вас заинтересовал проект Storm Engine и найденные в нем ошибки, вы можете повторить проведенный мною анализ самостоятельно. Также предлагаю познакомиться с подборкой статей про проверку исходных проектов – в ней вы найдете результаты анализа других проектов.

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Yo, Ho, Ho, And a Bottle of Rum - Or How We Analyzed Storm Engine's Bugs.

Теги:

Хабы: