// Recursive definitions are very graceful, and will be extremely useful for data types
//  such as lists and trees, as we'll see next week in LISP and later even more so
//  in strongly typed functional languages such as ML, Haskell, and Rust.

// The stack frame is a miracle of separating memory footprints of individual calls
//  to the same function, which run exactly the same code. In the fact() example,
//  the magic is in the combination of the relative addressing of all locals off RBP,
//  the preamble that saves the prior RBP ("push %rbp; mov %rsp, %rbp") and the post-amble
//  that restores is ("leave" is roughly "mov %rbp, %rsp; pop %rbp", preamble in reverse.
//
// BTW: AI agents got very good at explaining CPU instruction semantics, so asking them
//  may be the quickest way to refresh your memory about what PUSH or CALL does. Try it!    
//  
// Note that "CALL fact" acts kind of like a loop: execution jumps back to the start of the
//  function. The additional stack operations such as CALL pushing the address of the next
//  instruction to come back to after CALL and RET popping that address off the stack into RIP
//  keep the data context and the code flow in sync.

// Note that the stack to store return addresses can be _separate_ from the stack where
//  local data it stored. Indeed, MacOS/Darwin kernel uses separate stacks for data and
//  return addresses! So CALL and RET use a separate stack than PUSH and POP/LEAVE.

// Also note that the naive implementation of recursive functions is wasteful: stack
//  frames can waste a lot of RAM. However, modern compilers are very good at turning
//  recursive definitions into non-recursive implementations, as we'll see later in
//  this course. 

// ============ Consider the naive factorial function =================

[sergey@thepond cs59]$ cat fact.c
#include <stdio.h>

/* a very naive recursive factorial */
unsigned int fact(unsigned int n)
{
     if( 0 == n )
          return 1;
     return n * fact(n-1);
}

int main()
{
     int i;
     for( i = 0; i < 10; i++ ){ 
          printf("%d\n", fact(i));
     }

     return 0;
}

[sergey@thepond cs59]$ fg
gdb ./fact


Dump of assembler code for function main:
   0x0000000000001164 <+0>:	push   %rbp
   0x0000000000001165 <+1>:	mov    %rsp,%rbp
   0x0000000000001168 <+4>:	sub    $0x10,%rsp
   0x000000000000116c <+8>:	movl   $0x0,-0x4(%rbp)  // <-- "i" of the loop in main()
   0x0000000000001173 <+15>:	jmp    0x119b <main+55> // unconditional jump to checking "i < 10"
   0x0000000000001175 <+17>:	mov    -0x4(%rbp),%eax  // "i" becomes the argument to fact()
   0x0000000000001178 <+20>:	mov    %eax,%edi        //   .. 
   0x000000000000117a <+22>:	call   0x1139 <fact>
   0x000000000000117f <+27>:	mov    %eax,%edx        // return value of fact(), see <+36>  
   0x0000000000001181 <+29>:	lea    0xe7c(%rip),%rax        # 0x2004  // format string 
   0x0000000000001188 <+36>:	mov    %edx,%esi   // return value of fact() is 2nd argument to printf()
   0x000000000000118a <+38>:	mov    %rax,%rdi   // format string is the 1st argument to printf()
   0x000000000000118d <+41>:	mov    $0x0,%eax   // this is a special thing with printf() and other varargs functions (look it up)
   0x0000000000001192 <+46>:	call   0x1030 <printf@plt>
   0x0000000000001197 <+51>:	addl   $0x1,-0x4(%rbp)
   0x000000000000119b <+55>:	cmpl   $0x9,-0x4(%rbp) // <-- note that "10" in the main loop becomes 9
   0x000000000000119f <+59>:	jle    0x1175 <main+17> // think of other comparison/test pairings
   0x00000000000011a1 <+61>:	mov    $0x0,%eax      // return value of main()
   0x00000000000011a6 <+66>:	leave
   0x00000000000011a7 <+67>:	ret
End of assembler dump.

