Valgrind says malloc memory corruption, haven't used malloc

Question

I've got a fairly large program with a small memory issue. The code runs as it should, and I get the results I want, but I'd like to get rid of the corruption. I ran valgrind, but I don't really understand the error.

Here's what it says:

==11295== 
==11295== HEAP SUMMARY:
==11295==     in use at exit: 72,704 bytes in 2 blocks
==11295==   total heap usage: 19,836 allocs, 19,834 frees, 1,247,711 bytes allocated
==11295== 
==11295== 0 bytes in 1 blocks are definitely lost in loss record 1 of 2
==11295==    at 0x4C2E80F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11295==    by 0x40197C: grid::setSize(int, int) (grid.cpp:75)
==11295==    by 0x40B9AC: node::node() (node.cpp:17)
==11295==    by 0x4032AF: main (main.cpp:15)
==11295== 
==11295== 72,704 bytes in 1 blocks are still reachable in loss record 2 of 2
==11295==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11295==    by 0x4EC3EFF: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21)
==11295==    by 0x40104E9: call_init.part.0 (dl-init.c:72)
==11295==    by 0x40105FA: call_init (dl-init.c:30)
==11295==    by 0x40105FA: _dl_init (dl-init.c:120)
==11295==    by 0x4000CF9: ??? (in /lib/x86_64-linux-gnu/ld-2.23.so)
==11295== 
==11295== LEAK SUMMARY:
==11295==    definitely lost: 0 bytes in 1 blocks
==11295==    indirectly lost: 0 bytes in 0 blocks
==11295==      possibly lost: 0 bytes in 0 blocks
==11295==    still reachable: 72,704 bytes in 1 blocks
==11295==         suppressed: 0 bytes in 0 blocks
==11295== 
==11295== For counts of detected and suppressed errors, rerun with: -v
==11295== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 1 from 1)

The only pointers I know that I create are in the grid.setSize() function, but those should all be taken care of by the destructor. Besides, the first valgrind block says there are 0 bytes lost.

What I'm confused about is the second block. I haven't used malloc anywhere, and I don't really know what the block needs from me.

Any help is appreciated!

As requested, here's some of the code.

grid.cpp

#include <iostream>
#include <cstdlib>
#include <cstddef>
#include "grid.h"
using namespace std;

// initializes the double pointer
grid::grid()
{
  m_grid = NULL;
}

// destroys the 2D game array
grid::~grid()
{
  for (int i = 0; i < m_width; i++)
  {
    delete[] m_grid[i];
  }

  delete[] m_grid;
}

cell** grid::getGrid()
{
  return m_grid;
}

// returns width
int grid::getWidth()
{
  return m_width;
}

// returns height
int grid::getHeight()
{
  return m_height;
}

// returns radiation level of specified cell
int grid::getCellRad(const int x, const int y) const
{
  return m_grid[x][y].m_rad;
}

int grid::getXRad() const
{
  return m_x_rad;
}

int grid::getYRad() const
{
  return m_y_rad;
}

// clears grid pointer
void grid::setGridNull()
{
  m_grid = NULL;
}

// creates a grid of size width * height and makes all cells unoccupied
void grid::setSize(const int grid_width, const int grid_height)
{
  m_width = grid_width;
  m_height = grid_height;
  m_grid = new cell* [m_width];

  // from left to right
  for (int i = 0; i < m_width; i++)
  {
    m_grid[i] = new cell [m_height];

    // from top to bottom
    for (int j = 0; j < m_height; j++)
    {
      m_grid[i][j].m_occupied = 0;
    }
  }
}

// calculates radiation value for all cells in the grid
void grid::setRadiation(const int x_coord, const int y_coord,
  const int rad_mag, const int decay_factor)
{
  m_x_rad = x_coord;
  m_y_rad = y_coord;

  // from left to right
  for (int i = 0; i < m_width; i++)
  {
    // from top to bottom
    for (int j = 0; j < m_height; j++)
    {
      // radiation (equals) max radiation (minus)
      // Manhattan distance between source and current (times) decay factor
      m_grid[i][j].m_rad = rad_mag -
        (abs(m_x_rad - i) + abs(m_y_rad - j)) * decay_factor;

      // minimum radiation
      if (m_grid[i][j].m_rad < 1)
        m_grid[i][j].m_rad = 1;
    }
  }

  return;
}

