кто нибудь может мне объяснить как работает backtrace?

На сколько я понимаю, это возвращение по стеку Стек состоит из фреймов, которые образуют связанный список. Поэтому по нему можно ходить взад и вперед

Если в GDB, то там используется отладочная символьная (и не только) информация, которая из сырцов включается в бинарник - а насчет хождения туда/сюда тебе правильно сказали - зная инфу, указатель стека до/после входа в функцию, можно уже и смотреть, что где и как - ручками муторно, gdb делает все за тебя - не зря его столько писали...

backtrace работает только когда приложение собрано с frame pointers.
без них оно может только эвристически работать (как стандартный backtrace при oops в ядре).

в glibc есть функция, которая раскручивает стек на backtrace.
исходник на полэкрана.