20 April

A Second Check of Newton Game Dynamics with PVS-Studio

PVS-Studio corporate blogOpen sourceC++Working with 3D-graphicsC

Рисунок 1

Some time ago, somewhere on the Internet, I stumbled upon a physics engine called Newton Game Dynamics. Knowing that engine projects are usually big and complex, I decided to check its code with PVS-Studio for any interesting defects. I was especially enthusiastic about this one because my co-worker Andrey Karpov already checked it in 2014 and a second check would be a good opportunity to demonstrate our analyzer's evolution over the past six years. As of this writing, the latest version of Newton Game Dynamics is dated February 27, 2020, which means it has been actively developing for the past six years too. So, hopefully, this article will be interesting not only to us but to the engine's developers as well – and for them it's a chance to fix some bugs and improve their code.

Analysis report


In 2014, PVS-Studio issued:

  • 48 first-level warnings;
  • 79 second-level warnings;
  • 261 third-level warnings.

In 2020, it issued:

  • 124 first-level warnings;
  • 272 second-level warnings;
  • 787 third-level warnings (some of them are pretty interesting too).


This time, there are many more interesting warnings than in Andrey's article, so let's check them out.

Diagnostic messages


Warning 1

V519 The 'tmp[i][2]' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 468, 469. dgCollisionConvexHull.cpp 469

bool dgCollisionConvexHull::Create (dgInt32 count,....)
{
  ....
  dgStack<dgVector> tmp(3 * count);
  for (dgInt32 i = 0; i < count; i ++) 
  {
    tmp[i][0] = dgFloat32 (buffer[i*3 + 0]);
    tmp[i][1] = dgFloat32 (buffer[i*3 + 1]);
    tmp[i][2] = dgFloat32 (buffer[i*3 + 2]);
    tmp[i][2] = dgFloat32 (0.0f);
  }
  ....
}

An element of the tmp[i][2] array is initialized twice in a row. Defects like that are usually a sign of misused copy-paste. This can be fixed by either removing the second initialization if it's not meant to be there or changing the index number to 3 – it all depends on the value of the count variable. Now, I'd like to show you another V519 warning absent in Andrey's article but recorded in our bug database:

V519 The 'damp' object is assigned values twice successively. Perhaps this is a mistake. physics dgbody.cpp 404

void dgBody::AddBuoyancyForce (....)
{
  ....
  damp = (m_omega % m_omega) * dgFloat32 (10.0f) *
        fluidAngularViscousity; 
  damp = GetMax (GetMin ((m_omega % m_omega) * 
       dgFloat32 (1000.0f) * 
       fluidAngularViscousity, dgFloat32(0.25f)), 
       dgFloat32(2.0f));
  ....
}

Actually, this bug didn't show up in the report. Neither did I find the AddBuoyancyForce function in the dgbody.cpp file. And that's just fine: while the ability to detect new bugs is a sign of our analyzer's evolution, the absence of earlier bugs in recent project versions is a sign of the project's own evolution.

A bit of off-topic speculation

I'm not the one to judge if snippets below contain bugs or if their behavior fails the programmer's expectations, but they do look suspicious.

This snippet triggered two warnings at once:

V621 Consider inspecting the 'for' operator. It's possible that the loop will be executed incorrectly or won't be executed at all. MultiBodyCar.cpp 942

V654 The condition 'i < count' of loop is always false. MultiBodyCar.cpp 942

void MultibodyBodyCar(DemoEntityManager* const scene)
{
  ....
  int count = 10;
  count = 0;
  for (int i = 0; i < count; i++) 
  {
    for (int j = 0; j < count; j++) 
    {
      dMatrix offset(location);
      offset.m_posit += dVector (j * 5.0f + 4.0f, 0.0f, i * 5.0f, 0.0f);
      //manager->CreateSportCar(offset, viperModel.GetData());
      manager->CreateOffRoadCar(offset, monsterTruck.GetData());
    }
  }
  ....
}

This code might be used for debugging purposes – if so, turning off the loop is a normal trick. There were a few more cases like that:

V519 The 'ret' variable is assigned values twice successively. Perhaps this is a mistake.Check lines: 325, 326. dString.cpp 326

void dString::LoadFile (FILE* const file)
{
  ....
  size_t ret = fread(m_string, 1, size, file);
  ret = 0;
  ....
}

V519 The 'ret' variable is assigned values twice successively.Perhaps this is a mistake. Check lines: 1222, 1223. DemoEntityManager.cpp 1223

