;; I started (FACT1 3000000 1) in class but it was taking way too long. ;; I wanted to find our just how long it would take. Spoiler: 3 hours, ;; due to interesting architectural issues with GCL and my runtime; ;; by contrast, SBCL was done in minutes, for similarly interesting reasons. ;; So I started GCL, with compiled FACT1 running, and then attached the debugger ;; to that process: sergey@snowball lisp % pgrep gcl 50918 sergey@snowball lisp % lldb -p 50918 (lldb) process attach --pid 50918 Process 50918 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP frame #0: 0x00007fff205ea03c libsystem_platform.dylib`_platform_memmove$VARIANT$Rosetta + 140 libsystem_platform.dylib`_platform_memmove$VARIANT$Rosetta: -> 0x7fff205ea03c <+140>: movntiq %rbx, (%rcx) 0x7fff205ea040 <+144>: movntiq %r9, 0x8(%rcx) 0x7fff205ea045 <+149>: movntiq %r10, 0x10(%rcx) 0x7fff205ea04a <+154>: movntiq %r11, 0x18(%rcx) Target 0: (saved_ansi_gcl) stopped. Executable module set to "/opt/local/lib/gcl-2.6.14/unixport/saved_ansi_gcl". Architecture set to: x86_64-apple-macosx-. // The process got stopped at a random place, wherever the attach system call // has found it. We need to get to the actual code for FACT1. // The function FACT1 and the object file "facta.o" are loaded _somewhere_ // in GCL's address space. We can get a hint from (LOAD "facta.o") in GCL: // >(load "facta.o") // ;; Loading "facta.o" // start address -T 0x10b2f7330 ;; Finished loading "facta.o" (lldb) dis -a 0x10b2f7330 error: Could not find function bounds for address 0x10b2f7330 // Stands to reason, LLDB is not familiar with GCL internals. So we can // manually disassemble and look for matches with facta.o (lldb) x/10i 0x10b2f7330 0x10b2f7330: 48 8d 3d b1 02 00 00 leaq 0x2b1(%rip), %rdi 0x10b2f7337: e9 14 bf d1 f4 jmp 0x100013250 ; do_init 0x10b2f733c: 0f 1f 40 00 nopl (%rax) 0x10b2f7340: 55 pushq %rbp 0x10b2f7341: 41 57 pushq %r15 0x10b2f7343: 41 56 pushq %r14 0x10b2f7345: 41 55 pushq %r13 0x10b2f7347: 41 54 pushq %r12 0x10b2f7349: 53 pushq %rbx 0x10b2f734a: 48 83 ec 18 subq $0x18, %rsp // Seems to make sense, as it matched the top of facta.o, but we now need to // find the FACT1 itself. Then we find the top of the loop where we can // intercept the process and examine its registers, and will find which N // it is working on. // We know FACT1 got labeled L1 in the facta.c file. Then the top of the loop // was labeled TTL, but it was a local label, and thus not saved in the // symbol table of facta.o . We'll have to find that address by searching // the assembly code. (lldb) b TTL Breakpoint 1: no locations (pending). WARNING: Unable to resolve breakpoint to any actual locations. // No such luck with TTL. We'll have to look at the assembly the hard way. // We use -r with objdump because otherwise we won't know where the CALLs and // jumps are going. (lldb) zsh: suspended lldb -p 50918 sergey@snowball lisp % objdump -r -d facta.o facta.o: file format mach-o 64-bit x86-64 Disassembly of section __TEXT,__text: 0000000000000000 <_init_code>: 0: 48 8d 3d 00 00 00 00 leaq (%rip), %rdi # 7 <_init_code+0x7> 0000000000000003: X86_64_RELOC_SIGNED _VVi 7: e9 00 00 00 00 jmp 0xc <_init_code+0xc> 0000000000000008: X86_64_RELOC_BRANCH _do_init c: 0f 1f 40 00 nopl (%rax) 0000000000000010 <_L1>: // <--- this is the top of FACT1 10: 55 pushq %rbp 11: 41 57 pushq %r15 13: 41 56 pushq %r14 15: 41 55 pushq %r13 17: 41 54 pushq %r12 19: 53 pushq %rbx 1a: 48 83 ec 18 subq $24, %rsp 1e: 48 8b 05 00 00 00 00 movq (%rip), %rax # 25 <_L1+0x15> 0000000000000021: X86_64_RELOC_GOT_LOAD _vs_base@GOTPCREL 25: 4c 8b 38 movq (%rax), %r15 28: 49 8d 47 18 leaq 24(%r15), %rax 2c: 48 89 44 24 08 movq %rax, 8(%rsp) 31: 48 8b 05 00 00 00 00 movq (%rip), %rax # 38 <_L1+0x28> 0000000000000034: X86_64_RELOC_GOT_LOAD _vs_top@GOTPCREL 38: 48 8b 00 movq (%rax), %rax 3b: 48 8b 0d 00 00 00 00 movq (%rip), %rcx # 42 <_L1+0x32> 000000000000003e: X86_64_RELOC_GOT_LOAD _vs_limit@GOTPCREL 42: 48 3b 01 cmpq (%rcx), %rax 45: 72 05 jb 0x4c <_L1+0x3c> 47: e8 00 00 00 00 callq 0x4c <_L1+0x3c> 0000000000000048: X86_64_RELOC_BRANCH _vs_overflow 4c: 49 be 00 00 00 00 00 00 00 a0 movabsq $-6917529027641081856, %r14 56: 48 bd 00 00 00 00 00 00 00 80 movabsq $-9223372036854775808, %rbp 60: 49 bd 00 00 00 00 00 00 00 60 movabsq $6917529027641081856, %r13 6a: 49 8b 1f movq (%r15), %rbx 6d: 4c 89 7c 24 10 movq %r15, 16(%rsp) 72: 4d 8b 7f 08 movq 8(%r15), %r15 76: 48 8b 44 24 08 movq 8(%rsp), %rax 7b: 48 8b 0d 00 00 00 00 movq (%rip), %rcx # 82 <_L1+0x72> 000000000000007e: X86_64_RELOC_GOT_LOAD _vs_top@GOTPCREL 82: 48 89 01 movq %rax, (%rcx) 85: 48 85 db testq %rbx, %rbx 88: 79 76 jns 0x100 <_L1+0xf0> 8a: eb 1a jmp 0xa6 <_L1+0x96> 8c: 0f 1f 40 00 nopl (%rax) 90: 48 89 df movq %rbx, %rdi 93: 4c 89 fe movq %r15, %rsi 96: e8 00 00 00 00 callq 0x9b <_L1+0x8b> 0000000000000097: X86_64_RELOC_BRANCH _number_times 9b: 49 89 c7 movq %rax, %r15 // <-- top of the loop 9e: 4c 89 e3 movq %r12, %rbx a1: 48 85 db testq %rbx, %rbx // <-- is RBX zero or negative? a4: 79 5a jns 0x100 <_L1+0xf0> a6: 4c 39 f3 cmpq %r14, %rbx a9: 0f 84 d2 01 00 00 je 0x281 <_L1+0x271> af: 48 8d 04 2b leaq (%rbx,%rbp), %rax b3: 48 83 c0 ff addq $-1, %rax b7: 48 b9 00 00 00 00 00 00 00 40 movabsq $4611686018427387904, %rcx c1: 48 39 c8 cmpq %rcx, %rax c4: 73 1a jae 0xe0 <_L1+0xd0> c6: 4c 8d 63 ff leaq -1(%rbx), %r12 ca: 4c 85 fb testq %r15, %rbx cd: 79 c1 jns 0x90 <_L1+0x80> cf: eb 5a jmp 0x12b <_L1+0x11b> d1: 66 2e 0f 1f 84 00 00 00 00 00 nopw %cs:(%rax,%rax) db: 0f 1f 44 00 00 nopl (%rax,%rax) e0: 4a 8d 3c 2b leaq (%rbx,%r13), %rdi e4: 48 83 c7 ff addq $-1, %rdi e8: e8 00 00 00 00 callq 0xed <_L1+0xdd> 00000000000000e9: X86_64_RELOC_BRANCH _make_fixnum1 ed: 49 89 c4 movq %rax, %r12 f0: 4c 85 fb testq %r15, %rbx f3: 79 9b jns 0x90 <_L1+0x80> f5: eb 34 jmp 0x12b <_L1+0x11b> f7: 66 0f 1f 84 00 00 00 00 00 nopw (%rax,%rax) 100: 48 89 df movq %rbx, %rdi // <-- we land here if R12 was 0 103: 4c 89 f6 movq %r14, %rsi 106: e8 00 00 00 00 callq 0x10b <_L1+0xfb> 0000000000000107: X86_64_RELOC_BRANCH _number_compare 10b: 85 c0 testl %eax, %eax 10d: 0f 84 6e 01 00 00 je 0x281 <_L1+0x271> 113: 49 8d 76 01 leaq 1(%r14), %rsi 117: 48 89 df movq %rbx, %rdi //<-- this is N 11a: e8 00 00 00 00 callq 0x11f <_L1+0x10f> 000000000000011b: X86_64_RELOC_BRANCH _number_minus // N-1 11f: 49 89 c4 movq %rax, %r12 // result on _number_minus is saved in R12 122: 4c 85 fb testq %r15, %rbx 125: 0f 89 65 ff ff ff jns 0x90 <_L1+0x80> 12b: 4c 01 eb addq %r13, %rbx 12e: 4d 01 ef addq %r13, %r15 131: 48 89 de movq %rbx, %rsi 134: 48 f7 de negq %rsi 137: 48 0f 4c f3 cmovlq %rbx, %rsi 13b: 4c 89 fa movq %r15, %rdx 13e: 48 f7 da negq %rdx 141: 49 0f 4c d7 cmovlq %r15, %rdx 145: 31 c0 xorl %eax, %eax 147: 66 0f 1f 84 00 00 00 00 00 nopw (%rax,%rax) 150: 48 89 ef movq %rbp, %rdi 153: 89 c1 movl %eax, %ecx 155: 48 d3 ef shrq %cl, %rdi 158: 48 85 f7 testq %rsi, %rdi 15b: 75 4b jne 0x1a8 <_L1+0x198> 15d: 8d 48 01 leal 1(%rax), %ecx 160: 48 89 ef movq %rbp, %rdi 163: 48 d3 ef shrq %cl, %rdi 166: 48 85 f7 testq %rsi, %rdi 169: 75 2d jne 0x198 <_L1+0x188> 16b: 8d 48 02 leal 2(%rax), %ecx 16e: 48 89 ef movq %rbp, %rdi 171: 48 d3 ef shrq %cl, %rdi 174: 48 85 f7 testq %rsi, %rdi 177: 75 25 jne 0x19e <_L1+0x18e> 179: 8d 48 03 leal 3(%rax), %ecx 17c: 48 89 ef movq %rbp, %rdi 17f: 48 d3 ef shrq %cl, %rdi 182: 48 85 f7 testq %rsi, %rdi 185: 75 1d jne 0x1a4 <_L1+0x194> 187: 48 83 c0 04 addq $4, %rax 18b: 48 83 f8 40 cmpq $64, %rax 18f: 75 bf jne 0x150 <_L1+0x140> 191: be 40 00 00 00 movl $64, %esi 196: eb 14 jmp 0x1ac <_L1+0x19c> 198: 48 83 c0 01 addq $1, %rax 19c: eb 0a jmp 0x1a8 <_L1+0x198> 19e: 48 83 c0 02 addq $2, %rax 1a2: eb 04 jmp 0x1a8 <_L1+0x198> 1a4: 48 83 c0 03 addq $3, %rax 1a8: 48 0f be f0 movsbq %al, %rsi 1ac: 31 c0 xorl %eax, %eax 1ae: 66 90 nop 1b0: 48 89 ef movq %rbp, %rdi 1b3: 89 c1 movl %eax, %ecx 1b5: 48 d3 ef shrq %cl, %rdi 1b8: 48 85 d7 testq %rdx, %rdi 1bb: 0f 85 a3 00 00 00 jne 0x264 <_L1+0x254> 1c1: 8d 48 01 leal 1(%rax), %ecx 1c4: 48 89 ef movq %rbp, %rdi 1c7: 48 d3 ef shrq %cl, %rdi 1ca: 48 85 d7 testq %rdx, %rdi 1cd: 0f 85 81 00 00 00 jne 0x254 <_L1+0x244> 1d3: 8d 48 02 leal 2(%rax), %ecx 1d6: 48 89 ef movq %rbp, %rdi 1d9: 48 d3 ef shrq %cl, %rdi 1dc: 48 85 d7 testq %rdx, %rdi 1df: 75 79 jne 0x25a <_L1+0x24a> 1e1: 8d 48 03 leal 3(%rax), %ecx 1e4: 48 89 ef movq %rbp, %rdi 1e7: 48 d3 ef shrq %cl, %rdi 1ea: 48 85 d7 testq %rdx, %rdi 1ed: 75 71 jne 0x260 <_L1+0x250> 1ef: 48 83 c0 04 addq $4, %rax 1f3: 48 83 f8 40 cmpq $64, %rax 1f7: 75 b7 jne 0x1b0 <_L1+0x1a0> 1f9: b8 40 00 00 00 movl $64, %eax 1fe: 48 01 f0 addq %rsi, %rax 201: 48 83 f8 42 cmpq $66, %rax 205: 72 6a jb 0x271 <_L1+0x261> 207: 66 0f 1f 84 00 00 00 00 00 nopw (%rax,%rax) 210: 49 0f af df imulq %r15, %rbx 214: 48 b8 00 00 00 00 00 00 00 20 movabsq $2305843009213693952, %rax 21e: 48 01 d8 addq %rbx, %rax 221: 48 b9 00 00 00 00 00 00 00 40 movabsq $4611686018427387904, %rcx 22b: 48 39 c8 cmpq %rcx, %rax 22e: 73 17 jae 0x247 <_L1+0x237> 230: 4c 01 f3 addq %r14, %rbx 233: 49 89 df movq %rbx, %r15 236: 4c 89 e3 movq %r12, %rbx 239: 48 85 db testq %rbx, %rbx 23c: 0f 89 be fe ff ff jns 0x100 <_L1+0xf0> 242: e9 5f fe ff ff jmp 0xa6 <_L1+0x96> 247: 48 89 df movq %rbx, %rdi 24a: e8 00 00 00 00 callq 0x24f <_L1+0x23f> 000000000000024b: X86_64_RELOC_BRANCH _make_fixnum1 24f: e9 47 fe ff ff jmp 0x9b <_L1+0x8b> 254: 48 83 c0 01 addq $1, %rax 258: eb 0a jmp 0x264 <_L1+0x254> 25a: 48 83 c0 02 addq $2, %rax 25e: eb 04 jmp 0x264 <_L1+0x254> 260: 48 83 c0 03 addq $3, %rax 264: 48 0f be c0 movsbq %al, %rax 268: 48 01 f0 addq %rsi, %rax 26b: 48 83 f8 42 cmpq $66, %rax 26f: 73 9f jae 0x210 <_L1+0x200> 271: 48 89 df movq %rbx, %rdi 274: 4c 89 fe movq %r15, %rsi 277: e8 00 00 00 00 callq 0x27c <_L1+0x26c> 0000000000000278: X86_64_RELOC_BRANCH _fixnum_times 27c: e9 1a fe ff ff jmp 0x9b <_L1+0x8b> // <-- LOOP back 281: 48 8b 4c 24 10 movq 16(%rsp), %rcx 286: 4c 89 79 10 movq %r15, 16(%rcx) 28a: 48 83 c1 10 addq $16, %rcx 28e: 48 8b 05 00 00 00 00 movq (%rip), %rax # 295 <_L1+0x285> 0000000000000291: X86_64_RELOC_GOT_LOAD _vs_base@GOTPCREL 295: 48 89 08 movq %rcx, (%rax) 298: 48 8b 44 24 08 movq 8(%rsp), %rax 29d: 48 8b 0d 00 00 00 00 movq (%rip), %rcx # 2a4 <_L1+0x294> 00000000000002a0: X86_64_RELOC_GOT_LOAD _vs_top@GOTPCREL 2a4: 48 89 01 movq %rax, (%rcx) 2a7: 48 83 c4 18 addq $24, %rsp 2ab: 5b popq %rbx 2ac: 41 5c popq %r12 2ae: 41 5d popq %r13 2b0: 41 5e popq %r14 2b2: 41 5f popq %r15 2b4: 5d popq %rbp 2b5: c3 retq // So we have a hunch that the loop starts at the offset of 0x9b from the top // of our object file facta.o, loaded at 0x10b2f7330 and also that R12 // contains our N or a reference to our N at that point. So let's set // a breakpoint there. sergey@snowball lisp % fg [1] + continued lldb -p 50918 (lldb) print 0x10b2f7330 + 0x9b (long) $0 = 4482626507 // Meh, I need hex, not decimal (lldb) print/x 0x10b2f7330 + 0x9b (long) $1 = 0x000000010b2f73cb (lldb) x/100i 0x10b2f73cb error: Normally, 'memory read' will not read over 1024 bytes of data. error: Please use --force to override this restriction just once. error: or set target.max-memory-read-size if you will often need a larger limit. (lldb) x/100i --force 0x10b2f73cb 0x10b2f73cb: 49 89 c7 movq %rax, %r15 0x10b2f73ce: 4c 89 e3 movq %r12, %rbx // <-- R12 0x10b2f73d1: 48 85 db testq %rbx, %rbx 0x10b2f73d4: 79 5a jns 0x10b2f7430 0x10b2f73d6: 4c 39 f3 cmpq %r14, %rbx 0x10b2f73d9: 0f 84 d2 01 00 00 je 0x10b2f75b1 0x10b2f73df: 48 8d 04 2b leaq (%rbx,%rbp), %rax 0x10b2f73e3: 48 83 c0 ff addq $-0x1, %rax [..skipped.. I really didn't need to see 100 instructions.] // Set breakpoint (lldb) b 0x10b2f73cb Breakpoint 2: where = saved_ansi_gcl`saved_ansi_gcl[0x000000010b2f73cb], address = 0x000000010b2f73cb (lldb) c Process 50918 resuming Process 50918 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1 frame #0: 0x000000010b2f73cb saved_ansi_gcl -> 0x10b2f73cb: movq %rax, %r15 0x10b2f73ce: movq %r12, %rbx 0x10b2f73d1: testq %rbx, %rbx 0x10b2f73d4: jns 0x10b2f7430 Target 0: (saved_ansi_gcl) stopped. // Let's see the registers (lldb) reg read General Purpose Registers: rax = 0x000000010b6f68f8 rbx = 0xa0000000002c65bf rcx = 0x00000000953822b0 rdx = 0xfffffffffffffff8 rdi = 0x0000000000000001 rsi = 0x00000005196b0460 rbp = 0x8000000000000000 rsp = 0x0000000b0f3c51b0 r8 = 0x0000000000000000 r9 = 0x585c8c41211ca59a r10 = 0x000000010b6f6000 r11 = 0x0000000000000001 r12 = 0xa0000000002c65be // <-- our R12 r13 = 0x6000000000000000 r14 = 0xa000000000000000 r15 = 0x000000010b6f68e0 rip = 0x000000010b2f73cb rflags = 0x0000000000000202 cs = 0x000000000000002b fs = 0x0000000000000000 gs = 0x0000000000000000 // Let's run a couple of iterations through the loop (lldb) c Process 50918 resuming Process 50918 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1 frame #0: 0x000000010b2f73cb saved_ansi_gcl -> 0x10b2f73cb: movq %rax, %r15 0x10b2f73ce: movq %r12, %rbx 0x10b2f73d1: testq %rbx, %rbx 0x10b2f73d4: jns 0x10b2f7430 Target 0: (saved_ansi_gcl) stopped. (lldb) c Process 50918 resuming Process 50918 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1 frame #0: 0x000000010b2f73cb saved_ansi_gcl -> 0x10b2f73cb: movq %rax, %r15 0x10b2f73ce: movq %r12, %rbx 0x10b2f73d1: testq %rbx, %rbx 0x10b2f73d4: jns 0x10b2f7430 Target 0: (saved_ansi_gcl) stopped. // Now our R12 is reduced by 2. This looks like our N (0xE - 2 = 0xC): (lldb) reg r r12 r12 = 0xa0000000002c65bc (lldb) c Process 50918 resuming Process 50918 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1 frame #0: 0x000000010b2f73cb saved_ansi_gcl -> 0x10b2f73cb: movq %rax, %r15 0x10b2f73ce: movq %r12, %rbx 0x10b2f73d1: testq %rbx, %rbx 0x10b2f73d4: jns 0x10b2f7430 Target 0: (saved_ansi_gcl) stopped. // Yup, it's our N, reduced by 1 again: (lldb) reg r r12 r12 = 0xa0000000002c65bb (lldb) print $r12d // Same as "print 0x02c65bb (int) $2 = 2909627 // So we came down in N from 3,000,000 to 2,909,627 // about 100,000 in a short run. Makes sense. // So let's see how much progress this loop makes in about 10 minutes. I'll // disable the breakpoint, let it run for 30 minutes, then re-enable the // breakpoint and see how much progress we made in N. (lldb) breakpoint list Current breakpoints: 1: name = 'TTL', locations = 0 (pending) // <-- we could not set that one, TTL was not a saved label in the object file. We can "breakpoint delete 1". 2: address = saved_ansi_gcl[0x000000010b2f73cb], locations = 1, resolved = 1, hit count = 20 2.1: where = saved_ansi_gcl`saved_ansi_gcl[0x000000010b2f73cb], address = 0x000000010b2f73cb, resolved, hit count = 20 // <<-- this is our loop breakpoint (lldb) breakpoint disable 2 1 breakpoints disabled. (lldb) c Process 50918 resuming // Wait for 30 minutes, make tea & drink it :) // Then we interrupt the process. We hit whatever is executing at that time inside GCL: (lldb) process interrupt Process 50918 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP frame #0: 0x000000010ab380ea libgmp.10.dylib`__gmpn_copyi + 234 libgmp.10.dylib`__gmpn_copyi: -> 0x10ab380ea <+234>: movdqa %xmm7, 0x70(%rdi) 0x10ab380ef <+239>: palignr $0x8, %xmm5, %xmm6 ; xmm6 = xmm5[8,9,10,11,12,13,14,15],xmm6[0,1,2,3,4,5,6,7] 0x10ab380f5 <+245>: movaps 0x78(%rsi), %xmm7 0x10ab380f9 <+249>: movdqa %xmm6, 0x60(%rdi) Target 0: (saved_ansi_gcl) stopped. (lldb) breakpoint enable 2 1 breakpoints enabled. // Now we run to our loop breakpoint: (lldb) c Process 50918 resuming Process 50918 stopped * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1 frame #0: 0x000000010b2f73cb saved_ansi_gcl -> 0x10b2f73cb: movq %rax, %r15 0x10b2f73ce: movq %r12, %rbx 0x10b2f73d1: testq %rbx, %rbx 0x10b2f73d4: jns 0x10b2f7430 Target 0: (saved_ansi_gcl) stopped. (lldb) print $r12d (unsigned int) $3 = 2361286 (lldb) print 2909627 - 2361286 (int) $4 = 548341 // So we mowed down N by about 550,000 in 30 minutes. 3,000,000 then // would take just shy of 3 hours. // For extra credit, you can figure out what 0xa0000000 at the top of R12 // means, how FIXNUMs are represented, and how the control flow of the // computation goes.