I'm implementing an A* pathfinding algorithm in C++ to solve a maze, but I'm encountering a segmentation fault (SIGSEGV) when the maze size is high (~10,000x10,000 or larger).
The error occurs in the
~__shared_count()function inshared_ptr_base.hafternode = queue.top()is called in line 58 and dozens of~Node()deconstructors are called after that.
Edit: The error actually occurs in the _Sp_counted_base<_S_atomic>::_M_release() function now, though I don't know what I changed.
Here are the parts of my code that should be relevant. I'm new to using shared pointers so I'm not really sure what the problem is or how to fix it.
main.cpp
#include <iostream>
#include <queue>
#include <random>
#include <vector>
#include <algorithm>
#include <stack>
#include <fstream>
#include "Node.hpp"
constexpr uint16_t maze_size = 10000;
void solve(const uint16_t start_x, const uint16_t start_y, const uint16_t goal_x,
const uint16_t goal_y,
const std::vector<std::vector<std::pair<bool, bool> > > &walls) {
std::vector<std::vector<bool> > visited(maze_size, std::vector<bool>(maze_size, false));
// Min heap for our queue
std::priority_queue<Node, std::vector<Node>, std::greater<> > queue;
Node node(start_x, start_y, goal_x, goal_y);
visited[node.x][node.y] = true;
while (!node.solved(goal_x, goal_y)) {
// Add all valid neighbors to the queue
{
const auto x = node.x;
const auto y = node.y;
const auto ptr = std::make_shared<Node>(node);
// Right
if (x < maze_size - 1 && !walls[x][y].first && !visited[x + 1][y]) {
queue.emplace(x + 1, y, goal_x, goal_y, ptr);
visited[x + 1][y] = true;
}
// Left
if (x > 0 && !walls[x - 1][y].first && !visited[x - 1][y]) {
queue.emplace(x - 1, y, goal_x, goal_y, ptr);
visited[x - 1][y] = true;
}
// Down
if (y < maze_size - 1 && !walls[x][y].second && !visited[x][y + 1]) {
queue.emplace(x, y + 1, goal_x, goal_y, ptr);
visited[x][y + 1] = true;
}
// Up
if (y > 0 && !walls[x][y - 1].second && !visited[x][y - 1]) {
queue.emplace(x, y - 1, goal_x, goal_y, ptr);
visited[x][y - 1] = true;
}
}
node = queue.top();
queue.pop();
}
}
Node.hpp
#ifndef NODE_HPP
#define NODE_HPP
#include <cstdint>
#include <memory>
class Node {
public:
uint16_t x, y;
uint32_t steps;
uint32_t value;
std::shared_ptr<Node> parent;
Node(const uint16_t x, const uint16_t y, const uint16_t goal_x, const uint16_t goal_y,
const std::shared_ptr<Node> &parent = nullptr) : x(x), y(y), parent(parent) {
steps = parent ? parent->steps + 1 : 0;
value = abs(static_cast<int32_t>(goal_x) - static_cast<int32_t>(x)) +
abs(static_cast<int32_t>(goal_y) - static_cast<int32_t>(y)) +
steps;
}
[[nodiscard]] bool solved(const uint16_t goal_x, const uint16_t goal_y) const {
return x == goal_x && y == goal_y;
}
// Overload the > operator for the priority queue
bool operator>(const Node &rhs) const {
if (value == rhs.value) {
return steps < rhs.steps;
}
return value > rhs.value;
}
};
#endif
Valgrind output
valgrind --leak-check=full ./Tests
==5385== Memcheck, a memory error detector
==5385== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==5385== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==5385== Command: ./Tests
==5385==
Maze loaded10000
==5385== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5385==
==5385== Process terminating with default action of signal 11 (SIGSEGV)
==5385== Access not within mapped region at address 0x1FFE801FF8
==5385== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5385== at 0x116230: std::_Sp_counted_ptr_inplace<Node, std::allocator<void>, (__gnu_cxx::_Lock_policy)2>::_M_dispose() (shared_ptr_base.h:613)
==5385== If you believe this happened as a result of a stack
==5385== overflow in your program's main thread (unlikely but
==5385== possible), you can try to increase the size of the
==5385== main thread stack using the --main-stacksize= flag.
==5385== The main thread stack size used in this run was 8388608.
==5385==
==5385== HEAP SUMMARY:
==5385== in use at exit: 239,026,864 bytes in 556,422 blocks
==5385== total heap usage: 3,380,473 allocs, 2,824,051 frees, 374,594,816 bytes allocated
==5385==
==5385== LEAK SUMMARY:
==5385== definitely lost: 0 bytes in 0 blocks
==5385== indirectly lost: 0 bytes in 0 blocks
==5385== possibly lost: 0 bytes in 0 blocks
==5385== still reachable: 239,026,864 bytes in 556,422 blocks
==5385== suppressed: 0 bytes in 0 blocks
==5385== Reachable blocks (those to which a pointer was found) are not shown.
==5385== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==5385==
==5385== For lists of detected and suppressed errors, rerun with: -s
==5385== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)
You could try to reproduce the error using the following function to load this maze file. Sorry about the size. You can load it using this function:
std::vector<std::vector<std::pair<bool, bool> > > readVectorFromFile(const std::string &filename) {
std::vector<std::vector<std::pair<bool, bool> > > vec;
std::ifstream inFile(filename, std::ios::binary);
if (!inFile) {
std::cerr << "Error opening file for reading: " << filename << std::endl;
return vec;
}
// Read the size of the outer vector
size_t outerSize;
inFile.read(reinterpret_cast<char *>(&outerSize), sizeof(outerSize));
vec.resize(outerSize);
for (auto &innerVec: vec) {
// Read the size of each inner vector
size_t innerSize;
inFile.read(reinterpret_cast<char *>(&innerSize), sizeof(innerSize));
innerVec.resize(innerSize);
// Read each pair in the inner vector
for (auto &pair: innerVec) {
inFile.read(reinterpret_cast<char *>(&pair.first), sizeof(bool));
inFile.read(reinterpret_cast<char *>(&pair.second), sizeof(bool));
}
}
inFile.close();
return vec;
}
The main would look something like:
int main() {
auto walls = readVectorFromFile("maze.dat");
std::cout << "Maze loaded" << std::endl;
solve(0, 0, maze_size - 1, maze_size - 1, walls);
return 0;
}
You didn't explicitly define Node::~Node() but the compiler did that for you. In there, it calls std::shared_ptr<Node>::~shared_ptr. In turn, that calls Node::~Node.
This is a recursive call. Depending on your maze and query, this can overflow the call stack.
The easier solution is to let solve() manage the ownership of all the Nodes; each Node can just have a non-owning Node* parent. This ownership can be as easy as a std::deque<Node> (but not a std::vector<Node>, because that reallocates and breaks the Node* parent)
[edit]
Using smart pointers in node objects isn't necessarily a bad idea. In wide trees, where each parent had 10 children, you're going to run into memory problems around 9 levels deep (one billion nodes), but the stack can easily handle that level of nesting. Even a balanced binary tree with a billion nodes is not too bad (depth 32). In these tree cases, each node is the sole owner of a few children. That can be implemented with a std::vector<std::unique_ptr>> children.