CSCI 2021 Lab08: Stack Space and Function Calls

Due: 11:59pm Tue 21-Mar-2023 on Gradescope
Approximately 1.00% of total grade

CODE DISTRIBUTION: lab08-code.zip

CHANGELOG:

Wed Mar 15 09:40:44 AM CDT 2023: A minor problem with the Lab 08 Makefile and a missing file caused the command make test-code to fail for some students though make test would work. The code pack has been updated to include the missing file and a correction to the Makefile. If you are experiencing problems, re-download lab08-code.zip and copy over your version of order3_asm.s to the new directory.

1. Rationale
2. Codepack
3. Using Stack Space for Local Variables
4. QUESTIONS.txt File Contents
5. Submission

1 Rationale

Function calls are an important abstraction in any computing environment. At the architecture/assembly level, function calls often involve some setup such as placing arguments in certain registers. Also, functions that require local variables in main memory must manipulate the stack pointer, %rsp in x86-64, to "create" such space and then track offsets from the stack pointer at which various local variables reside. These two phenomena are intertwined: calling a function always means aligning the %rsp to a 16-byte boundary and passing the main memory address of a local variable to another function often involves loading an argument variable with an address based on %rsp.

This lab demonstrates several of these concepts by completing a main() function in assembly which has several local variables that require main memory addresses and passes those addresses to another function.

Associated Reading / Preparation

Bryant and O'Hallaron Ch 3.7 on assembly procedure call conventions in x86-64. This section includes discussion of using the stack for local variables and passing arguments to functions.
Any overview guide to x86-64 assembly instructions such as Brown University's x64 Cheat Sheet

Grading Policy

Credit for this Lab is earned by completing the exercises here and submitting a Zip of the work to Gradescope. Students are responsible to check that the results produced locally via make test are reflected on Gradescope after submitting their completed Zip. Successful completion earns 1 Engagement Point.

Lab Exercises are open resource/open collaboration and students are encouraged to cooperate on labs. Students may submit work as groups of up to 5 to Gradescope: one person submits then adds the names of their group members to the submission.

See the full policies in the course syllabus.

2 Codepack

The codepack for the HW contains the following files:

File		Description
`QUESTIONS.txt`	EDIT	Questions to answer: fill in the multiple choice selections in this file.
`order3_asm.s`	EDIT	Incomplete Assembly main() function, fill in remaining code
`order3_c.c`	Provided	C version of code for reference
`Makefile`	Build	Enables `make test` and `make zip`
`QUESTIONS.txt.bk`	Backup	Backup copy of the original file to help revert if needed
`QUESTIONS.md5`	Testing	Checksum for answers in questions file
`test_quiz_filter`	Testing	Filter to extract answers from Questions file, used in testing
`test_lab08.org`	Testing	Tests for this lab
`testy`	Testing	Test running scripts

3 Using Stack Space for Local Variables

This lab focuses on situations where local variables in a function like main() require main memory addresses.

Examine the Completed code in order3_c.c first to get a sense of the C code versions of the main() and order3() functions.
Examine the assembly code in order3_asm.s:
- COMPLETE the assembly main() according to the provided outline
- The assembly order3() function is complete and correct and requires no modification.

Locals in the Stack

Demoers will examine code such as the following fragment from main() in order3_c.c:

  int r=17, t=12, v=13;
  order3(&r, &t, &v);

It is important to realize that since r,t,v need memory addresses for the function call, they cannot exist only in registers. A compiler will likely place them in the function call stack. This appears in x86-64 assembly as offsets from the stack pointer %rsp such as the following fragment in order3_asm.s:

  movl    $17, 0(%rsp)           # r=17
  movl    $12, 4(%rsp)           # t=12
  movl    $13, 8(%rsp)           # v=13

Near the top of the assembly code for main() is a table indicating the locations of all the local variables in the stack.

Creating Stack Space

Prior to writing into the stack the stack pointer %rsp must be adjusted to grow the stack. Growing the stack is usually done by

A subtraction like subq $24, %rsp which will grow the stack by some number of bytes, usually large enough for the local variables, but leave that area uninitialized. Subtractions are usually used at the beginning of a function execution.
A push like pushl %r15d which will grow the stack a little, 4 bytes in this case, and initialize the new space with a value, in this case the value in register %r15d. Several pushX instructions can be used in a row, usually towards the beginning of a function. They are most often used to save registers that will be changed and need be restored such as %r15 or other Callee save registers.

Note that the stack grows downwards to lower addresses and shrinks upwards to higher addresses in x86-64. Later when the stack needs to shrink, the "inverse" instructions are used to adjust %rsp.

