SIGSEGV與遞歸算法

我實現了一個遞歸算法，它運行約1730年遞歸，然後崩潰與神祕的SIGSEGV。我想我的GDB，得到了以下的輸出：SIGSEGV與遞歸算法

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位。

我的簡化算法：

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

該模型是類同的名稱，它代表所有通過推動其堆棧上一個新的「層」，其是經修飾的步驟通過時所作的算法（hopfully簡化）問題，考慮到算法評估的部分解決方案。希望我把它縮小到可以理解的程度。

來源

2011-10-03 Sim

這是一個非常大的遞歸深度！你能給我們簡單的算法代碼嗎？在某些情況下，您可以將遞歸「展開」爲無限循環。 – Blender

這幾乎可以肯定是你的代碼有問題，而不是「操作系統相關的問題」。您可能會耗盡某些資源（例如堆棧空間），或者在代碼中碰到一些特定的案例錯誤。沒有看到代碼是不可能的。 – NPE

我發現通過將assert（）放入您的代碼來驗證不變量，調試深度遞歸算法效果最佳。這樣，當你遇到不希望發生的情況時，強迫它轉儲核心，而不是在很晚以後才能獲得SIGSEGV。在這種情況下，斷言也是可取的，因爲你有1700個遞歸調用，你將很難找到一個不會碰到成千上萬次的好斷點。 – Kevin

如果你在遞歸中的層次深度是1700，那麼你不可能超越你的棧並損壞了一個可能導致這種崩潰的調用參數。

如果您使用g ++，請嘗試添加-fstack-protector-all以查看它是否有助於您獲得更好的診斷。

編輯：另一個指標是如果你的內部gdb的回溯變成循環或不導致任何地方：這是一個強烈的指標，堆棧已經損壞。

並且在迴應評論時，沒有確定的方法來確定是堆棧溢出還是「更正常」的堆損壞。顯然valgrind對於內存錯誤如果可用的話總是一個可靠的選項。您可以在您的shell中使用ulimit，或者（我相信）setrlimit以編程方式配置堆棧限制。請注意，存在硬限制上限，通常最好將遞歸更改爲較少堆棧濫用，而不是增加堆棧大小。

來源

2011-10-03 20:22:03

這是一個很好的方式來調試可能的堆棧粉碎我在我的答案中提到。 –

應該有沒有比通常的SIGSEGV任何其他輸出？有沒有辦法增加堆棧大小？ – Sim

您在棧上傳遞的參數有多大？在這個深度，如果你爲5米長的8米堆棧傳遞，你可能會溢出。這對堆棧變量來說相當大，但可能。或者，您可能會通過寫入超過存儲在堆棧中的緩衝區的末尾（通常是字符串緩衝區）來粉碎堆棧。你在return崩潰的事實表明這是一種可能性。

來源

2011-10-03 20:20:21

我正在使用標準堆棧實現（在我的模型中）並推送一個包含短變量和短變量向量的類。我使用了大約300MB的Ram，直到它崩潰。除了指針之外，沒有其他的變量可以傳遞，如果你確實指的是函數本身。 – Sim

SIGSEGV與遞歸算法

回答

相關問題