Rubric for CS 2505 Fall 2019   GDB
-------------------------------------------------------------------------------

1.  [45 points] The file q1.c contains a short main() function, two helper
    functions, and finds real roots of quadratic equations.  Compile q1.c with
    the following command:

         gcc -o q1 -std=c11 -O0 -Wall -W -ggdb3 q1.c

    Now we are going to explore some of the features of gdb.

    a) Copy the last five lines of terminal output that are produced when you
       run q1 as follows:

        CentOS> q1 0.05 3.4 5.7 3.0

       ANSWER:

        3.995             20.131      20.081
        3.996             20.134      20.085
        3.997             20.138      20.089
        3.998             20.142      20.092
        3.999             20.146      20.096


    b) Start gdb on q1.  Set a breakpoint on main(), and  another breakpoint on
       line 57.  Use the gdb command info break to display the breakpoints you
       just set; copy those commands and output.

       ANSWER:

      (gdb) break main
      Breakpoint 1 at 0x4005bc: file q1.c, line 43.
      (gdb) break q1.c:57
      Breakpoint 2 at 0x400660: file q1.c, line 57.
      (gdb) info break
      Num     Type           Disp Enb Address            What
      1       breakpoint     keep y   0x00000000004005bc in main at q1.c:43
      2       breakpoint     keep y   0x0000000000400660 in main at q1.c:57


    c) Now, start the program with the parameters given in part a), but
       redirect the program's output into a file named q1output.txt.  The
       program should pause at line 43.  Use the gdb command continue to resume
       execution, which should now pause at the second breakpoint at line 57.
       Copy those commands and output. 

       ANSWER:

      (gdb) run 0.05 3.4 5.7 3.0 > q1output.txt
      Starting program: /home/wmcquain/2505/c03/q1/q1 0.05 3.4 5.7 3.0 > q1output.txt

      Breakpoint 1, main (argc=5, argv=0x7fffffffdfd8) at q1.c:43
      43    if ( argc != 5 ) {
      Missing separate debuginfos, use: debuginfo-install glibc-2.17-222.el7.x86_64
      (gdb) continue
      Continuing.

      Breakpoint 2, main (argc=5, argv=0x7fffffffdfd8) at q1.c:57
      57    if ( a == 0.0 ) {


    d) Now, use the info locals command to display the values of local
       variables.  Copy those commands and output.

       ANSWER:

      (gdb) info locals
      a = 0.050000000000000003
      b = 3.3999999999999999
      c = 5.7000000000000002
      x = 3
      h = 0


    Most of the local variables were initialized from the command-line
    parameters used when you started q1.  You will probably notice that the
    values of some, or all, of the local variables are not exactly what you
    expected.  This is a side-effect of the inherent inaccuracies of working
    with the floating-point types.

    e) Use the command next, several times, until gdb displays line 69.  Be
       careful here, we do not want to execute line 69 yet.  Now, use the step
       command to step into the call to the function extrapolate().  Note that
       gdb shows the values of the parameters that were passed to the function.
       gdb should now be displaying line 108 of the source code.  Copy those
       commands and output.

       ANSWER:

      (gdb) next
      63    double h = 0.0;
      (gdb) next
      66    for (int i = 0; i < stepLimit; i++) {
      (gdb) next
      69       double approximation = extrapolate(a, b, c, x, h);
      (gdb) step
      extrapolate (a=0.050000000000000003, b=3.3999999999999999, c=5.7000000000000002, x=3, h=0)
          at q1.c:108
      108      double slope = funcPrime(a, b, c, x + h);


    f) Now use the command next to execute lines 108, 109 and 110, which set
       the local variables declared in the function extrapolate(). Use the
       command info locals again, and note this does not display the values of
       the parameters.  Copy those commands and output.

       ANSWER:

      (gdb) next
      109      double vchange = h * slope;
      (gdb) next
      110      double estimate = func(a, b, c, x) + vchange;
      (gdb) next
      111      return estimate;
      (gdb) info locals
      slope = 3.7000000000000002
      vchange = 0
      estimate = 16.349999999999998


    g) Use the command info args to display the values of the parameters passed
       to extrapolate().  Copy those commands and output.

       ANSWER:

      (gdb) info args
      a = 0.050000000000000003
      b = 3.3999999999999999
      c = 5.7000000000000002
      x = 3
      h = 0


    h) Use the command next, several times, until gdb displays line 75.  Be
       careful here, we do not want to execute line 75 yet.  Use the print
       command to display the value of the variable funcval.  Copy those
       commands and output.

       ANSWER:

      (gdb) next
      112   }
      (gdb) next
      main (argc=5, argv=0x7fffffffdfd8) at q1.c:72
      72       double funcval = func(a, b, c, x + h);
      (gdb) next
      75       writeExtrapolation(x + h, approximation, funcval);
      (gdb) print funcval
      $1 = 16.349999999999998


    i) Use the command next, several times, until gdb displays line 66.  Be
       careful here, we do not want to execute line 66 yet.  Use the print
       command to display the value of the variable h.  Copy those commands
       and output.

       ANSWER:

      (gdb) next
      78       h = h + stepSize;
      (gdb) next
      66    for (int i = 0; i < stepLimit; i++) {
      (gdb) print h
      $2 = 0.001


    j) Use the command next until gdb displays line 69 again.  Be careful here,
       we do not want to execute line 69 yet.  Now, step into the call to
       extrapolate(), and then step into the call to funcprime().  Execute the
       command backtrace.  This shows the chain of function calls that got you
       to this point.  Copy those commands and output.

       ANSWER:

      (gdb) next
      69       double approximation = extrapolate(a, b, c, x, h);
      (gdb) step
      extrapolate (a=0.050000000000000003, b=3.3999999999999999, c=5.7000000000000002, x=3, h=0.001)
          at q1.c:108
      108      double slope = funcPrime(a, b, c, x + h);
      (gdb) step
      funcPrime (a=0.050000000000000003, b=3.3999999999999999, c=5.7000000000000002, 
          x=3.0009999999999999) at q1.c:98
      98    double slopeval = 2.0 * a;
      (gdb) backtrace
      #0  funcPrime (a=0.050000000000000003, b=3.3999999999999999, c=5.7000000000000002, 
          x=3.0009999999999999) at q1.c:98
      #1  0x000000000040088c in extrapolate (a=0.050000000000000003, b=3.3999999999999999, 
          c=5.7000000000000002, x=3, h=0.001) at q1.c:108
      #2  0x00000000004006e5 in main (argc=5, argv=0x7fffffffdfd8) at q1.c:69


    What you are seeing here is a simplified view of the runtime stack.  Each
    time a function is called, the program creates an object called a stack
    frame; the stack frame is used to store information about local variables
    in the function, as well as other information (but not the code for the
    function).  We will be studying the runtime stack in detail later in the
    course.

    For now, note that you see there are three frames on the stack, since we
    got here by starting the function main(), which has called the function
    extrapolate(), which has called the function funcprime().


    k) Use the command info frame 0, which will display information about frame
       0 on the stack.  This is the "top" frame on the stack, which belongs to
       the last function called, funcprime().  Copy those commands and output.

       ANSWER:

      (gdb) info frame 0
      Stack frame at 0x7fffffffde30:
       rip = 0x400800 in funcPrime (q1.c:98); saved rip 0x40088c
       called by frame at 0x7fffffffde90
       source language c.
       Arglist at 0x7fffffffde20, args: a=0.050000000000000003, b=3.3999999999999999, 
          c=5.7000000000000002, x=3.0009999999999999
       Locals at 0x7fffffffde20, Previous frame's sp is 0x7fffffffde30
       Saved registers:
        rbp at 0x7fffffffde20, rip at 0x7fffffffde28


    What you are seeing here is a simplified view of the frame for funcprime().
    There's not much interesting information here (yet), but you should notice
    the values of the parameters (args).


    l) Just to be complete, use the commands info frame 1 and info frame 2 to
       display information about the frames for extrapolate() and main(),
       respectively.  Copy those commands and output.

       ANSWER:

      (gdb) info frame 1
      Stack frame at 0x7fffffffde90:
       rip = 0x40088c in extrapolate (q1.c:108); saved rip 0x4006e5
       called by frame at 0x7fffffffdf00, caller of frame at 0x7fffffffde30
       source language c.
       Arglist at 0x7fffffffde80, args: a=0.050000000000000003, b=3.3999999999999999, 
          c=5.7000000000000002, x=3, h=0.001
       Locals at 0x7fffffffde80, Previous frame's sp is 0x7fffffffde90
       Saved registers:
        rbp at 0x7fffffffde80, rip at 0x7fffffffde88
      (gdb) info frame 2
      Stack frame at 0x7fffffffdf00:
       rip = 0x4006e5 in main (q1.c:69); saved rip 0x7ffff7a30445
       caller of frame at 0x7fffffffde90
       source language c.
       Arglist at 0x7fffffffdef0, args: argc=5, argv=0x7fffffffdfd8
       Locals at 0x7fffffffdef0, Previous frame's sp is 0x7fffffffdf00
       Saved registers:
        rbp at 0x7fffffffdef0, rip at 0x7fffffffdef8


    m) Repeat the command next until gdb displays line 78 again.  Now, set a
       conditional breakpoint to pause execution at line 75 when the variable i
       reaches the value 250.  Use the command info break again to show the
       current breakpoints.  Copy those commands and output.

       ANSWER:

      (gdb) next
      99    slopeval = slopeval * x + b;
      (gdb) next
      100      return slopeval;
      (gdb) next
      101   }
      (gdb) next
      extrapolate (a=0.050000000000000003, b=3.3999999999999999, c=5.7000000000000002, x=3, h=0.001)
          at q1.c:109
      109      double vchange = h * slope;
      (gdb) next
      110      double estimate = func(a, b, c, x) + vchange;
      (gdb) next
      111      return estimate;
      (gdb) next
      112   }
      (gdb) next
      main (argc=5, argv=0x7fffffffdfd8) at q1.c:72
      72       double funcval = func(a, b, c, x + h);
      (gdb) next
      75       writeExtrapolation(x + h, approximation, funcval);
      (gdb) next
      78       h = h + stepSize;
      (gdb) break q1.c:75 if i==250
      Breakpoint 3 at 0x400739: file q1.c, line 75.
      (gdb) info break
      Num     Type           Disp Enb Address            What
      1       breakpoint     keep y   0x00000000004005bc in main at q1.c:43
         breakpoint already hit 1 time
      2       breakpoint     keep y   0x0000000000400660 in main at q1.c:57
         breakpoint already hit 1 time
      3       breakpoint     keep y   0x0000000000400739 in main at q1.c:75
         stop only if i==250


    n) Use the delete command to remove the breakpoints you set at lines 43 and
       57, then use info break to verify that you only have the last,
       conditional, breakpoint now.  Copy those commands and output.

       ANSWER:

      (gdb) delete 1
      (gdb) delete 2
      (gdb) info break
      Num     Type           Disp Enb Address            What
      3       breakpoint     keep y   0x0000000000400739 in main at q1.c:75
         stop only if i==250


    o) Use the continue command to resume execution; gdb should now pause at
       line 75.  Display the values for the variables h, approximation, and
       funcval.  Copy those commands and output.

       ANSWER:

      (gdb) continue
      Continuing.

      Breakpoint 3, main (argc=5, argv=0x7fffffffdfd8) at q1.c:75
      75       writeExtrapolation(x + h, approximation, funcval);
      (gdb) print h
      $3 = 0.25000000000000017
      (gdb) print approximation
      $4 = 17.28125
      (gdb) print funcval
      $5 = 17.278124999999999


    Now use continue again, which should run the program until it terminates
    normally.

   >>>  Each part is worth only 3 points, so I think each part is all or nothing.