An addition like addq $24, %rsp undoes a subtraction.
A pop like popl %r15d which copies the 4-byte value at the top of the stack into the given register and shrinks the stack by 4 bytes.

Keep in mind that any changes to %rsp must be undone before returning as %rsp must point at the function's return address when ret is used.

Insert assembly code near the top of main() to grow the stack by an appropriate amount of space. This is discussed further in the Grow/Shrink section later.

Address of Locals in Assembly

The preceding assembly fragment is followed by additional instructions which equate to the address-of &x operator in C to load the stack locations of several local variables prior to a function call. This appears as the following assembly code.

  movq    %rsp, %rdi             # arg1 &r 
  leaq    4(%rsp), %rsi          # arg2 &t
  leaq    8(%rsp), %rdx          # arg3 &v
  call    order3                 # function call: order3(&r, &t, &v);

Note the use of movq to copy the stack pointer to %rdi as %rsp contains the address of the variable r already while the Load Effective Address leaq instruction is used to compute the addresses for variables t,v and store them in registers.

There are similar blocks that follow this initial example and you should use the table at the top of main() to guide you on where the various local variables are stored in the stack. Note that this stack storage is required because the order3() function requires memory addresses/pointers as arguments so the variables must be stored in main memory rather than registers.

Calls to `printf()`

Similarly, there are several blocks that need to be COMPLETE'd to call printf() to show the results of the ordering. Use the template provided and adjust the pattern as needed. Note that the printf() function is special for two reasons.

It is a "variadic" function which can take an arbitrary number of arguments. This has the special convention that the %eax register is used during function call setup, set to 0 in the sample code to indicate no vector registers are used. This is not essential to understand so copy the pattern provided.
It is defined in a dynamically linked library and thus uses the Procedure Linkage Table during its call via the syntax call printf@PLT. This may be discussed later in the semester when we study the linking process.

Grow/Shrink the Stack

IMPORTANT:

The main() function needs space for local variables during its operation so should create enough space for all locals at the beginning of its execution.
Before returning main() must restore %rsp through add/pop instructions to shrink the stack to its original state where %rsp points to the return address.

Finally, the x86-64 interface dictates that when calling a function such as in call order3, the %rsp should be divisible by 16, referred to at times as "the stack is aligned for function calls." This leads to an interesting calculation that the compiler computes to decide how many bytes to adjust the stack pointer:

When a function is called, the stack pointer is divisible by 16; call its value N
The call instruction pushes 8 bytes for the return address into the stack. The stack pointer is now N-8 which is NOT divisible by 16.
Even if a function has no locals, if it in turn calls another function, the compiler will usually grow the stack by another 8 bytes to re-align the stack. This is done with instructions like subq $8, %rsp which leaves %rsp with value N-16 which is again divisible by 16.
If space is required for locals like 36 bytes, then the compiler must grow by this amount such as via subq $36, %rsp leaving %rsp at N-8-36 = N-44. Unfortunately this is not divisible by 16 so often the compiler "pads" the stack growth to get to alignment: rather than growing by 36, grow by 40 bytes giving N-40-8 = N-48 which is divisible by 16.
Such "padded" expansion of the stack both (1) creates space for locals and (2) prepares for a function call later on in execution.

4 QUESTIONS.txt File Contents

Below are the contents of the QUESTIONS.txt file for the lab. Follow the instructions in it to complete the QUIZ and CODE questions for the lab.

                           __________________

                            LAB 08 QUESTIONS
                           __________________





Lab Instructions
================

  Follow the instructions below to experiment with topics related to
  this lab.
  - 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.


QUIZ Coding Assembly Functions
==============================

  Answer the following questions on stack manipulation and function
  calls in assembly.


Growing the Stack
~~~~~~~~~~~~~~~~~

  Which of the following instructions can be used to extend / grow the
  stack?
      Instruction     Description                                                                                
  ---------------------------------------------------------------------------------------------------------------
   A  subq $20, %rsp  extends the stack by 20 bytes, data is uninitialized                                       
   B  pushq %rbx      extends the stack by 8 bytes, 8-byte value in register ebx written at the top of the stack 
   C  pushl $99       extends the stack by 4 bytes, 4-byte value 99 written at the top of the stack              

  - ( ) A only
  - ( ) B only
  - ( ) C only
  - ( ) Any combination of A/B/C: they all grow the stack


