CMSC216 Lab08: Caller / Callee Registers and Global Variables in Assembly

                           _________________

                            LAB08 QUESTIONS
                           _________________


Exercise Instructions
=====================

  Follow the instructions below to experiment with topics related to
  this exercise.
  - For sections marked QUIZ, fill in an (X) for the appropriate
    response in this file. Use the command `make test-quiz' to see if
    all of your answers are correct.
  - For sections marked CODE, complete the code indicated. Use the
    command `make test-code' to check if your code is complete.
  - DO NOT CHANGE any parts of this file except the QUIZ sections as it
    may interfere with the tests otherwise.
  - If your `QUESTIONS.txt' file seems corrupted, restore it by copying
    over the `QUESTIONS.txt.bk' backup file.
  - When you complete the exercises, check your answers with `make test'
    and if all is well, create a zip file with `make zip' and upload it
    to Gradescope. Ensure that the Autograder there reflects your local
    results.
  - IF YOU WORK IN A GROUP only one member needs to submit and then add
    the names of their group.


PROBLEM 1 Overview of addstrs
=============================

  Survey the provided code and examine the following source files.
  ------------------------------------------------------------------------------------------------------------------
   FILE                  Description                                                                                
  ------------------------------------------------------------------------------------------------------------------
   add2strs_main.c       A main() and convert() function in C; these are used assembly function add2strs()          
   add2strs_asm_A.s      A broken version of the add2strs() function in assembly for study                          
   add2strs_asm_B.s      A broken version of the add2strs() function in assembly for study                          
   add2strs_asm_C.s      An empty version of add2strs() that needs to be Edited                                     
   add2strs_reference.c  A reference C implementation of add2strs(): it shows the intended behavior of the function 
  ------------------------------------------------------------------------------------------------------------------

  The general setup is the following calling sequence:
  - main() written in C calls...
  - add2strs() written in Assembly calls...
  - convert() written in C
  The middle function add2strs() has several versions which are
  broken. The goal of the lab is to explain why the A and B versions are
  incorrect and create a working C version of the function in
  `add2strs_asm_C.s'.

  The primary reason that the A and B versions broken is a failure to
  adhere to the usage conventions for caller/callee save registers.


PROBLEM 1 QUIZ add2strs_asm_A.s
===============================

Step 1
~~~~~~

  Type `make' which will build several executables based on different
  combinations of the source files
  ,----
  | >> make
  | gcc -Wall -Werror -g  -o add2strs_main_A add2strs_asm_A.s add2strs_main.c add2strs_clobber_asm.s
  | gcc -Wall -Werror -g  -o add2strs_main_B add2strs_asm_B.s add2strs_main.c add2strs_clobber_asm.s
  | gcc -Wall -Werror -g  -o add2strs_main_C add2strs_asm_C.s add2strs_main.c add2strs_clobber_asm.s
  `----
  Note that there are 3 executables built based on the a/b/c versions of
  assembly files.

  Run the "A" version of the main program.

  NOTE: If you aren't sure how to run a an executable, now would be a
  great time to talk with a staff member about what the output of the
  `make' command above and which parts of it show the executables that
  are produced and how to run them.

  What is the result of running the A version of the program?
  - ( ) A segmentation fault occurs while the program runs
  - ( ) The program runs but prints the error message "Unable to convert
    string to number"
  - ( ) The program runs normally but produces obviously incorrect
    output
  - ( ) The program runs correctly to completion but returns a non-zero
    exit code


Step 2
~~~~~~

  To get more insight on what is happening, run the A version of the
  program under Valgrind to print messages about any memory errors
  occur. Again, if you're not sure how to run the program under
  Valgrind, ASK A STAFF MEMBER for help.

  What does Valgrind report about the behavior of the program?
  - ( ) The `main()' function has a bad memory reference likely due to a
    faulty return value from the `addstrs()' function.
  - ( ) There is a bad memory reference by the assembly `addstrs()'
    function which is called from the C `main()' function
  - ( ) There is a bad memory reference during the C `convert()'
    function that is called by the assembly `addstrs()' function
  - ( ) Trick question: there are no memory problems reported by
    Valgrind


Step 3
~~~~~~

  Use GDB to step through the execution of `add2strs()' A version. Use
  the `nexti' command to step line by line through the function but step
  over any function calls: `convert()' is written in C so there is no
  reason to expect it is faulty. Look for obviously wrong assumptions in
  the code for `add2strs()' according to the comments given.

  Which of the following best summarizes the mistakes made in the A
  version which lead to its wrong behavior?
  - ( ) The stack is not aligned properly for the function call to
    succeed
  - ( ) The stack is not properly restored at the end of the function
    which causes problems on the return
  - ( ) Data is not properly loaded into argument registers for the
    first call to the `convert()' function
  - ( ) Data such as pointers are stored in Caller save registers that
    change when the `convert()' function is called