// And now for fact() itself:

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000000000001139 <+0>:	push   %rbp
   0x000000000000113a <+1>:	mov    %rsp,%rbp
   0x000000000000113d <+4>:	sub    $0x10,%rsp
   0x0000000000001141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000000000001144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000000000001148 <+15>:	jne    0x1151 <fact+24>
   0x000000000000114a <+17>:	mov    $0x1,%eax
   0x000000000000114f <+22>:	jmp    0x1162 <fact+41>
   0x0000000000001151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000000000001154 <+27>:	sub    $0x1,%eax
   0x0000000000001157 <+30>:	mov    %eax,%edi
   0x0000000000001159 <+32>:	call   0x1139 <fact>
   0x000000000000115e <+37>:	imul   -0x4(%rbp),%eax
   0x0000000000001162 <+41>:	leave
   0x0000000000001163 <+42>:	ret
^C

// At this point I decided that we just want to see fact(6), so I rebuilt fact.c:

[sergey@thepond cs59]$ cat fact.c
#include <stdio.h>

/* a very naive recursive factorial */
unsigned int fact(unsigned int n)
{
     if( 0 == n )
          return 1;
     return n * fact(n-1);
}

int main()
{
     printf("%d\n", fact(6));
     return 0;
}

[sergey@thepond cs59]$ gcc -Wall -o fact fact.c

[sergey@thepond cs59]$ gdb ./fact
GNU gdb (GDB) 17.2
Copyright (C) 2025 Free Software Foundation, Inc.
[..skipped..]
(No debugging symbols found in ./fact)

(gdb) disas main
Dump of assembler code for function main:
   0x0000000000001164 <+0>:	push   %rbp
   0x0000000000001165 <+1>:	mov    %rsp,%rbp
   0x0000000000001168 <+4>:	mov    $0x6,%edi     // just do fact(6)
   0x000000000000116d <+9>:	call   0x1139 <fact>
   0x0000000000001172 <+14>:	mov    %eax,%edx
   0x0000000000001174 <+16>:	lea    0xe89(%rip),%rax        # 0x2004  // see what this is!
   0x000000000000117b <+23>:	mov    %edx,%esi
   0x000000000000117d <+25>:	mov    %rax,%rdi
   0x0000000000001180 <+28>:	mov    $0x0,%eax
   0x0000000000001185 <+33>:	call   0x1030 <printf@plt>
   0x000000000000118a <+38>:	mov    $0x0,%eax
   0x000000000000118f <+43>:	pop    %rbp
   0x0000000000001190 <+44>:	ret
End of assembler dump.

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000000000001139 <+0>:	push   %rbp
   0x000000000000113a <+1>:	mov    %rsp,%rbp
   0x000000000000113d <+4>:	sub    $0x10,%rsp
   0x0000000000001141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000000000001144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000000000001148 <+15>:	jne    0x1151 <fact+24>
   0x000000000000114a <+17>:	mov    $0x1,%eax
   0x000000000000114f <+22>:	jmp    0x1162 <fact+41>
   0x0000000000001151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000000000001154 <+27>:	sub    $0x1,%eax
   0x0000000000001157 <+30>:	mov    %eax,%edi
   0x0000000000001159 <+32>:	call   0x1139 <fact>
   0x000000000000115e <+37>:	imul   -0x4(%rbp),%eax
   0x0000000000001162 <+41>:	leave
   0x0000000000001163 <+42>:	ret
End of assembler dump.

(gdb) b fact
Breakpoint 1 at 0x1141

(gdb) c
The program is not being run.  // Oops. Can't continue if not running :)

(gdb) r
Starting program: /home/sergey/cs59/fact 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x0000555555555141 in fact ()
(gdb) i r $edi
edi            0x6                 6          // 1st and only argument passed to fact(), in EDI

// Let's see the stack:

(gdb) x/10x $rsp
0x7fffffffea40:	0x00000000	0x00000000	0x00000000	0x00000000
0x7fffffffea50:	0xffffea60	0x00007fff	0x55555172	0x00005555
0x7fffffffea60:	0xffffeb10	0x00007fff

// Oops, I wanted to see the stack at 64-bit word/pointer granularity, not 32-bit as above

