带有递归算法的 SIGSEGV

Question

我实现了一个递归算法，该算法运行了大约 1730 次递归，然后因神秘的 SIGSEGV 而崩溃。我尝试了我的 gdb 并得到以下输出：

Program received signal SIGSEGV, Segmentation fault.
0x000000000040b7da in Town::get_cur_capacity (this=0x61efe0) at ./solver/Darstellung.cpp:54
54      return left_over_capacity;
(gdb) print 0x61efe0
$1 = 6418400
(gdb) print *0x61efe0
Cannot access memory at address 0x61efe0
(gdb) print this
$2 = (const Town * const) 0x61efe0
(gdb) 

调试器怎么知道它应该是一个 const Town 指针，但无法访问内存给我转储？我很确定这个方法中没有错误，因为它在崩溃前被使用了几千次，就像程序中的所有其他函数一样。有没有可能这是与操作系统相关的问题？我正在使用 Linux Ubuntu 64 位。

我的简化算法：

bool solveproblem(ptr_to_model) {
        if( way_one(ptr_to_model) )
              return true;

        if(way_two(ptr_to_model) )
              return true;

        if( check_if_solved)
              return true;

        return false;
}

bool way_one(ptr_to_model) {
     for(go_through_current_problem_configuration) {
     if(check_stuff) {
          ptr_to_model->execute_partial_solution(...); //adds another problem configuration to the stack within the model
          if(solveproblem(ptr_to_model))
                  return true;

          ptr_to_model->redo_last_step();
     }
     }
     return false;
}

bool way_two(...) {
   /*basicly the same as way one*/
}

bool check_if_solve(...) {
       if(problem_solved)
              return true;
       else
              return false;
}

该模型与名称相似，它代表了算法通过在其堆栈上推送一个新“层”而在时间上所做的所有步骤，这是一个由旧问题构成的修改（跳跃简化）问题，考虑到评估的部分解决方案算法。希望我把它缩小到足够和可以理解的程度。

Answer 1

如果您的递归深度达到 1700 级，那么您超出堆栈并损坏调用参数这很容易导致此类崩溃，这并不令人难以置信。

如果您使用 g++ -fstack-protector-all，请尝试添加以查看它是否有助于您获得更好的诊断。

编辑：另一个指标是如果您在 gdb 中的回溯变得循环或没有引导到任何地方：这是堆栈已损坏的强烈指标。

并且作为对评论的回应，没有一种万无一失的方法来确定某些东西是堆栈溢出还是“更正常”的堆损坏。显然，如果可用，valgrind 始终是解决内存错误的可靠选项。您可以ulimit在 shell 中或（我相信）以setrlimit编程方式使用来配置堆栈限制。请注意，有严格的上限限制，并且通常最好将递归更改为减少堆栈滥用，而不是增加堆栈大小。