// This log shows how a simple recursive function operates in C. // This may seem way too simple, but back in the day it was a major invention. // Treating the function's local variables as addressed via offsets off // of a register ("stack pointer"), the code of the functions could be // entered again and again, each time with a different set of values for // the variables (a.k.a be executed in a different context). % cat fact5.c #include /* a very naive recursive factorial */ unsigned int fact(unsigned int n) { // printf("%p %d\n", &n, n); if( n == 0 ) return 1; return n * fact(n-1); } int main() { printf("%d\n", fact(7)); return 0; } % gcc -Wall -S fact5.c % gcc -Wall -o fact5 fact5.s % lldb fact5 (lldb) target create "fact5" Current executable set to '/Users/user/cs59/c-and-asm/fact5' (arm64). // Let's set a breakpoint on fact(): (lldb) b fact Breakpoint 1: where = fact5`fact, address = 0x0000000100003ee4 (lldb) b main Breakpoint 2: where = fact5`main, address = 0x0000000100003f38 (lldb) r Process 5823 launched: '/Users/user/cs59/c-and-asm/fact5' (arm64) Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1 frame #0: 0x0000000100003f38 fact5`main fact5`main: -> 0x100003f38 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003f3c <+4>: stp x29, x30, [sp, #0x10] 0x100003f40 <+8>: add x29, sp, #0x10 ; =0x10 0x100003f44 <+12>: mov w8, #0x0 Target 0: (fact5) stopped. (lldb) disas -n main fact5`main: -> 0x100003f38 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003f3c <+4>: stp x29, x30, [sp, #0x10] 0x100003f40 <+8>: add x29, sp, #0x10 ; =0x10 0x100003f44 <+12>: mov w8, #0x0 0x100003f48 <+16>: str w8, [sp, #0x8] 0x100003f4c <+20>: stur wzr, [x29, #-0x4] 0x100003f50 <+24>: mov w0, #0x7 0x100003f54 <+28>: bl 0x100003ee4 ; fact <<--- call itself! 0x100003f58 <+32>: mov x10, x0 0x100003f5c <+36>: adrp x0, 0 0x100003f60 <+40>: add x0, x0, #0xfb4 ; =0xfb4 0x100003f64 <+44>: mov x9, sp 0x100003f68 <+48>: mov x8, x10 0x100003f6c <+52>: str x8, [x9] 0x100003f70 <+56>: bl 0x100003f84 ; symbol stub for: printf 0x100003f74 <+60>: ldr w0, [sp, #0x8] 0x100003f78 <+64>: ldp x29, x30, [sp, #0x10] 0x100003f7c <+68>: add sp, sp, #0x20 ; =0x20 0x100003f80 <+72>: ret // Question: what is a "stub" above at 0x100003f70 <+56>? // Answer: the executable we just compiled does not include the actual code for printf. // Instead, we create a short piece of code (a 'stub') as a stand-in for printf, // and "bl" to that stub for any calls to printf made in our file. // This 'stub' code will jump to the actual address of printf, which will be placed // in a known location by the OS loader once it loads the libc.so.6 library code. // This is the stub: (lldb) disas -a 0x100003f84 fact5`printf: 0x100003f84 <+0>: nop 0x100003f88 <+4>: ldr x16, #0x4078 ; (void *)0x0000000100003fa8 0x100003f8c <+8>: br x16 // We'll follow through the dynamic linking process at another time. For now, // let's resume executing our function. We stop at the start of fact(): (lldb) c Process 5823 resuming Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100003ee4 fact5`fact fact5`fact: <<--- object_file`function hint -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] Target 0: (fact5) stopped. // Oops, I mistyped here. I meant "register" not "run". Luckily, LLDB asked if I really // wanted to kill the process: (lldb) r r $sp There is a running process, kill it and restart?: [Y/n] n // OK, we are now at fact(7) (lldb) reg r $sp sp = 0x000000016fdff700 (lldb) reg r $sp $w0 sp = 0x000000016fdff700 w0 = 0x00000007 // Continue (lldb) c Process 5823 resuming Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100003ee4 fact5`fact fact5`fact: -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] Target 0: (fact5) stopped. // And now we back at the same breakpoint, but now our argument and stack frame // are different: (lldb) reg r $sp $w0 sp = 0x000000016fdff6e0 w0 = 0x00000006 // This is our stack now, before the preamble allocates the next frame. // So we see the previous stack frame. (I could've just said "x $sp"): (lldb) x 0x000000016fdff6e0 0x16fdff6e0: 00 00 00 00 07 00 00 00 07 00 00 00 00 00 00 00 ................ 0x16fdff6f0: 10 f7 df 6f 01 00 00 00 58 3f 00 00 01 00 00 00 ...o....X?...... // The same bytes as 4-byte words, so that we can quickly spot integers, like 7: (lldb) x/32w 0x000000016fdff6e0 0x16fdff6e0: 0x00000000 0x00000007 0x00000007 0x00000000 0x16fdff6f0: 0x6fdff710 0x00000001 0x00003f58 0x00000001 ^^^^^^^^^^^^^^^^^^^^^ this a previously saved x29, 0x000000016fdff710 ^^^^^^^^^^^^^^^^^^^^^ this is a saved x30, 0x0000000100003f58 0x16fdff700: 0x00000000 0x00000000 0x00000000 0x00000000 0x16fdff710: 0x6fdff730 0x00000001 0x8ca89430 0x00000001 0x16fdff720: 0x8ca89430 0x00000001 0x00000000 0x00000000 0x16fdff730: 0x00000000 0x00000000 0x00000000 0x00000000 0x16fdff740: 0x00000000 0x00000000 0x00000000 0x00000001 0x16fdff750: 0x00000001 0x00000000 0x6fdff928 0x00000001 (lldb) c Process 5823 resuming Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100003ee4 fact5`fact fact5`fact: -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] Target 0: (fact5) stopped. // And another iteration: (lldb) reg r $sp $w0 sp = 0x000000016fdff6c0 w0 = 0x00000005 // This is our stack now, with two frames of fact(): (lldb) x/32w $sp 0x16fdff6c0: 0x000112a8 0x00000006 0x00000006 0x00000000 0x16fdff6d0: 0x6fdff6f0 0x00000001 0x00003f1c 0x00000001 ___frame for fact(6) 0x16fdff6e0: 0x00000000 0x00000007 0x00000007 0x00000000 0x16fdff6f0: 0x6fdff710 0x00000001 0x00003f58 0x00000001 ___frame for fact(7) 0x16fdff700: 0x00000000 0x00000000 0x00000000 0x00000000 0x16fdff710: 0x6fdff730 0x00000001 0x8ca89430 0x00000001 0x16fdff720: 0x8ca89430 0x00000001 0x00000000 0x00000000 0x16fdff730: 0x00000000 0x00000000 0x00000000 0x00000000 // Moar! moar! frames: (lldb) c Process 5823 resuming Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100003ee4 fact5`fact fact5`fact: -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] Target 0: (fact5) stopped. (lldb) x/32w $sp 0x16fdff6a0: 0x00000000 0x00000005 0x00000005 0x00000001 0x16fdff6b0: 0x6fdff6d0 0x00000001 0x00003f1c 0x00000001 ___fact(5) 0x16fdff6c0: 0x000112a8 0x00000006 0x00000006 0x00000000 0x16fdff6d0: 0x6fdff6f0 0x00000001 0x00003f1c 0x00000001 ___fact(6) 0x16fdff6e0: 0x00000000 0x00000007 0x00000007 0x00000000 0x16fdff6f0: 0x6fdff710 0x00000001 0x00003f58 0x00000001 ___fact(7) 0x16fdff700: 0x00000000 0x00000000 0x00000000 0x00000000 0x16fdff710: 0x6fdff730 0x00000001 0x8ca89430 0x00000001 // We can group these bytes into 64-bit words to see the addresses better: (lldb) x/32xg $sp 0x16fdff6a0: 0x0000000500000000 0x0000000100000005 0x16fdff6b0: 0x000000016fdff6d0 0x0000000100003f1c <<-- fact(5)'s saved x29 and x30 0x16fdff6c0: 0x00000006000112a8 0x0000000000000006 0x16fdff6d0: 0x000000016fdff6f0 0x0000000100003f1c <<-- fact(6)'s saved x29 and x30 0x16fdff6e0: 0x0000000700000000 0x0000000000000007 0x16fdff6f0: 0x000000016fdff710 0x0000000100003f58 <<-- fact(7)'s saved x29 and x30 0x16fdff700: 0x0000000000000000 0x0000000000000000 0x16fdff710: 0x000000016fdff730 0x000000018ca89430 0x16fdff720: 0x000000018ca89430 0x0000000000000000 0x16fdff730: 0x0000000000000000 0x0000000000000000 0x16fdff740: 0x0000000000000000 0x0000000100000000 0x16fdff750: 0x0000000000000001 0x000000016fdff928 0x16fdff760: 0x0000000000000000 0x000000016fdff949 0x16fdff770: 0x000000016fdff953 0x000000016fdff960 0x16fdff780: 0x000000016fdff988 0x000000016fdff9c4 0x16fdff790: 0x000000016fdff9cc 0x000000016fdff9e4 // Note that whenever stack frames are allocated, they are *not* zeroed out, // so we can see some bytes left of prior stack frames if not overwritten by our code. (lldb) c Process 5823 resuming Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100003ee4 fact5`fact fact5`fact: -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] Target 0: (fact5) stopped. (lldb) c Process 5823 resuming Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100003ee4 fact5`fact fact5`fact: -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] Target 0: (fact5) stopped. (lldb) c Process 5823 resuming Process 5823 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 frame #0: 0x0000000100003ee4 fact5`fact fact5`fact: -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] Target 0: (fact5) stopped. (lldb) reg r $sp $w0 sp = 0x000000016fdff640 w0 = 0x00000001 ____________saved n and intermediate result (lldb) x/32w $sp VVVVVVVVVV VVVVVVVVVV 0x16fdff640: 0x000cbad0 0x00000002 0x00000002 0x00000000 0x16fdff650: 0x6fdff670 0x00000001 0x00003f1c 0x00000001 __fact(2) 0x16fdff660: 0x00010000 0x00000003 0x00000003 0x00000001 0x16fdff670: 0x6fdff690 0x00000001 0x00003f1c 0x00000001 __fact(3) 0x16fdff680: 0x00090088 0x00000004 0x00000004 0x00000001 0x16fdff690: 0x6fdff6b0 0x00000001 0x00003f1c 0x00000001 __fact(4) 0x16fdff6a0: 0x00000000 0x00000005 0x00000005 0x00000001 0x16fdff6b0: 0x6fdff6d0 0x00000001 0x00003f1c 0x00000001 __fact(5) (lldb) x/32b $sp 0x16fdff640: 0xd0 0xba 0x0c 0x00 0x02 0x00 0x00 0x00 0x16fdff648: 0x02 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x16fdff650: 0x70 0xf6 0xdf 0x6f 0x01 0x00 0x00 0x00 0x16fdff658: 0x1c 0x3f 0x00 0x00 0x01 0x00 0x00 0x00 /// Note that all saved link register ("return") addresses are the same for these frames, // and point to the instruction right after the fact() call: (lldb) reg r x30 lr = 0x0000000100003f1c fact5`fact + 56 (lldb) disas -n fact fact5`fact: -> 0x100003ee4 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003ee8 <+4>: stp x29, x30, [sp, #0x10] 0x100003eec <+8>: add x29, sp, #0x10 ; =0x10 0x100003ef0 <+12>: str w0, [sp, #0x8] <<--- this is our argument, n 0x100003ef4 <+16>: ldr w8, [sp, #0x8] 0x100003ef8 <+20>: cbnz w8, 0x100003f08 ; <+36> <<--- is our n zero? 0x100003efc <+24>: mov w8, #0x1 <<--- yes, prepare to return 1 0x100003f00 <+28>: stur w8, [x29, #-0x4] 0x100003f04 <+32>: b 0x100003f28 ; <+68> <<--- jump to exit 0x100003f08 <+36>: ldr w8, [sp, #0x8] <<--- no, save n 0x100003f0c <+40>: str w8, [sp, #0x4] 0x100003f10 <+44>: ldr w8, [sp, #0x8] 0x100003f14 <+48>: subs w0, w8, #0x1 ; =0x1 <<--- make n-1 0x100003f18 <+52>: bl 0x100003ee4 ; <+0> <<--- call self! bl to start of fact() 0x100003f1c <+56>: ldr w8, [sp, #0x4] <<--- return here, pick up "n" saved in this frame 0x100003f20 <+60>: mul w8, w8, w0 <<--- fact(n-1) is now in x0, multiply 0x100003f24 <+64>: stur w8, [x29, #-0x4] 0x100003f28 <+68>: ldur w0, [x29, #-0x4] 0x100003f2c <+72>: ldp x29, x30, [sp, #0x10] 0x100003f30 <+76>: add sp, sp, #0x20 ; =0x20 0x100003f34 <+80>: ret (lldb) x/32w $sp 0x16fdff640: 0x000cbad0 0x00000002 0x00000002 0x00000000 0x16fdff650: 0x6fdff670 0x00000001 0x00003f1c 0x00000001 0x16fdff660: 0x00010000 0x00000003 0x00000003 0x00000001 0x16fdff670: 0x6fdff690 0x00000001 0x00003f1c 0x00000001 0x16fdff680: 0x00090088 0x00000004 0x00000004 0x00000001 0x16fdff690: 0x6fdff6b0 0x00000001 0x00003f1c 0x00000001 0x16fdff6a0: 0x00000000 0x00000005 0x00000005 0x00000001 0x16fdff6b0: 0x6fdff6d0 0x00000001 0x00003f1c 0x00000001 // Let's see the full stack: (lldb) x/48w $sp 0x16fdff640: 0x000cbad0 0x00000002 0x00000002 0x00000000 0x16fdff650: 0x6fdff670 0x00000001 0x00003f1c 0x00000001 0x16fdff660: 0x00010000 0x00000003 0x00000003 0x00000001 0x16fdff670: 0x6fdff690 0x00000001 0x00003f1c 0x00000001 0x16fdff680: 0x00090088 0x00000004 0x00000004 0x00000001 0x16fdff690: 0x6fdff6b0 0x00000001 0x00003f1c 0x00000001 0x16fdff6a0: 0x00000000 0x00000005 0x00000005 0x00000001 0x16fdff6b0: 0x6fdff6d0 0x00000001 0x00003f1c 0x00000001 0x16fdff6c0: 0x000112a8 0x00000006 0x00000006 0x00000000 0x16fdff6d0: 0x6fdff6f0 0x00000001 0x00003f1c 0x00000001 0x16fdff6e0: 0x00000000 0x00000007 0x00000007 0x00000000 0x16fdff6f0: 0x6fdff710 0x00000001 0x00003f58 0x00000001 (lldb) disas -n main fact5`main: 0x100003f38 <+0>: sub sp, sp, #0x20 ; =0x20 0x100003f3c <+4>: stp x29, x30, [sp, #0x10] 0x100003f40 <+8>: add x29, sp, #0x10 ; =0x10 0x100003f44 <+12>: mov w8, #0x0 0x100003f48 <+16>: str w8, [sp, #0x8] 0x100003f4c <+20>: stur wzr, [x29, #-0x4] 0x100003f50 <+24>: mov w0, #0x7 0x100003f54 <+28>: bl 0x100003ee4 ; fact 0x100003f58 <+32>: mov x10, x0 0x100003f5c <+36>: adrp x0, 0 0x100003f60 <+40>: add x0, x0, #0xfb4 ; =0xfb4 0x100003f64 <+44>: mov x9, sp 0x100003f68 <+48>: mov x8, x10 0x100003f6c <+52>: str x8, [x9] 0x100003f70 <+56>: bl 0x100003f84 ; symbol stub for: printf 0x100003f74 <+60>: ldr w0, [sp, #0x8] 0x100003f78 <+64>: ldp x29, x30, [sp, #0x10] 0x100003f7c <+68>: add sp, sp, #0x20 ; =0x20 0x100003f80 <+72>: ret // Notice that the list of breakpoints shows a counter of how many times each // breakpoint was hit: (lldb) br l Current breakpoints: 1: name = 'fact', locations = 1, resolved = 1, hit count = 7 1.1: where = fact5`fact, address = 0x0000000100003ee4, resolved, hit count = 7 <<--- 2: name = 'main', locations = 1, resolved = 1, hit count = 1 2.1: where = fact5`main, address = 0x0000000100003f38, resolved, hit count = 1 (lldb) ^D /// There's an easier way to see the stack grow: % cat fact5.c #include /* a very naive recursive factorial */ unsigned int fact(unsigned int n) { printf("%p %d\n", &n, n); // print the address of n if( n == 0 ) return 1; return n * fact(n-1); } int main() { printf("%d\n", fact(7)); return 0; } // Note that the stack frame size increased. It was 0x20, now it's 0x30: % gcc -Wall -o fact5 fact5.c % ./fact5 0x16b97b7e8 7 0x16b97b7b8 6 0x16b97b788 5 0x16b97b758 4 0x16b97b728 3 0x16b97b6f8 2 0x16b97b6c8 1 0x16b97b698 0 5040 // And if we optimize the stack frame gets bigger (0x40 == 64), because of having // to save callee-saved registers x19 and x20 that are used by optimized version: % gcc -O2 -Wall -o fact5 fact5.c % ./fact5 0x16d9877dc 7 0x16d98779c 6 0x16d98775c 5 0x16d98771c 4 0x16d9876dc 3 0x16d98769c 2 0x16d98765c 1 0x16d98761c 0 5040 // Also notice that the stack addresses vary in the page part, but not in the // offsets within a page (last three hex digits). This variation is deliberate // and is chosen by the OS loader. It is called Address Space Load Randomization (ASLR), // so that not every memory image of the running program looks exactly the same. % ./fact5 0x16f9f77dc 7 0x16f9f779c 6 0x16f9f775c 5 0x16f9f771c 4 0x16f9f76dc 3 0x16f9f769c 2 0x16f9f765c 1 0x16f9f761c 0 5040 % ./fact5 0x16af077dc 7 0x16af0779c 6 0x16af0775c 5 0x16af0771c 4 0x16af076dc 3 0x16af0769c 2 0x16af0765c 1 0x16af0761c 0 5040 % ./fact5 0x16f94f7dc 7 0x16f94f79c 6 0x16f94f75c 5 0x16f94f71c 4 0x16f94f6dc 3 0x16f94f69c 2 0x16f94f65c 1 0x16f94f61c 0 5040 % ./fact5 0x16f6d77dc 7 0x16f6d779c 6 0x16f6d775c 5 0x16f6d771c 4 0x16f6d76dc 3 0x16f6d769c 2 0x16f6d765c 1 0x16f6d761c 0 5040 % ./fact5 0x16b7937dc 7 0x16b79379c 6 0x16b79375c 5 0x16b79371c 4 0x16b7936dc 3 0x16b79369c 2 0x16b79365c 1 0x16b79361c 0 5040 % ./fact5 0x16f0177dc 7 0x16f01779c 6 0x16f01775c 5 0x16f01771c 4 0x16f0176dc 3 0x16f01769c 2 0x16f01765c 1 0x16f01761c 0 5040 % ./fact5 0x16b46b7dc 7 0x16b46b79c 6 0x16b46b75c 5 0x16b46b71c 4 0x16b46b6dc 3 0x16b46b69c 2 0x16b46b65c 1 0x16b46b61c 0 5040 % ./fact5 0x16b7eb7dc 7 0x16b7eb79c 6 0x16b7eb75c 5 0x16b7eb71c 4 0x16b7eb6dc 3 0x16b7eb69c 2 0x16b7eb65c 1 0x16b7eb61c 0 5040 % ./fact5 0x16f7d77dc 7 0x16f7d779c 6 0x16f7d775c 5 0x16f7d771c 4 0x16f7d76dc 3 0x16f7d769c 2 0x16f7d765c 1 0x16f7d761c 0 5040 % ./fact5 0x16dafb7dc 7 0x16dafb79c 6 0x16dafb75c 5 0x16dafb71c 4 0x16dafb6dc 3 0x16dafb69c 2 0x16dafb65c 1 0x16dafb61c 0 5040 % ./fact5 0x16f1137dc 7 0x16f11379c 6 0x16f11375c 5 0x16f11371c 4 0x16f1136dc 3 0x16f11369c 2 0x16f11365c 1 0x16f11361c 0 5040 % ./fact5 0x16afb77dc 7 0x16afb779c 6 0x16afb775c 5 0x16afb771c 4 0x16afb76dc 3 0x16afb769c 2 0x16afb765c 1 0x16afb761c 0 5040 ---- To be continued