(gdb) x/10gx $rsp
0x7fffffffea40:	0x0000000000000000	0x0000000000000000   // this is our new frame
0x7fffffffea50:	0x00007fffffffea60	0x0000555555555172   //<<-- behold, return address -----+
0x7fffffffea60:	0x00007fffffffeb10	0x00007ffff7c27781                                      | 
0x7fffffffea70:	0x00007ffff7fe0ce0	0x00007fffffffeb98                                      |
0x7fffffffea80:	0x00000001f7fbe000	0x0000555555555164                                      |
                                                                                                |
(gdb) disas main                                                                                |
Dump of assembler code for function main:                                                       |
   0x0000555555555164 <+0>:	push   %rbp                                                     | 
   0x0000555555555165 <+1>:	mov    %rsp,%rbp                                                |
   0x0000555555555168 <+4>:	mov    $0x6,%edi                                                |
   0x000055555555516d <+9>:	call   0x555555555139 <fact>                                    |
   0x0000555555555172 <+14>:	mov    %eax,%edx    // <-- return back here just after fact() --+
   0x0000555555555174 <+16>:	lea    0xe89(%rip),%rax        # 0x555555556004
   0x000055555555517b <+23>:	mov    %edx,%esi
   0x000055555555517d <+25>:	mov    %rax,%rdi
   0x0000555555555180 <+28>:	mov    $0x0,%eax
   0x0000555555555185 <+33>:	call   0x555555555030 <printf@plt>
   0x000055555555518a <+38>:	mov    $0x0,%eax
   0x000055555555518f <+43>:	pop    %rbp
   0x0000555555555190 <+44>:	ret
End of assembler dump.

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
=> 0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)       // save our argument "n" into our frame
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)       //  is it 0?
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>  
   0x000055555555514a <+17>:	mov    $0x1,%eax             //  it was 0, return 0! = 1, base case
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax       // make me (n-1)  
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi             // .. pass n-1 as 1st argument to fact()!
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>  // this pushes next address on the stack
                                                              //   and jumps back to the top of fact()
   
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax        // <--- remember this address
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

// So this is our first frame, before "n" is saved into it:

(gdb) x/10gx $rsp
0x7fffffffea40:	0x0000000000000000	0x0000000000000000
0x7fffffffea50:	0x00007fffffffea60	0x0000555555555172
0x7fffffffea60:	0x00007fffffffeb10	0x00007ffff7c27781
0x7fffffffea70:	0x00007ffff7fe0ce0	0x00007fffffffeb98
0x7fffffffea80:	0x00000001f7fbe000	0x0000555555555164
(gdb) c
Continuing.

// .. and now there is another frame

Breakpoint 1, 0x0000555555555141 in fact ()
(gdb) c
Continuing.

// .. and another 

Breakpoint 1, 0x0000555555555141 in fact ()

// .. and another 

(gdb) c
Continuing.
Breakpoint 1, 0x0000555555555141 in fact ()

// Let's see these frames!

(gdb) x/16gx $rsp
0x7fffffffe9e0:	0x0000000000000000	0x0000000000000000
0x7fffffffe9f0:	0x00007fffffffea10	0x000055555555515e     // note this return address to imult
0x7fffffffea00:	0x0000000000000000	0x0000000400000000  // frame with n=4 saved
0x7fffffffea10:	0x00007fffffffea30	0x000055555555515e     // same return address
0x7fffffffea20:	0x0000000000000000	0x0000000500000000  // frame with n=5 saved 
0x7fffffffea30:	0x00007fffffffea50	0x000055555555515e     // same imult return address 
0x7fffffffea40:	0x0000000000000000	0x0000000600000000  // frame with n=6
0x7fffffffea50:	0x00007fffffffea60	0x0000555555555172

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
=> 0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>
   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax    // the function will keep returning here
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

(gdb) c
Continuing.
Breakpoint 1, 0x0000555555555141 in fact ()

// another frame (note that it's not 0s in the place on "n" this time):