PROBLEM 1 QUIZ add2strs_asm_B.s
===============================

Step 1
~~~~~~

  Examine the B version of the assembly code in `add2strs_asm_B.s'.
  Which of the following best describes the different approach taken in
  the B version compared to the A version.

  - ( ) Callee Save Registers like %rbp and %rbx are used to preserve
    needed data across the call to `convert()' which clobbers Caller
    Save Registers
  - ( ) Adjustments are made to how the argument registers are loaded
    for the first call to `convert()' so that the function runs
    correctly.
  - ( ) The stack is aligned differently for function calls in this
    version which correct compared to the alignment used in the A
    version.
  - ( ) Callee registers that are used are saved and then restored
    before returning from the function.


Step 2
~~~~~~

  Run the B version of the program which uses this version of the
  assembly code. Run the program under Valgrind as well. Which of the
  following best describe the results?
  - ( ) A segmentation fault still occurs but it happens on the second
    call to `convert()' during `add2strs()'
  - ( ) A segmentation fault still occurs but it happens during the
    `main()' function.
  - ( ) The program runs but it produces incorrect results and Valgrind
    reports a "Conditional move/jump depends on uninitialized data"
  - ( ) The program runs and produces incorrect results but Valgrind
    does not report any errors.


Step 3
~~~~~~

  Run the B version of the program under GDB.  Set a breakpoint in
  `add2strs()' and step through the assembly noting its behavior.
  Again, use the nexti command to step over calls to `convert()'.

  Continue stepping through the return from `add2strs()' which will land
  back in `main()'.  When the debugger shows the C code for `main()',
  change its display to the assembly instructions for that C code using
  the GDB command `layout asm'.

  Which of the following best describes the instructions that appear in
  `main()' immediately after `call add2strs'?
  - ( ) These instructions make use of the stack pointer `%rsp' which
    was not properly restored by `add2strs()' which will create problem
    for `main()'
  - ( ) These instructions use a Caller Save register like `%rdi' which
    was altered by `add2strs()' but not restored which will create
    problems for `main()'
  - ( ) These instructions use a Callee Save register like `%rbp' which
    was altered by `add2strs()' but not restored which will create
    problems for `main()'
  - ( ) These instructions perform a buffer overflow check and due to
    one occurring in `add2strs()', problems are created for `main()'.


PROBLEM 1 CODE add2strs_asm_C.s
===============================

  Fill in a completely correct definition for the `add2strs()' function
  in the file `add2strs_asm_C.s' which is currently mostly blank. Base
  your code on the B version but correct the problems you identified in
  the with that version. Some useful instructions for this purpose are
  noted below.
  -----------------------------------------------------------------------
   INSTRUCTION  EFFECT                                                   
  -----------------------------------------------------------------------
   pushq %rxy   Extends the stack and places the current 8-byte value of 
                register %rxy in the stack to "save" the register        
                                                                       
   popq %rxy    Copies the 8-byte value pointed at by the Stack Pointer  
                into register %rxy "restoring" it then shrinks the stack 
  -----------------------------------------------------------------------


  REMEMBER: For function calls to be compliant with the x86-64 standard,
  the Stack Pointer must be divisible by 16. Functions that call other
  functions typically expand the stack by the following number of bytes
  with a combination of `pushq / subq' instructions.
  ------------------------------------------------------------------------------------------------
   PUSHQ / SUBQ GROWTH  RETURN ADDRESSS  TOTAL STACK GROWTH  EXAMPLES                             
  ------------------------------------------------------------------------------------------------
   8 bytes              8 bytes          16 bytes            subq $8,%rsp OR pushq %rbx           
   24 bytes             8 bytes          32 bytes            pushq %rbx; pushq %rbp; subq $8,%rsp 
   40 bytes             8 bytes          48 bytes            pushq %rbp; subq $32,%rsp            
  ------------------------------------------------------------------------------------------------

  FINAL NOTE: When writing longer assembly functions, one may "run out"
  of Caller Save registers. Even if there are no function calls, it is
  still common practice to push/pop Callee Save registers to allow their
  use during these longer functions. Just make sure to push/pop in
  opposite orders to respect stack semantics:
  ,----
  | longfunc:
  |         pushq %reg1             # callee save regs like rbx, rbp, r15
  |         pushq %reg2
  |         pushq %reg3
  |         ...
  |         ...     # code that needs to use callee save reg1,reg2,reg3
  | 
  |         popq %reg3              # last in, first out stack semantics
  |         popq %reg2
  |         popq %reg1
  |         ret
  `----

  You can test your code for the problem via the provided Makefile:
  ,----
  | make test-code testnum=1
  `----


PROBLEM 2 Overview of prime program
===================================

  Examine the following files related to this problem.
  -----------------------------------------------------------------------------------------------------
   FILE               Description                                                                      
  -----------------------------------------------------------------------------------------------------
   prime_main.c       A main() function in C that calls two functions defined elsewhere                
   prime_funcs.c      C implementations of the primprod() and primsums() functions                     
   prime_funcs_asm.s  Assembly implementations of primprod() and primsums(), the 2nd must be completed 
  -----------------------------------------------------------------------------------------------------

  The code performs some simple integer calculations involving
  arithmetic on prime numbers. It utilizes a global array called
  `primes[]' that contains some prime numbers in it. This allows the
  demonstrating of how global variables, particularly arrays, are
  accessed in assembly. Provided code shows the syntax for this using
  RIP-relative addressing which must be used to complete the second
  function.


