SIGSEGV с рекурсивным алгоритмом - PullRequest
Новая
       24

SIGSEGV с рекурсивным алгоритмом

0 голосов
/ 04 октября 2011

Я реализовал рекурсивный алгоритм, который работает около 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-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;
}

Модель похожа на название, она представляет все шаги, которые алгоритм сделал за это время, помещая новый «слой» в свой стек, который является модифицированной (надеюсь, упрощенной) проблемой, созданной из старого, с учетом частичного Решение оценивается по алгоритму. Надеюсь, я сузил это достаточно и понятно.

Ответы [ 2 ]

4 голосов
/ 04 октября 2011

Если у вас 1700 уровней в глубине рекурсии, не исключено, что вы перегрузили свой стек и испортили параметр вызова, который может легко привести к такого рода сбоям.

Если вы используете g ++, попробуйте добавить -fstack-protector-all, чтобы посмотреть, поможет ли вам улучшить диагностику.

РЕДАКТИРОВАТЬ: еще один индикатор, если ваша обратная трассировка внутри GDB становится круговой или никуда не ведет: это сильный индикатор, стек был поврежден.

И в ответ на комментарий не существует надежного способа определить, является ли что-то переполнением стека или «более нормальным» повреждением кучи. Очевидно, что valgrind всегда является надежной опцией для ошибок памяти, если она доступна. Вы можете использовать ulimit в своей оболочке или (я считаю) setrlimit программно для настройки предела стека. Обратите внимание, что существуют жесткие верхние границы и часто лучше изменить свою рекурсию так, чтобы она была менее вредной для стека, чем для увеличения размера стека.

0 голосов
/ 04 октября 2011

Насколько велики параметры, которые вы передаете в стек?На этой глубине вы можете переполниться, если вы проходите около 5 Кбайт для стека 8 Мб.Это довольно много для стековых переменных, но возможно.С другой стороны, вы можете разбить свой стек, записав за конец буфера, хранящегося в стеке (часто строковый буфер).Тот факт, что вы потерпели крах в return, предполагает, что это возможно.

...