(gdb) x/16gx $rsp
0x7fffffffe9c0:	0x0000000000000000	0x00007ffff7fbc000
0x7fffffffe9d0:	0x00007fffffffe9f0	0x000055555555515e
0x7fffffffe9e0:	0x0000000000000000	0x0000000300000000
0x7fffffffe9f0:	0x00007fffffffea10	0x000055555555515e
0x7fffffffea00:	0x0000000000000000	0x0000000400000000
0x7fffffffea10:	0x00007fffffffea30	0x000055555555515e
0x7fffffffea20:	0x0000000000000000	0x0000000500000000
0x7fffffffea30:	0x00007fffffffea50	0x000055555555515e

// There will be a few more, but we'll continue through them. We'll hit n=0 and
//  will then start hitting IMUL and then LEAVE and RET.

// We'll keep returning to IMUL as we unwind the stack once we reach n=0.
//   Let's break on this address and see EAX 

(gdb) b *0x000055555555515e
Breakpoint 2 at 0x55555555515e

(gdb) c
Continuing.

Breakpoint 1, 0x0000555555555141 in fact ()

(gdb) c
Continuing.

Breakpoint 1, 0x0000555555555141 in fact ()
(gdb) c
Continuing.

// And now we reached n=0. We haven't reached IMUL before now, but now we'll hit it every time:

Breakpoint 2, 0x000055555555515e in fact ()

(gdb) print $eax
$1 = 1               // that's 0! == 1

(gdb) c
Continuing.

Breakpoint 2, 0x000055555555515e in fact ()

(gdb) print $eax
$2 = 1               // that's 1! = 1 * 0! = 1 

(gdb) c
Continuing.

Breakpoint 2, 0x000055555555515e in fact ()

(gdb) print $eax
$3 = 2               // that's 2! = 2

(gdb) c
Continuing.

Breakpoint 2, 0x000055555555515e in fact ()
(gdb) print $eax

$4 = 6              // 3! = 6

(gdb) c
Continuing.

Breakpoint 2, 0x000055555555515e in fact ()

(gdb) print $eax
$5 = 24

(gdb) disas
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp
   0x000055555555513a <+1>:	mov    %rsp,%rbp
   0x000055555555513d <+4>:	sub    $0x10,%rsp
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>
   0x000055555555514a <+17>:	mov    $0x1,%eax
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax
   0x0000555555555154 <+27>:	sub    $0x1,%eax
   0x0000555555555157 <+30>:	mov    %eax,%edi
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>
=> 0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax  // <-- Yup, we keep returning here
   0x0000555555555162 <+41>:	leave
   0x0000555555555163 <+42>:	ret
End of assembler dump.

// Our stack frame now:, n=5

(gdb) x/16gx $rsp
0x7fffffffea20:	0x0000000000000000	0x0000000500000000
0x7fffffffea30:	0x00007fffffffea50	0x000055555555515e
0x7fffffffea40:	0x0000000000000000	0x0000000600000000
0x7fffffffea50:	0x00007fffffffea60	0x0000555555555172
0x7fffffffea60:	0x00007fffffffeb10	0x00007ffff7c27781
0x7fffffffea70:	0x00007ffff7fe0ce0	0x00007fffffffeb98
0x7fffffffea80:	0x00000001f7fbe000	0x0000555555555164
0x7fffffffea90:	0x00007fffffffead0	0x00007ffff7fdf2e0

// ... prior stack frames are still in RAM, we just don't point to them anymore

(gdb) x/16gx $rsp-64
0x7fffffffe9e0:	0x0000000000000000	0x0000000300000000
0x7fffffffe9f0:	0x00007fffffffea10	0x000055555555515e
0x7fffffffea00:	0x0000000000000000	0x0000000400000000
0x7fffffffea10:	0x00007fffffffea30	0x000055555555515e
0x7fffffffea20:	0x0000000000000000	0x0000000500000000
0x7fffffffea30:	0x00007fffffffea50	0x000055555555515e
0x7fffffffea40:	0x0000000000000000	0x0000000600000000
0x7fffffffea50:	0x00007fffffffea60	0x0000555555555172

(gdb) c
Continuing.

Breakpoint 2, 0x000055555555515e in fact ()

(gdb) print $eax
$6 = 120

(gdb) c
Continuing.
720
[Inferior 1 (process 242027) exited normally]

