readme_v1.txt
=============

The assignment was to use gdb to explore some code.

I've expanded my version 0 demo.c to include more printing
of memory addresses to understand which pieces - code,
stack, heap - get put where. See memory_map.txt for that stuff.

Here I'm going to do something a bit different : try to see
how the recursive fibbo calls use the stack to store
successive frames, and where the local variables for
each function call are put.

The fibbo function is

    int fibbo(int n){
      if (n < 2) return 1;
      return fibbo(n-1) + fibbo(n-2);
    }

which recursively finds the n'th Fibonnaci number.
(See https://en.wikipedia.org/wiki/Fibonacci_number if you've
never heard of these before, though the details don't really
matter for the x86 exploration we're doing here.)

So let's look at it in the debugger, and remind ourselves
about the x86 register conventions : 

   %rax (64bit) , %eax (32bit)       return value
   %rdi (64bit) , %edi (32bit)       1st input arg
   %rsp                              stack pointer
   %rbx , %ebx                       callee saved (store on stack if used)
   %rbp , %ebp                       callee saved (store on stack if used)

Here's what I see from gdb, with some annotations.

    $ gdb ./demo
    (gdb) start
    Temporary breakpoint 1 at 0xd2f
    Starting program: /home/jupyter-jimmahoney/fall2020/systems/c/demo/demo 
    Temporary breakpoint 1, 0x0000555555554d2f in main ()

The first call to fibbo is in part2. Here it is with some annotations.

    (gdb) disass part2
    Dump of assembler code for function part2:
       0x00005555555548bd <+0>:     push   %rbx
       0x00005555555548be <+1>:     mov    $0x5,%edi                       // n = 5
       0x00005555555548c3 <+6>:     callq  0x5555555547ea <fibbo>          // rax = f(n)
       0x00005555555548c8 <+11>:    mov    %eax,%ebx
       0x00005555555548ca <+13>:    lea    0x57a(%rip),%rdi        # 0x555555554e4b
       0x00005555555548d1 <+20>:    callq  0x555555554690 <puts@plt>
       0x00005555555548d6 <+25>:    mov    %ebx,%edx
       0x00005555555548d8 <+27>:    lea    0x578(%rip),%rsi        # 0x555555554e57
       0x00005555555548df <+34>:    mov    $0x1,%edi
       0x00005555555548e4 <+39>:    mov    $0x0,%eax
       0x00005555555548e9 <+44>:    callq  0x5555555546c0 <__printf_chk@plt>
       0x00005555555548ee <+49>:    pop    %rbx
       0x00005555555548ef <+50>:    retq   

And the code for fibbo itself, also with annotations : 

    (gdb) disas fibbo
    Dump of assembler code for function fibbo:
       0x00005555555547ea <+0>:      cmp    $0x1,%edi                  // n <= 1 ?
       0x00005555555547ed <+3>:  +-  jg     0x5555555547f5 <fibbo+11>    
       0x00005555555547ef <+5>:  |   mov    $0x1,%eax                  // yes
       0x00005555555547f4 <+10>: |   retq                              //  ... so return 1
       0x00005555555547f5 <+11>: +-> push   %rbp                       // no : save old rbp
       0x00005555555547f6 <+12>:     push   %rbx                       //      save old rbx
       0x00005555555547f7 <+13>:     sub    $0x8,%rsp                  //      align stack
       0x00005555555547fb <+17>:     mov    %edi,%ebx                  //      rbx = n
       0x00005555555547fd <+19>:     lea    -0x1(%rdi),%edi            //      n' = n-1
       0x0000555555554800 <+22>:     callq  0x5555555547ea <fibbo>     //      rax = fib(n')
       0x0000555555554805 <+27>:     mov    %eax,%ebp                  //      rbp = rax  
       0x0000555555554807 <+29>:     lea    -0x2(%rbx),%edi            //      n'' = n-2
       0x000055555555480a <+32>:     callq  0x5555555547ea <fibbo>     //      rax = fib(n'')
       0x000055555555480f <+37>:     add    %ebp,%eax                  //      rax += rbp
       0x0000555555554811 <+39>:     add    $0x8,%rsp                  //      align stack
       0x0000555555554815 <+43>:     pop    %rbx                       //      restore old rbx
       0x0000555555554816 <+44>:     pop    %rbp                       //      restore old rbp
       0x0000555555554817 <+45>:     retq                              // return f(n')+f(n'')

The "sub $0x8,%rsp" line is to ensure that successive return addresses
on the stack are aligned on 16 byte boundaries; see for example
https://stackoverflow.com/questions/4175281/what-does-it-mean-to-align-the-stack .

So what happens is that the registers %rbx and %rbp are used to store
the values of n and f(n-1) before the call to calculate f(n-2).
(Don't be confused by the fact that those are sometimes named %ebx and
%ebp when refering to the integers in the lower 32 bits.)

This means that for each fibbo invocation, what's put on the stack is
(remmbering that each thing pushed onto the stack is put at a lower
address), like this :

     ... higher ...
     -- what ---                    -- set from --               -- has --
     return address (8 bytes)       callq fibbo   (in caller)    0x..4805, 480f, or 48c8
     %rbp (8 bytes)                 push %rbp     (in callee)    fib(n-1)
     %rbx (8 bytes)                 push %rbx     (in callee)    n
     blank (8 bytes)                sub $0x8,%rsp (in callee)
     ... lower ...

The return address will be a line number right after "callq <fibbo>",
from either part2 or one of the two calls within fibbo.

From the C code we can see that in part2 we calculate fibbo(5). 
And each call to fibbo(n) needs to call fibbo(n-1) and fibbo(n-2).
So that means to find fibbo(5) the calls we can expect are :

    fibbo(5)
              fibbo(4)
                            fibbo(3)
                                         fibbo(2)
                                                     fibbo(1)  => 1
                                                     fibbo(0)  => 1
                                         fibbo(1) => 1
                            fibbo(2)
                                         fibbo(1) => 1
                                         fibbo(0) => 1
              fibbo(3)
                            fibbo(2)
                                         fibbo(1) => 1
                                         fibbo(0) => 1
                            fibbo(1) => 1

... since there isn't anything in here smart enough to know that it
has calculated things like fibbo(2) before, it will need to calculate
the same result over and over again. Each layer then adds the results
of the layer before.

I'll put a breakpoint at fibbo, look at $edi (i.e. n), and continue
a few times before trying to look at the stack.

    (gdb) continue
    Continuing.
    It's another demo.c !!!
    -- part 0 --
     inputs[] is at 0x7fffffffe290 
     What is your favorite color?  ... never mind. ;) 
    -- part1 --
     before: n1 = 12, n2 = 34, n3 = 5, n4 = 0 
       address of g in swap_and_stuff is 0x7fffffffe2e0 
     after: n1 = 34, n2 = 12, n3 = 5, n4 = 483 

    Breakpoint 2, 0x00005555555547ea in fibbo ()
    (gdb) x $rdi
    0x5:	Cannot access memory at address 0x5
    (gdb) print $rdi
    $1 = 5
    (gdb) continue
    Continuing.

    Breakpoint 2, 0x00005555555547ea in fibbo ()
    (gdb) print $rdi
    $2 = 4
    (gdb) continue
    Continuing.

    Breakpoint 2, 0x00005555555547ea in fibbo ()
    (gdb) print $rdi
    $3 = 3

    Breakpoint 2, 0x00005555555547ea in fibbo ()
    (gdb) print $edi
    $5 = 2
    (gdb) continue
    Continuing.

    Breakpoint 2, 0x00005555555547ea in fibbo ()
    (gdb) print $edi
    $6 = 1