void DemoEntityManager::DeserializeFile (....)
{
  ....
  size_t ret = fread(buffer, size, 1, (FILE*) serializeHandle);
  ret = 0;
  ....
}

V560 A part of conditional expression is always true: (count < 10). dMathDefines.h 726

bool dCholeskyWithRegularizer(....)
{
  ....
  int count = 0;
  while (!pass && (count < 10))
  {
    ....
  }
  ....
} 

V654 The condition 'ptr != edge' of loop is always false. dgPolyhedra.cpp 1571

void dgPolyhedra::Triangulate (....)
{
  ....
  ptr = edge;
  ....
  while (ptr != edge);
  ....
}

V763 Parameter 'count' is always rewritten in function body before being used. ConvexCast.cpp 31

StupidComplexOfConvexShapes (...., int count)
{
  count = 40;
  //count = 1;
  ....
}

V547 Expression 'axisCount' is always false. MultiBodyCar.cpp 650

void UpdateDriverInput(dVehicle* const vehicle, dFloat timestep) 
{
  ....
  int axisCount = scene->GetJoystickAxis(axis);
  axisCount = 0;
  if (axisCount)
  {
    ....
  }
  ....
}

Many of you might argue that changes like that to publicly available code should be, at the very least, commented. Well, I'm with you on this one. I believe that certain features that are fine for a pet project shouldn't be allowed in a project intended for use by many people. But the choice is still up to the authors.

Warning 2

V769 The 'result' pointer in the 'result + i' expression equals nullptr. The resulting value is senseless and it should not be used. win32_monitor.c 286

GLFWvidmode* _glfwPlatformGetVideoModes(_GLFWmonitor* monitor, int* count)
{
  GLFWvidmode* result = NULL;
  ....
  for (i = 0;  i < *count;  i++)
    {
    if (_glfwCompareVideoModes(result + i, &mode) == 0)
      break;
    }
}

The problem here is that result doesn't change once it's initialized. The resulting pointer is pointless; you can't use it.

Warnings 3, 4, 5

V778 Two similar code fragments were found. Perhaps, this is a typo and 'm_colorChannel' variable should be used instead of 'm_binormalChannel'. dgMeshEffect1.cpp 1887

void dgMeshEffect::EndBuildFace ()
{
  ....
  if (m_attrib.m_binormalChannel.m_count) <=
  {
    attibutes.m_binormalChannel.
      PushBack(m_attrib.m_binormalChannel[m_constructionIndex + i]);
  }
  if (m_attrib.m_binormalChannel.m_count) <= 
  {
    attibutes.m_colorChannel.
      PushBack(m_attrib.m_colorChannel[m_constructionIndex + i]);
  }
}

The second condition seems to be a clone of the first one and was meant to look like this:

if (m_attrib.m_colorChannel.m_count) <= 
{
  attibutes.m_colorChannel.
  PushBack(m_attrib.m_colorChannel[m_constructionIndex + i]);
}

Here's another very similar bug:

V524 It is odd that the body of 'EnabledAxis1' function is fully equivalent to the body of 'EnabledAxis0' function. dCustomDoubleHingeActuator.cpp 88

void dCustomDoubleHingeActuator::EnabledAxis0(bool state)
{
  m_axis0Enable = state;  <=
}
void dCustomDoubleHingeActuator::EnabledAxis1(bool state)
{
  m_axis0Enable = state;  <=
}

This one should be fixed as follows:

void dCustomDoubleHingeActuator::EnabledAxis1(bool state)
{
  m_axis1Enable = state;
}

Another copy-paste error:

V525 The code contains the collection of similar blocks. Check items 'm_x', 'm_y', 'm_y' in lines 73, 74, 75. dWoodFracture.cpp 73

WoodVoronoidEffect(....)
{
  ....
  for (int i = 0; i < count; i ++) 
  {
    dFloat x = dGaussianRandom(size.m_x * 0.1f);
    dFloat y = dGaussianRandom(size.m_y * 0.1f);  <=
    dFloat z = dGaussianRandom(size.m_y * 0.1f);  <=
  ....
  }
  ....
}

I guess the z variable should be initialized as follows:
dFloat z = dGaussianRandom(size.m_z * 0.1f); 

Warnings 6, 7

Like any other big C or C++ project, Newton Game Dynamics failed to steer clear of unsafe pointer handling bugs. These are typically hard to find and debug and they cause programs to crash – that is, they are highly dangerous and unpredictable. Luckily, many of them are easily detected by our analyzer. It doesn't seem to be a very original idea that writing a check for a pointer and moving on with a light heart is way better than wasting time trying to reproduce the bug, tracing the problem spot, and debugging it, does it? Anyway, here are some of the warnings of this type:

V522 There might be dereferencing of a potential null pointer 'face'. dgContactSolver.cpp 351

DG_INLINE dgMinkFace* dgContactSolver::AddFace(dgInt32 v0,dgInt32 v1,
                                               dgInt32 v2)
{
  dgMinkFace* const face = NewFace();
  face->m_mark = 0; 
  ....
}

The implementation of the NewFace function isn't big, so I'll include it in full:

DG_INLINE dgMinkFace* dgContactSolver::NewFace()
{
  dgMinkFace* face = (dgMinkFace*)m_freeFace;
  if (m_freeFace) 
  {
    m_freeFace = m_freeFace->m_next;
  } else 
  {
    face = &m_facePool[m_faceIndex];
    m_faceIndex++;
    if (m_faceIndex >= DG_CONVEX_MINK_MAX_FACES) 
    {
      return NULL;
    }
  }
#ifdef _DEBUG
    memset(face, 0, sizeof (dgMinkFace));
#endif
  return face;
}

In one of its exit points, the NewFace function returns NULL, which will in its turn lead to null pointer dereferencing with undefined behavior as a result.

Here's a similar case of null pointer dereferencing, but more dangerous:

V522 There might be dereferencing of a potential null pointer 'perimeter'. dgPolyhedra.cpp 2541

bool dgPolyhedra::PolygonizeFace(....)
{
  ....
  dgEdge* const perimeter = flatFace.AddHalfEdge
                           (edge1->m_next->m_incidentVertex,
                            edge1->m_incidentVertex);
  perimeter->m_twin = edge1;
  ....
}

Here's the implementation of AddHalfEdge:

dgEdge* dgPolyhedra::AddHalfEdge (dgInt32 v0, dgInt32 v1)
{
  if (v0 != v1) 
  {
    dgPairKey pairKey (v0, v1);
    dgEdge tmpEdge (v0, -1);
    dgTreeNode* node = Insert (tmpEdge, pairKey.GetVal()); 
    return node ? &node->GetInfo() : NULL;
  } else 
  {
    return NULL;
  }
}

This time, NULL is returned at two exit points out of three.

In total, the analyzer issued 48 V522 warnings. They are similar for the most part, so I don't see any point in discussing more here.

Warning 8

V668 There is no sense in testing the 'pBits' pointer against null, as the memory was allocated using the 'new' operator. The exception will be generated in the case of memory allocation error. TargaToOpenGl.cpp 166

char* const pBits = new char [width * height * 4];
if(pBits == NULL) 
{
  fclose(pFile);
  return 0;
}

The value of the pointer returned by the new operator is compared with zero. This usually means that you'll get unexpected behavior if memory allocation fails. When the new operator fails to allocate the required storage, a std::bad_alloc() exception should be thrown, as prescribed by the C++ standard. In this particular case, it means the condition will never execute, which is obviously different from the behavior the programmer counted on. They wanted the program to close the file in the case of memory allocation failure. But the program won't do that and will instead end up with a resource leak.

Warnings 9, 10, 11

V764 Possible incorrect order of arguments passed to 'CreateWheel' function: 'height' and 'radius'. StandardJoints.cpp 791
V764 Possible incorrect order of arguments passed to 'CreateWheel' function: 'height' and 'radius'. StandardJoints.cpp 833
V764 Possible incorrect order of arguments passed to 'CreateWheel' function: 'height' and 'radius'. StandardJoints.cpp 884

These are the calls to the function:

NewtonBody* const wheel = CreateWheel (scene, origin, height, radius);

And this is its declaration:

static NewtonBody* CreateWheel (DemoEntityManager* const scene,
  const dVector& location, dFloat radius, dFloat height)

This diagnostic detects function calls with presumably swapped arguments.

Warnings 12, 13

The analyzer issued warnings on two similar methods of different names:

V621 Consider inspecting the 'for' operator. It's possible that the loop will be executed incorrectly or won't be executed at all. dgCollisionUserMesh.cpp 161

V621 Consider inspecting the 'for' operator. It's possible that the loop will be executed incorrectly or won't be executed at all. dgCollisionUserMesh.cpp 236