callq effects on Stack Pointer
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  When calling a function via the `callq', the stack pointer `%rsp' must
  be "aligned", e.g. divisible by 16.  Assuming this is so, how does the
  `callq' instruction change `%rsp'?

  - ( ) `callq' does not change `%rsp' during at all. `%rsp' is
    therefore still divisible by 16 after the instruction completes.
  - ( ) `callq' will subtract off 8 from the value of `%rsp' and places
    the return address at the top of the stack. `%rsp' is then divisible
    by 8 but not 16.
  - ( ) `callq' will subtract off 16 from the value of `%rsp' and places
    the return address at the top of the stack. `%rsp' is therefore
    still divisible by 16.
  - ( ) `callq' will subtract off 24 from the value of `%rsp' and places
    the return address at the top of the stack. `%rsp' is then divisible
    by 8 but not 16.


Alignment
~~~~~~~~~

  If the total size of local variables that need main memory space in a
  function is 36 bytes, one approach is to grow the stack by 36 bytes
  exactly. BUT if functions are to be called during that function, then
  it would be better to...
  - ( ) No special action is required: growing by 36 bytes is a good
    idea as it saves memory while growing larger would waste memory.
  - ( ) No special action is required: the `callq' instruction
    automatically changes `%rsp' to be a value that is divisible by 16.
  - ( ) Grow the stack by 48 bytes; this will mean `%rsp' is aligned at
    a 16-byte boundary and ready for function calls.
  - ( ) Grow the stack by 40 bytes; this + 8 bytes for the return
    address in the stack will mean `%rsp' is aligned at a 16-byte
    boundary and ready for function calls.


CODE order3_asm.s
=================

  Complete the `main()' function in `order3_asm.s'. This will require
  completing the `TODO' sections in the code to grow the stack, populate
  the stack with local variable values, call several functions with the
  addresses of local variables, and then shrink the stack.

  To help understand the intent of the assembly code, you can analyze
  the equivalent C code in `order3_c.c' which performs the same
  "computation" in C including use of the address-of operator.

  When written correctly, the program should compile and run as follows.
  ,----
  | > make
  | gcc -Wall -Werror -g  -o order3_c order3_c.c
  | gcc -Wall -Werror -g  -o order3_asm order3_asm.s
  | 
  | > ./order3_asm 
  | r t v: 12 13 17
  | q e d:  2  5  9
  | i j k: 24 27 29
  `----

  If mistakes in the stack manipulation are present, this can lead to
  problems late in the program. Valgrind can give a little insight but
  generally these are difficult problems to diagnose so be careful. For
  example, below is a transcript of an incorrectly written version which
  does not allocate the correct amount of space in the stack for the
  local variables.

  ,----
  | > ./order3_asm                     # run broken version
  | r t v: 12 13 17                    # output look okay
  | q e d:  2  5  9
  | i j k: 24 27 29
  | Segmentation fault (core dumped)   # uh-oh...
  | 
  | > valgrind ./order3_asm            # see if valgrind gives any help
  | ==2508984== Memcheck, a memory error detector
  | ==2508984== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
  | ==2508984== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
  | ==2508984== Command: ./order3_asm
  | ==2508984== 
  | r t v: 12 13 17                    # output OK...
  | q e d:  2  5  9
  | i j k: 24 27 29
  | ==2508984== Jump to the invalid address stated on the next line
  | ==2508984==    at 0x1D: ???
  | ==2508984==    by 0x1FFF000557: ???
  | ==2508984==    by 0x10489EF72: ???
  | ==2508984==    by 0x109138: ??? (in ./order3_asm)
  | ==2508984==    by 0x7FFFFFFFF: ???
  | ==2508984==  Address 0x1d is not stack'd, malloc'd or (recently) free'd
  | ==2508984==                        # ADDRESS 0x1d is really small; probably clobbered 
  | ==2508984==                        # return address during execution, look at stack carefully
  | ==2508984== Process terminating with default action of signal 11 (SIGSEGV): dumping core
  | ==2508984==  Bad permissions for mapped region at address 0x1D
  | ==2508984==    at 0x1D: ???
  | ==2508984==    by 0x1FFF000557: ???
  | ==2508984==    by 0x10489EF72: ???
  | ==2508984==    by 0x109138: ??? (in ./order3_asm)
  | ==2508984==    by 0x7FFFFFFFF: ???
  | ==2508984== 
  | ==2508984== HEAP SUMMARY:
  | ==2508984==     in use at exit: 0 bytes in 0 blocks
  | ==2508984==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
  | ==2508984== 
  | ==2508984== All heap blocks were freed -- no leaks are possible
  | ==2508984== 
  | ==2508984== For lists of detected and suppressed errors, rerun with: -s
  | ==2508984== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
  | Segmentation fault (core dumped)
  `----

5 Submission

Follow the instructions at the end of Lab01 if you need a refresher on how to upload your completed lab zip to Gradescope.