SIGSEGV使用递归算法 [英] SIGSEGV with a recursive algorithm

问题描述

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

I implemented a recursive algorithm which runs for about 1730 recursions and then crashes with a mysterious SIGSEGV. I tried my gdb and got the following output:

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指针，但是不能访问内存给我一个转储？我相当肯定，这种方法中没有错误，因为它在崩溃之前使用了几千次，像程序中的其他所有函数。有没有机会，这是一个操作系统相关的问题？我使用Linux Ubuntu 64位。

How can it be that the debugger does know that it should be a const Town pointer but is not able to access the memory to give me a dump? I am quite sure that there is no error within this method as it is used several thousand times before the crash, like every other function within the Program. Is there any chance that this is a OS related problem? I am using Linux Ubuntu 64-Bit.

我的简化算法：

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;
}

模型与名称很相似，它表示算法通过通过在其堆栈上推送一个新的层，这是一个修改的（希望简化的）问题，从旧的，考虑由算法评估的部分解决方案的时间。

The model is similiar to the name, it represents all steps the algorithm made through the time by pushing a new "layer" on its stack which is a modified (hopfully simplified) problem made out of the old one, considering the partial solution evaluated by the algorithm. Hope i narrowed it down enough and understandable.

推荐答案

如果你是1700级深度递归，这是不可思议的，你overran

If you're 1700 levels deep in recursion it's not unbelievable that you overran your stack and corrupted a call parameter which could easily lead to this sort of crash.

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

If you use g++ try adding -fstack-protector-all to see if it helps you get better diagnostics.

编辑：另一个指标是，如果你的回溯跟踪gdb变成循环或不导致任何地方：这是一个强大的指示器堆栈已损坏。

Another indicator is if your backtrace inside gdb becomes circular or doesn't lead anywhere: This is a strong indicator the stack has become corrupted.

并且响应评论，没有一个肯定的火的方式来确定是否是堆栈溢出或更正常的堆损坏。显然valgrind总是一个内存错误的固体选项，如果它可用。你可以在你的shell或者（我相信） setrlimit 中用编程方式使用 ulimit 来配置堆栈限制。请注意，有硬上限限制，通常最好更改递归以减少堆栈滥用，而不是增加堆栈大小。

And in response to the comment, there isn't a sure-fire way to determine if something is a stack overflow or a "more normal" heap corruption. Obviously valgrind is always a solid option for memory errors if it's available. You can use ulimit in your shell or (I believe) setrlimit programmatically to configure the stack limit. Note that there are hard upper bound limits and that it's often better to change your recursion to be less stack-abusive rather than increasing the stack size.

这篇关于SIGSEGV使用递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！