// makes a specified cell unavailable
void grid::setOccupied(const int x, const int y)
{
  m_grid[x][y].m_occupied = 1;
  return;
}

// makes a specified cell available
void grid::setUnoccupied(const int x, const int y)
{
  m_grid[x][y].m_occupied = 0;
  return;
}

grid& grid::operator=(const grid& g)
{
  m_x_rad = g.m_x_rad;
  m_y_rad = g.m_y_rad;
  m_width = g.m_width;
  m_height = g.m_height;
  m_grid = new cell* [m_width];

  // from left to right
  for (int i = 0; i < m_width; i++)
  {
    m_grid[i] = new cell [m_height];

    // from top to bottom
    for (int j = 0; j < m_height; j++)
    {
      m_grid[i][j].m_occupied = g.m_grid[i][j].m_occupied;
      m_grid[i][j].m_rad = g.m_grid[i][j].m_rad;
    }
  }

  return *this;
}

// checks whether specified cell is available
bool grid::isAvailable(const int x, const int y) const
{
  return !(m_grid[x][y].m_occupied);
}

// displays a map of available/unavailable cells
void grid::printOccupied() const
{
  cout << "--------------------Occupied\n";

  // from top to bottom
  for (int i = 0; i < m_height; i++)
  {
    // from left to right
    for (int j = 0; j < m_width; j++)
    {
      cout << (m_grid[j][i].m_occupied ? "1" : "0") << "  ";
    }
    cout << "\n";
  }
}

// displays a map of every cell's radiation level
void grid::printRadiation() const
{
  cout << "--------------------Radiation\n";

  // from top to bottom
  for (int i = 0; i < m_height; i++)
  {
    // from left to right
    for (int j = 0; j < m_width; j++)
    {
      cout << m_grid[j][i].m_rad
        << (m_grid[j][i].m_rad >= DOUBLE_DIGIT ? " " : "  ");
    }
    cout << "\n";
  }
}

main.cpp

#include "main.h"
using namespace std;