void dgCollisionUserMesh::GetCollidingFacesContinue
    (dgPolygonMeshDesc* const data) const
{
  ....
  data->m_faceCount = 0; <=
  data->m_userData = m_userData;
  data->m_separationDistance = dgFloat32(0.0f);
  m_collideCallback(&data->m_p0, NULL);
  dgInt32 faceCount0 = 0;
  dgInt32 faceIndexCount0 = 0;
  dgInt32 faceIndexCount1 = 0;
  dgInt32 stride = data->m_vertexStrideInBytes / sizeof(dgFloat32);
  dgFloat32* const vertex = data->m_vertex;
  dgInt32* const address = data->m_meshData.m_globalFaceIndexStart;
  dgFloat32* const hitDistance = data->m_meshData.m_globalHitDistance;
  const dgInt32* const srcIndices = data->m_faceVertexIndex;
  dgInt32* const dstIndices = data->m_globalFaceVertexIndex;
  dgInt32* const faceIndexCountArray = data->m_faceIndexCount;
  for (dgInt32 i = 0; (i < data->m_faceCount)&&
       (faceIndexCount0 < (DG_MAX_COLLIDING_INDICES - 32));
       i++)
  {
    ....
  }
  ....
}
void dgCollisionUserMesh::GetCollidingFacesDescrete
    (dgPolygonMeshDesc* const data) const
{
  ....
  data->m_faceCount = 0; <=  
  data->m_userData = m_userData;
  data->m_separationDistance = dgFloat32(0.0f);
  m_collideCallback(&data->m_p0, NULL);
  dgInt32 faceCount0 = 0;
  dgInt32 faceIndexCount0 = 0;
  dgInt32 faceIndexCount1 = 0;
  dgInt32 stride = data->m_vertexStrideInBytes / sizeof(dgFloat32);
  dgFloat32* const vertex = data->m_vertex;
  dgInt32* const address = data->m_meshData.m_globalFaceIndexStart;
  dgFloat32* const hitDistance = data->m_meshData.m_globalHitDistance;
  const dgInt32* const srcIndices = data->m_faceVertexIndex;
  dgInt32* const dstIndices = data->m_globalFaceVertexIndex;
  dgInt32* const faceIndexCountArray = data->m_faceIndexCount;
  for (dgInt32 i = 0; (i < data->m_faceCount)&&
       (faceIndexCount0 < (DG_MAX_COLLIDING_INDICES - 32));
       i++)
  {
    ....
  }
  ....
}

The problem spot is the i < data->m_faceCount part of the condition.Since data->m_faceCount is assigned the value 0, this loop won't execute even once. I guess the programmer forgot to reinitialize the m_faceCount field and simply cloned the method's body.

Warnings 14, 15

The analyzer issued two warnings on two similar adjacent lines:

V630 The '_alloca' function is used to allocate memory for an array of objects which are classes containing constructors. dgSkeletonContainer.cpp 1341

V630 The '_alloca' function is used to allocate memory for an array of objects which are classes containing constructors. dgSkeletonContainer.cpp 1342

#define alloca _alloca
....
#define dAlloca(type,size) (type*) alloca ((size) * sizeof (type))
....
dgSpatialMatrix::dgSpatialMatrix();
dgSpatialMatrix::dgSpatialMatrix(dgFloat32 val);
....
dgSpatialMatrix* const bodyMassArray = dgAlloca(dgSpatialMatrix,
                                                m_nodeCount);
dgSpatialMatrix* const jointMassArray = dgAlloca(dgSpatialMatrix,
                                                 m_nodeCount); 

The problem with this code is that the allocated memory block is being handled as if it were an array of objects that have a constructor or destructor. But when memory is allocated the way it's done here, the constructor won't be called. Neither will the destructor be called when freeing the memory. This code is very suspicious. The program may end up handling uninitialized variables and running into other troubles. Another problem with this approach is that, unlike with the malloc/free technique, you won't get an explicit error message if you try to have more memory allocated than the machine could provide. Instead, you'll get a segmentation error when trying to access that memory. A few more messages of this type:

  • V630 The '_alloca' function is used to allocate memory for an array of objects which are classes containing constructors. dVehicleSolver.cpp 498
  • V630 The '_alloca' function is used to allocate memory for an array of objects which are classes containing constructors. dVehicleSolver.cpp 499
  • V630 The '_alloca' function is used to allocate memory for an array of objects which are classes containing constructors. dVehicleSolver.cpp 1144
  • About 10 more warnings like that.

Conclusion


As usual, PVS-Studio didn't let us down and found a few interesting bugs. And that means it's doing great and helps make the world a better place. If you want to try PVS-Studio on your own project, you can get it here.
Tags:cc++static code analysisstatic code analyzerpvs-studioopen sourcenewton game dynamics3d graphics
Hubs: PVS-Studio corporate blog Open source C++ Working with 3D-graphics C
0
320 1
Leave a comment