Now let's look at the stack.

    (gdb) x $rsp
    0x7fffffffe278:	0x0000555555554805

The stack has the return address, which an address after "callq fibbo"
within fiboo.

The next value higher (at a larger address) is 8 bytes above that.

    (gdb) x $rsp + 8
    0x7fffffffe280:	0x00000000000001e3

That's junk; the stack pointer was moved by 8 for alignment.

Past that is 

    (gdb) x $rsp + 16
    0x7fffffffe288:	0x0000000000000003    

And the n=2 value is currently stored in %rbx since
at the start of fibbo it hasn't yet been pushed to the stack
for storage.

   (gdb) print $rbx
   $9 = 2

We can see more of the stack with one "examine" (i.e. x)
command, but need to be careful about what the result means
... this will show us increasing memory downwards, while
pictures of the stack often show it the other way,
with higher address at the top.

    (gdb) x /12gx $rsp
    0x7fffffffe278: 0x0000555555554805      0x00000000000001e3
    0x7fffffffe288: 0x0000000000000003      0x0000555555554d90
    0x7fffffffe298: 0x0000555555554805      0x000000000000000b
    0x7fffffffe2a8: 0x0000000000000004      0x0000555555554d90
    0x7fffffffe2b8: 0x0000555555554805      0x0000000000000000
    0x7fffffffe2c8: 0x0000000000000005      0x0000555555554d90

That last command "x/12gx" means, looking at the gdb notes
at http://csapp.cs.cmu.edu/2e/docs/gdbnotes-x86-64.txt ,
"examine 12 words, each made up of 8-bytes, in hex format.

However, be clear that output is arranged like this :

    1 2         lower addresses
    3 4
    5 6         higher address
    etc

with two 8-byte (64bit) words per line, addresses increasing downward,
with lower addresses on top.

If I rearrage that as

   etc
   6
   5
   4
   3
   2
   1

I get this, in the usual stack orientation. 

		    0x0000555555554d90           junk ; don't know f(n-1) yet
    0x7fffffffe2c8: 0x0000000000000005           saved n = 5
		    0x0000000000000000           junk ; stack alignment

    0x7fffffffe2b8: 0x0000555555554805           return address
		    0x0000555555554d90           junk ; don't know f(n-1) yet
    0x7fffffffe2a8: 0x0000000000000004           saved n = 4
		    0x000000000000000b           junk ; stack alignment

    0x7fffffffe298: 0x0000555555554805           return for last fibbo invocation
		    0x0000555555554d90           caller stored f(n-1), if known
    0x7fffffffe288: 0x0000000000000003           caller value of n, saved n = 3
		    0x00000000000001e3           caller stack alignment

    0x7fffffffe278: 0x0000555555554805           return for this callee
		
Each f(n) call calculates both f(n-1) and f(n-2). During the f(n-1) calculation,
only n and the return value are saved on the stack; during the f(n-2)'s
(which haven't happened yet), both n and the f(n-1) value are saved.

So ... there you are. ;)