//.. and we are done ("return 0" out of main() is "existed normally" as per Unix convention)

// We passed through this loop 7 times, every time pushing a new stack frame thanks to CALL
//   and the preamble of the first three instructions PUSH-MOV-SUB:

(gdb) disas fact
Dump of assembler code for function fact:
   0x0000555555555139 <+0>:	push   %rbp      <-----------------------+
   0x000055555555513a <+1>:	mov    %rsp,%rbp                         |
   0x000055555555513d <+4>:	sub    $0x10,%rsp                        |
   0x0000555555555141 <+8>:	mov    %edi,-0x4(%rbp)                   |
   0x0000555555555144 <+11>:	cmpl   $0x0,-0x4(%rbp)                   |
   0x0000555555555148 <+15>:	jne    0x555555555151 <fact+24>          |
   0x000055555555514a <+17>:	mov    $0x1,%eax                         |
   0x000055555555514f <+22>:	jmp    0x555555555162 <fact+41>          |
   0x0000555555555151 <+24>:	mov    -0x4(%rbp),%eax                   |
   0x0000555555555154 <+27>:	sub    $0x1,%eax                         |
   0x0000555555555157 <+30>:	mov    %eax,%edi                         |
   0x0000555555555159 <+32>:	call   0x555555555139 <fact>     --------+

// .. and then unwound the frame sequence by looping through this 7 times:

   0x000055555555515e <+37>:	imul   -0x4(%rbp),%eax   <---------------+ 
   0x0000555555555162 <+41>:	leave                                    |
   0x0000555555555163 <+42>:	ret                              --------+
End of assembler dump.

=====================================================================================

// And now for a darker side of stack frames!

// Consider the following program:

[sergey@thepond ~]$ cat gets2.c
#include <stdio.h>
char *gets(char *s);   // Needed because gets() is so bad, it's not included in Alpine's
                       //  standard libc headers. Only fgets() is present, check with gcc -E  
int main()
{
  struct inps {
    char c[10];   // array of 10 chars
    int cnt;      // 4 byte integer
  } inp;          // how long is this struct? _At least_ 14 bytes: struct members aren't
                  //   guaranteed to be adjacent, unless  __attribute__((packed))  is added. 
  int i;
  
  inp.cnt = 10;
  gets( inp.c);   

  i = inp.cnt;
  
  while( i >= 0 ){
    i = i - 1;
    puts(inp.c);
  }
  return 42;
}

// If you try to compile it without the explicit declaration of gets(), you'll get an error:
//   "gets? What gets? You mean fgets, right?"

[sergey@thepond ~]$ gcc -Wall -o gets2 gets2.c
gets2.c: In function 'main':
gets2.c:14:3: error: implicit declaration of function 'gets'; did you mean 'fgets'? [-Wimplicit-function-declaration]
   14 |   gets( inp.c);
      |   ^~~~
      |   fgets

[sergey@thepond ~]$ gcc -E gets2.c | grep gets | grep -v ^#
extern char *fgets (char *__restrict __s, int __n, FILE *__restrict __stream)
... and my own uses of it ... 

// Also check out the manual page, "man gets". It tells you to never use this function! Why?
//  The linker will warn you in its turn, too:

[sergey@thepond ~]$ gcc -Wall -o gets2 gets2.c
/usr/bin/ld: /tmp/ccqnF9S4.o: in function `main':
gets2.c:(.text+0x26): warning: the `gets' function is dangerous and should not be used.

// OK, we finally managed to compile it. Let's run it:

//  gets reads characters from Unix's standard input and copies them into memory,
//    starting at the address provided, until it encounters the character 0x00 or
//    the end of the input stream. Gets() writes 0x00 at the end of the copied string.

[sergey@thepond ~]$ ./gets2 
hello    // <<-- we type this
hello    // it gets echoed a bunch of times
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello

// Let's use echo and the Unix pipe "|" to control the input:  

[sergey@thepond ~]$ echo "hello" | ./gets2
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello

// We can pipe the output of the program to wc to count lines:

[sergey@thepond ~]$ echo "hello" | ./gets2 | wc
     11      11      66

// So I prepared some inputs:

[sergey@thepond ~]$ cat A1
A10   A100  A11   A12   A13   A14   A15   A16   A17   

[sergey@thepond ~]$ cat A11 
AAAAAAAAAAA

[sergey@thepond ~]$ wc A11  
 0  1 11 A11

// Note that there is no final newline here, just pure 'A's
//   (xxd shows the exact bytes in a file)

[sergey@thepond ~]$ xxd A10   
00000000: 4141 4141 4141 4141 4141                 AAAAAAAAAA

// Let's feed ten 'A's into the program. That will result in gets() writing 11 chars,
//   counting the final 0x00 (a.k.a. '\0')

[sergey@thepond ~]$ cat A10 | ./gets2 
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA

// Seems to be fine...

[sergey@thepond ~]$ cat A11 | ./gets2 | wc
     11      11     132

// Let's write 11 'A's. Gets() will write 11 'A's and a '\0'

[sergey@thepond ~]$ cat A11 | ./gets2     
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA

// Seems fine again... But what is this? 

[sergey@thepond ~]$ cat A12 | ./gets2 
AAAAAAAAAAAA

// Just one line instead of 11! Mystery. Shall we continue? 

[sergey@thepond ~]$ cat A13 | ./gets2 
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA   ///  keep scrolling :)
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA

// That's 66 lines, reproducibly.

[sergey@thepond ~]$ cat A13 | ./gets2 | wc
     66      66     924

// What gives? Let's see more:

[sergey@thepond ~]$ cat A14 | ./gets2 | wc
  16706   16706  250590

[sergey@thepond ~]$ cat A15 | ./gets2 | wc
4276546 4276546 68424736

// What if we take 100 'A's?

[sergey@thepond ~]$ wc A100 
  0   1 100 A100

[sergey@thepond ~]$ cat A100 | ./gets2 > /dev/null
*** stack smashing detected ***: terminated
Aborted                    (core dumped) 

// At some point, the mystery gets to be too much for the standard library :)
// Let's see what's going on. 

[sergey@thepond ~]$ gdb ./gets2
GNU gdb (GDB) 16.3
(No debugging symbols found in ./gets2)

(gdb) b main
Breakpoint 1 at 0x115d

(gdb) r
Starting program: /home/sergey/gets2 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x000055555555515d in main ()

(gdb) disas
Dump of assembler code for function main:
   0x0000555555555159 <+0>:	push   %rbp
   0x000055555555515a <+1>:	mov    %rsp,%rbp
=> 0x000055555555515d <+4>:	sub    $0x30,%rsp

   // You can skip the following on the first reading

   0x0000555555555161 <+8>:	mov    %fs:0x28,%rax   // this gets a value from "thread-local storage",
     // an area that a Unix thread doesn't share with others, unlike the rest of address space.
     // This uses an x86-specific gimmick of segment selectors that are a part of the thread context,
     // context-switched together with registers. If this doesn't sound familiar, just think of this as
     // a per-thread secret value squirreled away somewhere safe away from the stack
   0x000055555555516a <+17>:	mov    %rax,-0x8(%rbp)  // ...and this value is saved at RBP-8.
                                                        //  it will serve as a "canary" for the stack.
							//  Read on :) 

   0x000055555555516e <+21>:	xor    %eax,%eax
   0x0000555555555170 <+23>:	movl   $0xa,-0x14(%rbp)      // inp.cnt = 10
   0x0000555555555177 <+30>:	lea    -0x20(%rbp),%rax      // the address of inp.c 
   0x000055555555517b <+34>:	mov    %rax,%rdi             //   .. will be the argument to gets()
   0x000055555555517e <+37>:	call   0x555555555050 <gets@plt>
   0x0000555555555183 <+42>:	mov    -0x14(%rbp),%eax      // now we read inp.cnt back
   0x0000555555555186 <+45>:	mov    %eax,-0x24(%rbp)      //   ... into "i"
   0x0000555555555189 <+48>:	jmp    0x55555555519b <main+66>  // typical trick for loops
                                                                 //  that run at least once
   0x000055555555518b <+50>:	subl   $0x1,-0x24(%rbp)          //  i = i-1
   0x000055555555518f <+54>:	lea    -0x20(%rbp),%rax      // address of inp.c     
   0x0000555555555193 <+58>:	mov    %rax,%rdi             //   .. will be passed to puts() 
   0x0000555555555196 <+61>:	call   0x555555555030 <puts@plt>   
   0x000055555555519b <+66>:	cmpl   $0x0,-0x24(%rbp)          // compare "i" with 0
   0x000055555555519f <+70>:	jns    0x55555555518b <main+50>  //  if not negative, jump back
   0x00005555555551a1 <+72>:	mov    $0x2a,%eax
   0x00005555555551a6 <+77>:	mov    -0x8(%rbp),%rdx       // load the canary from the stack
   0x00005555555551aa <+81>:	sub    %fs:0x28,%rdx         //  is it the same as the secret value?
   0x00005555555551b3 <+90>:	je     0x5555555551ba <main+97>               //  if so, return
   0x00005555555551b5 <+92>:	call   0x555555555040 <__stack_chk_fail@plt>  //  if not, signal trouble
   0x00005555555551ba <+97>:	leave
   0x00005555555551bb <+98>:	ret