2.  [16 points] The file q2.c contains a short main() function and the
    following recursive function:

      int q2(int N) {
         
         if ( N <= 1 ) 
            return 1;
         else {
            int retVal = q2(--N);  // being clever (?) with decrement
            return N * retVal;
         }
      }

    Compile the given code for debugging; it compiles but does not always
    produce correct results:

      centos > q3 5
      5! = 24
      centos > q3 3
      3! = 2

    Use gdb to discover any relevant clues to what goes wrong with the function
    above when you run the program with the parameter 3, as shown in the second
    example above.  Describe your observations, and include supporting lines
    from your gdb output.

    Note:  your work here may not fully explain WHY things go wrong, but it
    should explain clearly WHAT goes wrong.

    ANSWER:

    Here's my approach.  First, I set breakpoints just before main() calls q2(),
    and at the first line in q2(), then I started the program with the parameter
    3:

      (gdb) break q2.c:31
      Breakpoint 1 at 0x400646: file q2.c, line 31.
      (gdb) break q2.c:45
      Breakpoint 2 at 0x40067c: file q2.c, line 45.
      (gdb) run 3
      Starting program: /home/wmcquain/2505/c03/q2/q2 3

    So, I reached the first breakpoint; out of sheer paranoia, I checked to see
    whether N equals 3 right before the call to q3().  It does:

      Breakpoint 1, main (argc=2, argv=0x7fffffffdff8) at q2.c:31
      31    int facN = q2(N);
      Missing separate debuginfos, use: debuginfo-install glibc-2.17-222.el7.x86_64
      (gdb) print N
      $1 = 3

    A backtrace shows the only active function call is for main(), as it should
    be:

      (gdb) backtrace
      #0  main (argc=2, argv=0x7fffffffdff8) at q2.c:31

    Next, I step into the call to q2(), and verify that q2() did receive 3.  I
    also did another backtrace to confirm we have a frame for q2() now:

      (gdb) step

      Breakpoint 2, q2 (N=3) at q2.c:45
      45    if ( N <= 1 ) 
      (gdb) print N
      $2 = 3
      (gdb) backtrace
      #0  q2 (N=3) at q2.c:45
      #1  0x0000000000400650 in main (argc=2, argv=0x7fffffffdff8) at q2.c:31

    Continuing, I pause at the breakpoint again, after the first recursive call
    to q2():

      (gdb) continue
      Continuing.

      Breakpoint 2, q2 (N=2) at q2.c:45
      45    if ( N <= 1 ) 

    A backtrace shows we now have another frame for q2(), corresponding to the
    first recursive call:

      (gdb) backtrace
      #0  q2 (N=2) at q2.c:45
      #1  0x0000000000400697 in q2 (N=2) at q2.c:48
      #2  0x0000000000400650 in main (argc=2, argv=0x7fffffffdff8) at q2.c:31

    But there's something strange in the backtrace above... now the first call
    to q2() shows N == 2, but in the first backtrace the same frame shows that
    N == 3... that may be a clue...

    Let's continue... we get the second recursive call with N == 1, which is
    correct.  But the backtrace now indicates that N == 1 in the frame for the
    first recursive call:

    
      (gdb) continue
      Continuing.

      Breakpoint 2, q2 (N=1) at q2.c:45
      45    if ( N <= 1 ) 
      (gdb) backtrace
      #0  q2 (N=1) at q2.c:45
      #1  0x0000000000400697 in q2 (N=1) at q2.c:48
      #2  0x0000000000400697 in q2 (N=2) at q2.c:48
      #3  0x0000000000400650 in main (argc=2, argv=0x7fffffffdff8) at q2.c:31

    So, I walk through a few instructions until I the second recursive call
    returns:

      (gdb) next
      46       return 1;
      (gdb) next
      51 }

    And, I do the same again until the first recursive call returns:

      (gdb) next
      49       return N * retVal;
      (gdb) backtrace
      #0  q2 (N=1) at q2.c:49
      #1  0x0000000000400697 in q2 (N=2) at q2.c:48
      #2  0x0000000000400650 in main (argc=2, argv=0x7fffffffdff8) at q2.c:31
      (gdb) next
      51 }
      (gdb) next
      49       return N * retVal;
      (gdb) backtrace
      #0  q2 (N=2) at q2.c:49
      #1  0x0000000000400650 in main (argc=2, argv=0x7fffffffdff8) at q2.c:31

    Now, we are in the first (non-recursive) call to q2().  Examining N now 
    shows that N has changed from 3 (see the check above before the first 
    recursive call was made) to 2... that's wrong.

      (gdb) print N
      $3 = 2
      (gdb) print retVal
      $4 = 1
      (gdb) next
      51 }

    And, that shows that main() receives the value 2 when the first call
    to q2() returns to main():

      (gdb) next
      main (argc=2, argv=0x7fffffffdff8) at q2.c:34
      34    printf("%d! = %d\n", N, facN);
      (gdb) print N
      $5 = 3
      (gdb) print facN
      $6 = 2
      (gdb) 

   >>>  The student must show gdb output in order to receive any points.
   >>>  There has to be sufficient evidence to show that something has gone wrong
   >>>  with the value of N that's used after a recursive call returns to the
   >>>  previous call...
   >>>  That requires a considerable amount of gdb output.  I suppose you could
   >>>  give half credit if there's some sensible attempt to analyze it with gdb,
   >>>  but not enough to show that the value of N is being modified in the caller,
   >>>  prior to the recursive return.


