Let’s walk through a backtrace for a “Hello, world!” program, specifically simpler case with enabled frame pointers. Frame pointer is effectively an optional pointer, pointing to a portion of the stack dedicated to currently executing function. For ARM architecture, it occupies register r11.

int f1(int i) {
	return f2(i);
}

int main(void)
{
	return f1(3);
}

To enforce usage of frame pointers, -fno-omit-frame-pointer should be used:

gcc backtrace.c -fno-omit-frame-pointer -o backtrace

Omitting frame pointer is a performance optimization that makes r11 available for other uses.

Now to the backtrace itself: the idea is that with frame pointers enabled, there’s effectively a stack-based linked list of two-member structures, consisting of previous frame pointer and link register (pointer to caller).

Let’s stop at main, before calling f1:

0x1045c <<main+8>>                mov    r0, #3
0x10460 <<main+12>>               bl     0x1042c <<f1>>

(gdb) i r r11 lr
r11            0x7efff5dc
lr             0x76e8f678

Now let’s make a few more steps and stop exactly after prologue of f1:

0x1042c <<f1>>                    push   {r11, lr}
0x10430 <<f1+4>>                  add    r11, sp, #4
0x10434 <<f1+8>>                  sub    sp, sp, #8 

Two instructions in bold effectively add a node to the linked list. So that at any instruction inside f1, we could check the previous node link by looking at r11:

r11            0x7efff5d4

.. and examining a node that it points to:

(gdb) x/2x 0x7efff5d0
0x7efff5d0:     0x7efff5dc      0x00010464

(not sure why it points to the second member of the struct, that is where 4 bytes offset comes from, probably some ARM peculiarity)

Note that 0x7efff5dc is a previous value of FP during main, and 0x00010464 is an instruction inside main (can be seen by looking at main instruction addresses above). With this method, entire callstack can be recursively determined.

Determining backtrace without frame pointers is more complicated and generally less reliable. See this yosefk post for details.