End of assembler dump.

// GDB allows us to run the program with the prepared input from a file

(gdb) r < A12
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/sergey/gets2 < A12
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x000055555555515d in main ()
(gdb) c
Continuing.
AAAAAAAAAAAA
[Inferior 1 (process 501913) exited with code 052]

// What we want is to watch when inp.cnt gets overwritten by gets().
//  So we'll break just after gets():

(gdb) b *0x0000555555555183        // just after gets() call 
Breakpoint 2 at 0x555555555183

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555183 in main ()

(gdb) x/10xg $rsp
0x7fffffffea90:	0x0000000000000000	0x0000000000000000
0x7fffffffeaa0:	0x4141414141414141	0x0000000a00004141   // <<-- inp struct 
0x7fffffffeab0:	0x0000000000000000	0x492cc7f105989500
0x7fffffffeac0:	0x00007fffffffeb60	0x00007ffff7c27675
0x7fffffffead0:	0x00007ffff7fc2000	0x00007fffffffebe8

// More granular:

(gdb) x/16xb $rbp-0x20    // 0x7fffffffeaa0
0x7fffffffeaa0:	0x41	0x41	0x41	0x41	0x41	0x41	0x41	0x41  <<--  10-byte buffer inp.c
0x7fffffffeaa8:	0x41	0x41	0x00	0x00	0x0a	0x00	0x00	0x00
                --------->>|    ^^^^^^^^^^^^    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                2 slack bytes            int inp.cnt 

// Note that the actual length of struct inp as allocated is 16 bytes, not 10. There are 2 unused
//  "slack" bytes between the 10 byte buffer "c" and the integer "cnt", likely for nicer alignment.

(gdb) c
Continuing.
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA

// Another run, with 'A'x11 times

(gdb) r < A11
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/sergey/gets2 < A11
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x000055555555515d in main ()

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555183 in main ()

(gdb) disas
Dump of assembler code for function main:
   0x0000555555555159 <+0>:	push   %rbp
   0x000055555555515a <+1>:	mov    %rsp,%rbp
   0x000055555555515d <+4>:	sub    $0x30,%rsp
   0x0000555555555161 <+8>:	mov    %fs:0x28,%rax
   0x000055555555516a <+17>:	mov    %rax,-0x8(%rbp)
   0x000055555555516e <+21>:	xor    %eax,%eax
   0x0000555555555170 <+23>:	movl   $0xa,-0x14(%rbp)
   0x0000555555555177 <+30>:	lea    -0x20(%rbp),%rax
   0x000055555555517b <+34>:	mov    %rax,%rdi
   0x000055555555517e <+37>:	call   0x555555555050 <gets@plt>