int main()
{
    clock_t start = clock();
    double duration;
    queue<node> frontier;
    node root; // node that grabs initial puzzle state
    unordered_map<int, basic_node> node_map;

    int grid_width, grid_height, x_coord, y_coord, rad_mag, decay_factor,
      num_alligators, num_turtles, num_trees;
    string orientation;

    root.setNumItems(VECTOR_SHIFT + num_alligators + num_turtles + num_trees);

    if (!getInitialPuzzle(root.getGrid(), root.getItems(),
        grid_width, grid_height, rad_mag, decay_factor,
        num_alligators, num_turtles, num_trees,
        x_coord, y_coord, orientation))
    {
        return -1;
    }

    frontier.push(node(root));
    breadthFirstTreeSearch(frontier, node_map, num_alligators, num_trees);

    // put the root in the hash table
    basic_node r;
    r.node_id = frontier.back().getID();
    r.node_parent = -1;
    r.node_cost = frontier.back().getItems()[1]. // only the boat has a cost
        calcItemCost(frontier.back().getGrid());
    // no action taken to get here
    r.node_action_item = '\0';
    r.node_action_number = 0;
    r.node_action_move = '\0';

    node_map.insert({r.node_id, r});

    int j = 0;
    while (!frontier.empty())
    {
        ++j;

        if (frontier.front().isGoal())
            break;

        // only need to check boat, alligators, and turtles
        for (int i = 1; i < frontier.front().getItems().size() - num_trees; i++)
        {
            // only the boat can rotate
            if (i == 1)
            {
                // if the boat can rotate ccw in its own grid
                if (frontier.front().getItems()[i].
                    canRotateCCW(frontier.front().getGrid()))
                {
                    // enqueue a copy of the current node and rotate that boat ccw
                    frontier.push(frontier.front());
                    frontier.back().getItems()[i].rotateCCW(frontier.back().getGrid());

                    basic_node b;
                    b.node_id = frontier.back().getID();
                    b.node_parent = frontier.back().getParent();
                    b.node_cost = frontier.back().getItems()[1].
                        calcItemCost(frontier.back().getGrid());
                    b.node_action_item = frontier.back().getItems()[1].getType();
                    b.node_action_number = 0; // there's only one boat
                    b.node_action_move = 'N'; // counterclockwise

                    node_map.insert({b.node_id, b});
                }

                // if the boat can rotate cw in its own grid
                if (frontier.front().getItems()[i].
                    canRotateCW(frontier.front().getGrid()))
                {
                    // enqueue a copy of the current node and rotate that boat cw
                    frontier.push(frontier.front());
                    frontier.back().getItems()[i].rotateCW(frontier.back().getGrid());

                    basic_node b;
                    b.node_id = frontier.back().getID();
                    b.node_parent = frontier.back().getParent();
                    b.node_cost = frontier.back().getItems()[1].
                        calcItemCost(frontier.back().getGrid());
                    b.node_action_item = frontier.back().getItems()[1].getType();
                    b.node_action_number = 0; // there's only one boat
                    b.node_action_move = 'C'; // clockwise

                    node_map.insert({b.node_id, b});
                }
            }

            // if the boat, alligator, or turtle can move forward
            if (frontier.front().getItems()[i].
                canMoveForward(frontier.front().getGrid()))
            {
                // enqueue a copy of the current node and move the item forward
                frontier.push(frontier.front());
                frontier.back().getItems()[i].moveForward(frontier.back().getGrid());

                basic_node b;
                b.node_id = frontier.back().getID();
                b.node_parent = frontier.back().getParent();
                b.node_cost = frontier.back().getItems()[1].
                    calcItemCost(frontier.back().getGrid());

                // gets B, A, or T for the item that moves
                b.node_action_item = frontier.back().getItems()[i].getType();
                // need to shift for boat and goal, and alligator if necessary
                b.node_action_number = i -
                    (b.node_action_item == 'B' ? 1 : VECTOR_SHIFT) - // shift 1 if boat
                    (b.node_action_item == 'A' ? 0 : num_alligators);
                // this will get the movement; one of {U, D, L, R}
                b.node_action_move = (frontier.back().getItems()[i].getOrientation());

                node_map.insert({b.node_id, b});
            }

            // if the alligator or turtle can move backward
            if (frontier.front().getItems()[i].
                canMoveBackward(frontier.front().getGrid()))
            {
                // enqueue a copy of the current node and move the item forward
                frontier.push(frontier.front());
                frontier.back().getItems()[i].moveBackward(frontier.back().getGrid());

                basic_node b;
                b.node_id = frontier.back().getID();
                b.node_parent = frontier.back().getParent();
                b.node_cost = frontier.back().getItems()[1].
                    calcItemCost(frontier.back().getGrid());

                // gets A or T for the item that moves
                b.node_action_item = frontier.back().getItems()[i].getType();
                // need to shift for boat and goal, and alligator if necessary
                b.node_action_number = i - VECTOR_SHIFT -
                    (b.node_action_item == 'A' ? 0 : num_alligators);
                // this will get the movement; one of {U, D, L, R}
                b.node_action_move = (frontier.back().getItems()[i].getOrientation());

                // this will get the movement; one of {U, D, L, R}
                switch (frontier.back().getItems()[i].getOrientation())
                {
                    case 'L':
                        b.node_action_move = 'R';
                        break;
                    case 'R':
                        b.node_action_move = 'L';
                        break;
                    case 'U':
                        b.node_action_move = 'D';
                        break;
                    case 'D':
                        b.node_action_move = 'U';
                        break;
                }

                node_map.insert({b.node_id, b});
            }
        }

        // all possible moves completed for the current state of the board
        frontier.pop();
    }

    root.getGrid().printOccupied();
    cout << endl;
    frontier.front().getGrid().printRadiation();

    duration = double(clock() - start) / CLOCKS_PER_MS;
    writeSolutions(duration, frontier.front(), node_map, rad_mag, decay_factor,
        num_alligators, num_turtles, num_trees);

    return 0;
}