3.  The file q3.c contains a short main() function and a second function, q3(),
    called repeatedly by main():

      int main(int argc, char** argv) {

         if ( argc != 2 ) {
            printf("Invocation:  q3 iterLimit, where iterLimit >= 0.\n");
            exit(1);
         }
         
         int iterLimit = atoi(argv[1]);  // convert argument to an integer
         if ( iterLimit < 0 ) {
            printf("iterLimit must be non-negative.\n");
            exit(2);
         }

         int value = -1;
         int pass = 1;  
         while ( pass < iterLimit ) {

            value = q3(pass);
            pass++;
         }
         
         return 0;
      }

      int q3(int N) {
         
         static int dejavue = 1;    // dejavue retains its value for next call

         dejavue = N * dejavue + dejavue % 29;  // perform strange computation

         return ( dejavue % 500 );  // return value between 0 and 499, inclusive
      }

    a) [13 points]  Use appropriate gdb commands to analyze the program and
       determine what value will be returned by the function q3() when it is
       called from the given loop with the parameter equaling 100.  Show the
       relevant gdb output to support your answer.

       ANSWER:

       First, I set a conditional breakpoint on the call to q3():

         (gdb) break q3.c:23 if pass==100
         Breakpoint 1 at 0x400656: file q3.c, line 23.

       Then, I ran the program with a sufficiently large iteration limit:

         (gdb) run 1000
         Starting program: /home/wmcquain/2505/c03/q3/q3 1000
             1:   2
             2:   6
             3:  24
             4: 120
             5: 104
            ...
            97: -346
            98: 493
            99: 104

         Breakpoint 1, main (argc=2, argv=0x7fffffffdff8) at q3.c:23
         23	      value = q3(pass);
         Missing separate debuginfos, use: debuginfo-install glibc-2.17-222.el7.x86_64

       Then I printed the values of the variables pass (unnecessry) and value:

         (gdb) print pass
         $1 = 100
         (gdb) next
         24	      printf("%5d: %3d\n", pass, value);
         (gdb) print value
         $2 = -406

       So, q3() returned -406.

   >>>  To receive credit, the student must show gdb output.  I can't really imagine
   >>>  how to do this without setting a conditional breakpoint, as I did in my
   >>>  answer, but I suppose they could actually step through a huge number of 
   >>>  iterations manually.  I'm not sure how to justify partial credit for this,
   >>>  aside from the possibility that the gdb output is not complete enough; in
   >>>  that case, I can see giving up to half credit.


    b) [13 points]  Use appropriate gdb commands to analyze the program and
       determine what value the variable pass will have at the beginning of the
       iteration on which q3() returns the value -146.  Show the relevant gdb
       output to support your answer.

       ANSWER:

       So, I'll set a conditional break on the call to q3(), watching for the
       situation that value is -146:

         (gdb) break q3.c:23 if value==-146
         Breakpoint 1 at 0x400656: file q3.c, line 23.

       Then, I'll run q3 again, hoping that 1000 iterations are sufficient:

         (gdb) run 1000
         Starting program: /home/wmcquain/2505/c03/q3/q3 1000
             1:   2
             2:   6
             3:  24
           ...
           700: 246
           701: -422
           702: -146

         Breakpoint 1, main (argc=2, argv=0x7fffffffdff8) at q3.c:23
         23	      value = q3(pass);
         Missing separate debuginfos, use: debuginfo-install glibc-2.17-222.el7.x86_64
         (gdb) print value
         $1 = -146
         (gdb) print pass
         $2 = 703

       And... they were... but this isn't quite right.  The pause occurred
       because value == -146, which was not true until the assignment had been
       performed.  The return value was -146 on the previous pass:

         (gdb) break q3.c:23 if pass==702
         Note: breakpoint 1 also set at pc 0x400656.
         Breakpoint 2 at 0x400656: file q3.c, line 23.
         (gdb) run 1000
         The program being debugged has been started already.
         Start it from the beginning? (y or n) y
         Starting program: /home/wmcquain/2505/c03/q3/q3 1000
             1:   2
             2:   6
             3:  24
            ...
           699: -470
           700: 246
           701: -422

         Breakpoint 2, main (argc=2, argv=0x7fffffffdff8) at q3.c:23
         23	      value = q3(pass);
         (gdb) print pass
         $3 = 702
         (gdb) next
         24	      printf("%5d: %3d\n", pass, value);
         (gdb) print value
         $4 = -146
         (gdb) 

       So, q3() returned -146 on the iteration where pass was 702.

   >>>  To receive credit, the student must show gdb output.  I can't really imagine
   >>>  how to do this without setting a conditional breakpoint, as I did in my
   >>>  answer, but I suppose they could actually step through a huge number of 
   >>>  iterations manually.  I'm not sure how to justify partial credit for this,
   >>>  aside from the possibility that the gdb output is not complete enough; in
   >>>  that case, I can see giving up to half credit.

    c) [13 points]  Based on the information you discovered in part b), use
       appropriate gdb commands to analyze the program and determine what value
       the variable dejavue will have immediately before q3() returns the value
       -146.  Show the relevant gdb output to support your answer.

       ANSWER:

       I began by removing a breakpoint I no longer wanted:

         (gdb) info break
         Num     Type           Disp Enb Address            What
         1       breakpoint     keep y   0x0000000000400656 in main at q3.c:23
            stop only if value==-146
         2       breakpoint     keep y   0x0000000000400656 in main at q3.c:23
            stop only if pass==702
            breakpoint already hit 1 time
         (gdb) delete 1

       Then, I restarted the program, which paused at desired iteration:

         (gdb) run 1000
         The program being debugged has been started already.
         Start it from the beginning? (y or n) y
         Starting program: /home/wmcquain/2505/c03/q3/q3 1000
             1:   2
             2:   6
             3:  24
           ...
           699: -470
           700: 246
           701: -422

         Breakpoint 2, main (argc=2, argv=0x7fffffffdff8) at q3.c:23
         23	      value = q3(pass);
         (gdb) print pass
         $5 = 702

       Then, I stepped into the call to q3(), and obtained the value of dejavue:

         (gdb) step
         q3 (N=702) at q3.c:35
         35	   dejavue = N * dejavue + dejavue % 29;  // perform strange computation
         (gdb) next
         37	   return ( dejavue % 500 );  // return value between 0 and 499, inclusive
         (gdb) print dejavue
         $6 = -1127450146

       Just to be sure, I walked back to main() and checked the return value:

         (gdb) next
         38	}
         (gdb) next
         main (argc=2, argv=0x7fffffffdff8) at q3.c:24
         24	      printf("%5d: %3d\n", pass, value);
         (gdb) print value
         $7 = -146
         (gdb) 

   >>>  To receive credit, the student must show gdb output.  I can't really imagine
   >>>  how to do this without setting a conditional breakpoint, as I did in my
   >>>  answer, but I suppose they could actually step through a huge number of 
   >>>  iterations manually.  I'm not sure how to justify partial credit for this,
   >>>  aside from the possibility that the gdb output is not complete enough; in
   >>>  that case, I can see giving up to half credit.