PROBLEM 2 QUIZ
==============

  Study the C and Assembly implementations in `prime_funcs.c /
  prime_funcs_asm.s' and answer the following questions.


A
~

  The variable `primes[]' is declared in the C program outside of any
  function making it a global variable. Where does this variable appear
  in the Assembly version of the code?
  - ( ) It is defined in a separate file `prime_funcs_asm.data' because
    Assembly implementation requires that Global Data and Functions be
    placed in different compilation units
  - ( ) It is lower down in the `prime_funcs_asm.s' file in a `.data'
    section which is distinguished from the `.text' section where the
    functions are placed
  - ( ) It is simply defined above the Assembly functions in
    `prime_funcs_asm.s' using the same syntax as in C:
    ,----
    | int data[200] = {2,3,7,...};
    `----
  - ( ) Trick question: the `primes[]' array is actually defined in
    `prime_main.c' and only used in the assembly code.


B
~

  The C code for `primprod()' starts with a complex condition to check
  for bad parameters. Which of the following best describes how this is
  realized in assembly.
  - ( ) The instruction `cmpl' is used with multiple operands (8 in this
    case) to check all comparisons and a single jump is made if any are
    invalid.
  - ( ) The instruction `cmpmultl' is used with multiple operands (8 in
    this case) to check all comparisons and a single jump is made if any
    are invalid.
  - ( ) The instruction `cmpl' is used with two operands 4 times in a
    row to check each comparison with a jump to an error label made if
    the condition is not met.
  - ( ) The instruction `cmpmultl' is used with multiple operands (3 in
    this case) to check that a register is between two constants. Two
    checks are made for the two parameter registers which are followed
    by jumps if the condition is not met.


C
~

  Which of the following best describes the following instruction?
  ,----
  | leaq primes(%rip), %rcx
  `----

  - ( ) It loads the address of the global variable `primes' into the
    `%rcx' register
  - ( ) It moves the value of the global variable `primes' into the
    `%rcx' register
  - ( ) It creates the global variable `primes' at the location
    indicated by the `%rcx' register
  - ( ) It creates the global variable `primes' at the location
    indicated by the `%rip' register and gives it the initial value
    stored in `%rcx'


D
~

  Which of the following best describes the following instruction which
  appears soon after the one above?
  ,----
  | movl (%rcx,%rdi,4), %eax
  `----

  - ( ) It computes the arithmetic expression `4*rdi+rcx' and stores
    that value in `%eax'.
  - ( ) It treats `%rcx' as a pointer to an array, `%rdi' as an index
    into the array, and the array elements of as size 4; it copies the
    value in `%eax' into all elements of array up to index `%rdi'
  - ( ) It treats `%rcx' as a pointer to an array, `%rdi' as an index
    into the array, and the array elements of as size 4; it copies the
    value in `%eax' into the array at the given position
  - ( ) It treats `%rcx' as a pointer to an array, `%rdi' as an index
    into the array, and the array elements of as size 4; it copies the
    value from the array into the register `%eax'


PROBLEM 2 CODE
==============

  Complete the assembly implementation of `primsums()'. Use the provided
  C code as a reference for its behavior and the the techniques
  demonstrated in `primprod()' Assembly function to complete the
  function. To complete the function, you'll need a good grasp on
  - Which registers are used for function parameters and its return
    value
  - How to create a simple loop in assembly
  - How to set up a pointer to a global array
  - How to access array elements

  You can test your code for the problem via the provided Makefile:
  ,----
  | make test-code testnum=2
  `----


PROBLEM 2 OPTIONAL Code Practice
================================

  For additional practice, complete the optional function `primfact()'
  in `prime_funcs_asm.s'.  The C version of this is provided in
  `prime_funcs.c' and a `main()' for it is present in `prime_fact.c'.
  no test cases are available by when compiling, two executables are
  produced
  - `prime_fact_c' based on the C provided implementation
  - `prime_fact_asm' based on the Assembly implementation
  and their output can be compared to determine if the code is correct.

  NOTE: This is a more challenging function as it requires the use of
  division which has a number of interesting effects such as clobbering
  several registers. It makes for EXCELLENT practice in preparation for
  projects involving assembly.