and node.cpp

#include <cstddef>
#include <iostream>
#include "node.h"

int node::class_id = 0;
int node::num_items = 0;

node::node()
{
  m_grid.setGridNull();
  m_grid.setSize(0, 0);
  m_grid.setRadiation(0, 0, 0, 0);
  m_id = 0;
  m_parent = 0;
}

node::node(const node& n)
{
  m_grid = n.m_grid;
  m_items = n.m_items;
  m_id = ++class_id;
  m_parent = n.m_id;

  /*for (int i = 0; i < n.getNumItems(); i++)
  {
    m_items[i] = n.m_items[i];
  }*/
}

int node::getNumItems() const
{
  return num_items;
}

grid& node::getGrid()
{
  return m_grid;
}

vector<item>& node::getItems()
{
  return m_items;
}

int node::getID() const
{
  return m_id;
}

int node::getParent() const
{
  return m_parent;
}

void node::setNumItems(const int n)
{
  num_items = n;
  return;
}

void node::setID(const int i)
{
  m_id = i;
  return;
}

void node::setParent(const int p)
{
  m_parent = p;
  return;
}

node& node::operator=(node& n)
{
  m_grid = n.m_grid;
  m_parent = n.m_parent;
  m_id = ++class_id;

  for (int i = 0; i < n.getItems().size(); i++)
  {
    cout << "yo\n";
    m_items[i] = n.m_items[i];
    cout << "hey\n";
  }

  return *this;
}

// this will compare the boat and goal locations to determine goal node
bool node::isGoal() const
{
  bool found = false;

  // if we don't have 2+, we don't have a goal and a boat
  if (m_items.size() >= 2)
  {
    // item 1 is the boat
    // back of the boat is in the goal
    if ((m_items[1].getXCoord() == m_items[0].getXCoord()) &&
      m_items[1].getYCoord() == m_items[0].getYCoord())
    {
      found = true;
    }

    else
    {
      switch (m_items[1].getOrientation())
      {
        case 'R':
          if ((m_items[1].getXCoord() == m_items[0].getXCoord() - 1) &&
            m_items[1].getYCoord() == m_items[0].getYCoord())
          {
            found = true;
          }
          break;

        case 'U':
          if ((m_items[1].getXCoord() == m_items[0].getXCoord()) &&
            m_items[1].getYCoord() == m_items[0].getYCoord() + 1)
          {
            found = true;
          }
          break;

        case 'L':
          if ((m_items[1].getXCoord() == m_items[0].getXCoord() + 1) &&
            m_items[1].getYCoord() == m_items[0].getYCoord())
          {
            found = true;
          }
          break;

        case 'D':
          if ((m_items[1].getXCoord() == m_items[0].getXCoord()) &&
            m_items[1].getYCoord() == m_items[0].getYCoord() - 1)
          {
            found = true;
          }
          break;
      }
    }
  }

  return found;
}

Answer 1

The clue is the _dl_init in the stack frame. This is the shared library's initialization function. Any time a shared library is loaded, its initialization function runs. The memory block in question was allocated in the shared library's initialization function.

It is common for shared libraries to allocate memory for its internal data structures, in their initialization functions. This is the C++ runtime library, which is expected to remain loaded for the lifetime of the process. As such, this is not truly a memory leak, especially since the "possibly lost" designation indicates that valgrind managed to find a pointer to the memory block, somewhere.

However, you do have a memory leak in your own code. "definitely lost" means what it means: definitely lost. Your class leaked memory, and valgrind didn't find any dangling pointer to it, otherwise it would fall into the "possibly lost" category.