=> 0x0000555555555183 <+42>:	mov    -0x14(%rbp),%eax
   0x0000555555555186 <+45>:	mov    %eax,-0x24(%rbp)
   0x0000555555555189 <+48>:	jmp    0x55555555519b <main+66>
   0x000055555555518b <+50>:	subl   $0x1,-0x24(%rbp)
   0x000055555555518f <+54>:	lea    -0x20(%rbp),%rax
   0x0000555555555193 <+58>:	mov    %rax,%rdi
   0x0000555555555196 <+61>:	call   0x555555555030 <puts@plt>
   0x000055555555519b <+66>:	cmpl   $0x0,-0x24(%rbp)
   0x000055555555519f <+70>:	jns    0x55555555518b <main+50>
   0x00005555555551a1 <+72>:	mov    $0x2a,%eax
   0x00005555555551a6 <+77>:	mov    -0x8(%rbp),%rdx
   0x00005555555551aa <+81>:	sub    %fs:0x28,%rdx
   0x00005555555551b3 <+90>:	je     0x5555555551ba <main+97>
   0x00005555555551b5 <+92>:	call   0x555555555040 <__stack_chk_fail@plt>
   0x00005555555551ba <+97>:	leave
   0x00005555555551bb <+98>:	ret
End of assembler dump.

(gdb) x/16xb $rbp-0x20  // 0x7fffffffeaa0 , the start of inp and inp's char c[10] buffer 
0x7fffffffeaa0:	0x41	0x41	0x41	0x41	0x41	0x41	0x41	0x41
0x7fffffffeaa8:	0x41	0x41	0x41	0x00	0x0a	0x00	0x00	0x00
                                ^^^^^^^^^^^^ cutting into slack bytes now

// But not enough to overwrite the inp.cnt integer yet.

(gdb) c
Continuing.
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA


(gdb) r < A12
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/sergey/gets2 < A12
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x000055555555515d in main ()

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555183 in main ()

(gdb) x/16xb $rbp-0x20      // 0x7fffffffeaa0
0x7fffffffeaa0:	0x41	0x41	0x41	0x41	0x41	0x41	0x41	0x41
0x7fffffffeaa8:	0x41	0x41	0x41	0x41	0x00	0x00	0x00	0x00
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
						   cnt is now overwritten,
						   its lowest byte is now 0 

// Now we see the exact mechanism of the mystery. It's a combination of
//  low-endian integer representation and gets() writing past the intended
//  end of inp.c[10]

(gdb) r < A13                 
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/sergey/gets2 < A13
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x000055555555515d in main ()

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555183 in main ()

(gdb) x/16xb $rbp-0x20
0x7fffffffeaa0:	0x41	0x41	0x41	0x41	0x41	0x41	0x41	0x41
0x7fffffffeaa8:	0x41	0x41	0x41	0x41	0x41	0x00	0x00	0x00
                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

// This explains 66 repetitions of the input string 

(gdb) r < A14
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/sergey/gets2 < A14
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Breakpoint 1, 0x000055555555515d in main ()

(gdb) c
Continuing.

Breakpoint 2, 0x0000555555555183 in main ()

(gdb) x/16xb $rbp-0x20
0x7fffffffeaa0:	0x41	0x41	0x41	0x41	0x41	0x41	0x41	0x41
0x7fffffffeaa8:	0x41	0x41	0x41	0x41	0x41	0x41	0x00	0x00
                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// ... and this explains 16705 

// Mystery solved. Note that none of these goes far enough to overwrite the
//  canary at RBP-8. Only 'A'x100 does that in our example.

// The stack frame canary scheme protects the saved RBP and the return address,
//   but serious violations of the intended program workflow can happen before
//   this scheme triggers (if at all). This is the essence of exploitation (in this case,
//     memory corruption-based exploitation).

// So the darkest secret of the stack frame is that it's mostly imaginary. It's just memory,
//   and there's almost nothing that enforces our intended uses of its bytes and offsets
//   at the CPU instruction level. _Any compiled code allows many many executions that
//   were never meant by the original source code and yet are repeatable and stable._

// Designing languages, compilers, and runtime systems that are better at enforcing
//  programmer's intent without uneconomical cost and performance burdens remains
//  a wide-open research question.

// It took about 30 years of developing various mathematical ideas to get to the point
//   that the code is simultaneously fast and a lot more expressive of intent. This
//   is the essence of PL as a field.