Last Updated: 2025-10-18 Sat 10:50

CMSC216 Lab07: Stack Space and Function Calls

CODE DISTRIBUTION: lab07-code.zip

CHANGELOG: Empty

1 Rationale

Debuggers must inherently deal with binary programs as this is what the processor actually runs. While it is massively more convenient when high-level source code is available to use during debugging, it is still possible to analyze and understand program behavior by disassembling the compiled instructions contained in the program. Most debuggers can do this in debug sessions producing text versions of the assembly code and as well show values in registers and memory those instructions manipulate. That in combination with a strong will and reservoir of patience allow debugging of binaries without source code. This lab provides practices the working with binaries to deepen knowledge of the debugger and compiled assembly.

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. 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 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

PROBLEM 1

PROBLEM 2

  • 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.

Grading Policy

Credit for this exercise is earned by completing the code/asnwers 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.
     
quote_main.c Provided Problem 1: Main file for debugging
quote_data.o Provided Problem 1: Binary file for debugging
     
order2_asm.s EDIT Problem 2: Incomplete Assembly main() function, fill in remaining code
order2_c.c Provided Problem 2: C version of code for reference
order3_asm.s EDIT Problem 2: Incomplete Assembly main() function, fill in remaining code
order3_c.c Provided Problem 2: 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_order_asm.org Testing Tests for code portions of the lab run via make test-code
test_lab07.org Testing Tests for this exercise
testy Testing Test running scripts

3 Using Stack Space for Local Variables

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

  1. Examine the Completed code in order2_c.c first to get a sense of the C code versions of the main() and order2() functions.
  2. Examine the assembly code in order2_asm.s:
    • COMPLETE the assembly main() according to the provided outline
    • The assembly order2() function is complete and correct and requires no modification.
  3. Examine the Completed code in order3_c.c first to get a sense of the C code versions of the main() and order3() functions. Note that there are several function calls and many more local variables requiring addresses.
  4. Examine the assembly code in order3_asm.s and complete the TODO sections in main() according to the provided outline. Pay careful attention to the local variable layout table.

Locals in the Stack

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

  int r=17, t=12;
  order2(&r, &t);

It is important to realize that since r,t 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 order2_asm.s: 

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

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 via one of two methods.

  1. A subtraction like subq $24, %rsp which will grow the stack by 24 bytes. The specific value is chosen to be large enough for all local variables but leaves that area uninitialized. Subtractions are usually used at the beginning of a function execution to grow the stack.
  2. 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 of 24 bytes.
  • 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() in the provided assembly files 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.

  1. 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.
  2. 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 order2 or 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 exercise. Follow the instructions in it to complete the QUIZ and CODE questions for the exercise. 

                           _________________

                            LAB07 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: Binary Debugging of QUOTES
=====================================

  The two files `quote_main.c' and `quote_data.o' can be compiled
  together to form an executable as in the following.
  ,----
  | > gcc quote_main.c quote_data.o
  | > ./a.out
  | Complete this sentence by C++ creator Bjarne Stroustrup:
  | C makes it easy to shoot yourself in the foot; ...
  | 
  | enter a number from 0 to 15: 2
  | 
  | 2: This is why most programmers are such poor dancers.
  | 
  | Have a nice tall glass of ... NOPE.
  `----
  As in a previous exercise, the intention is to use the debugger to
  detect the correct response. In this case however, the correct
  completion is present in `quote_main.c'. However, one must enter a
  number which selects from several responses in an attempt to match the
  correct completion. This causes something to happen in `quote_data.o'
  but no source code is available for it.

  It is possible to "brute force" the solution by trying all
  solutions. That would miss the purpose of the exercise, to gain
  familiarity with how GDB can handle binaries and allow one to resolve
  situations that are not so amenable to brute force.


QUIZ: Basic Binary Analysis
~~~~~~~~~~~~~~~~~~~~~~~~~~~

  Use some utility programs to gather information about the contents of
  the binary file `quote_data.o'.  Review the previous HW if you have
  forgotten what programs do OR brute force this QUIZ question by trying
  the various suggested programs to see what they do.

  For each of the below commands, select the response that best
  describes its effect.


`>> nm quote_data.o'
--------------------

  - ( ) Prints back the name of the file
  - ( ) Displays the assembly code in the TEXT section of the file
  - ( ) Displays the original C code that produced the binary file
  - ( ) Shows the "symbols" (functions and global variables) in the file
  - ( ) Shows the ELF (executable/linkable format) sections are in file
  - ( ) Produces all ASCII strings embedded in the file


`>> objdump -d quote_data.o'
----------------------------

  - ( ) Prints back the name of the file
  - ( ) Displays the assembly code in the TEXT section of the file
  - ( ) Displays the original C code that produced the binary file
  - ( ) Shows the "symbols" (functions and global variables) in the file
  - ( ) Shows the ELF (executable/linkable format) sections are in file
  - ( ) Produces all ASCII strings embedded in the file


`>> readelf -s quote_data.o'
----------------------------

  - ( ) Prints back the name of the file
  - ( ) Displays the assembly code in the TEXT section of the file
  - ( ) Displays the original C code that produced the binary file
  - ( ) Shows the "symbols" (functions and global variables) in the file
  - ( ) Shows the ELF (executable/linkable format) sections are in file
  - ( ) Produces all ASCII strings embedded in the file


`>> strings quote_data.o'
-------------------------

  - ( ) Prints back the name of the file
  - ( ) Displays the assembly code in the TEXT section of the file
  - ( ) Displays the original C code that produced the binary file
  - ( ) Shows the "symbols" (functions and global variables) in the file
  - ( ) Shows the ELF (executable/linkable format) sections are in file
  - ( ) Produces all ASCII strings embedded in the file


QUIZ: GDB with Compiled Functions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  The entry point into the assembly code in `quote_data.o' is the
  function `get_it()' which is called from the `main()' function defined
  in `quote_main.c'.

  Which of the following command sequences will start `gdb', set a break
  point on this function, and run to that position?
  ,----
  | ####### A ######
  | >> gdb -tui quote_main
  | (gdb) break get_it
  | (gdb) run
  | 
  | ####### B ######
  | >> gdb -tui quote_data.o
  | (gdb) break get_it
  | (gdb) run main
  | 
  | ####### C ######
  | >> gdb -tui quote_main.c
  | (gdb) break quote_data.o
  | (gdb) run get_it
  | 
  | ####### D ######
  | >> gdb -tui quote_data.o
  | (gdb) break quote_main
  | (gdb) run get_it
  `----

  - ( ) A
  - ( ) B
  - ( ) C
  - ( ) D

  On arriving in the `get_it()' function, what does GDB show initially
  about the function?
  - ( ) It shows the first lines of the C code for that function
  - ( ) It shows the first lines of the Assembly code for that function
  - ( ) It shows the first lines of the Binary Opcodes for that function
  - ( ) It shows "No Source Available" because a certain cruel
    instructor omitted the source code for this binary file.

  Type thefollowing commands below and indicate how this changes the
  display that GDB shows.
  ,----
  | (gdb) layout asm
  | (gdb) layout regs
  | (gdb) run
  | # answer "y" to re-run
  `----
  After these commands GDB shows
  - ( ) The return value of the `get_it()' function and the register it
    is stored in
  - ( ) The values of all registers and the C code of `get_it()'
  - ( ) The values of all registers and the assembly instructions of
    `get_it()' (which are disassembled by GDB)
  - ( ) The values of all registers and the binary and hex encoding of
    the machine instructions for `get_it()'


CODE: Step through the code to find the right Choice
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  Use the debugger to step through the functions in `quote_data.o' and
  determine the right number to pass in to generate the correct
  response. Place this number in the file `input.txt' which is opened
  and read by `quote_main.c'.

  *NOTE: It is VERY EASY to solve this via brute force* by trying many
  possibilities BUT the point is the gain experience navigating assembly
  code with GDB and understanding compiled code despite lacking its
  original source.

  Here are some tips to help you navigate and understand what you see.
  - Debugger commands for single instructions are preferable when
    working in assembly
     stepi / si  step a single instruction forward, step INTO function calls 
     nexti / ni  step a single instruction forward, step OVER function calls 
    Use plain `step' may step several instructions ahead as GDB guesses
    on how many correspond to a missing line of C.

  - Within the code for `get_it' is a call to `list_get'. This along
    with the fact that earlier listings of global variables had a
    `nodes' name indicates that some sort of linked list is present with
    the choices.

  - The parameters to the function follow the standard convention: 1st
    param in register `%rdi', second in `%rsi', and so forth.  You
    should be able to identify a loop in a critical function in which
    the choices are present.  Use `print' and `x' commands in gdb to
    examine data pointed to be registers to help identify where the
    correct response is located.

  - Often the `testX' instruction is used to determine truthy/falsey
    qualities about a register. This takes several forms that are
    discussed in lecture that you are likely to see:
    - `testl %edx, %edx' may be used to check if `%edx' is 0 or negative
    - `testq %rax, %rax' may be used to check if `%rax' is a `NULL'
      pointer

  - You can examine memory addresses pointed to registers with gdb
    commands like the following. More details are in the GDB Quick
    Guide.
    ,----
    |   (gdb) x/d $rax   # print memory pointed to by rax as a decimal integer
    |   (gdb) x/x $rax   # print memory pointed to by rax as a hex number
    |   (gdb) x/s $rax   # print memory pointed to by rax as a string
    `----

  - You can set breakpoints at individual instructions using the
    following syntax involving the * symbol from the GDB Quick Guide.
     COMMAND             Effect                                                
    ---------------------------------------------------------------------------
     `break *0x1248f2'   Break at specific instruction address                 
     `break *func+24'    Break at instruction with decimal offset from a label 
     `break *func+0x18'  Break at instruction with hex offset from a label

  A good sign that you are absorbing what's going on is if you can come
  back to `quote_main' a day later, and use GDB commands to quickly find
  the correct index again.


PROBLEM 2A: order2
==================

CODE order2_asm.s
~~~~~~~~~~~~~~~~~

  Examine the code in `order2_asm.s' and compare it to `order2_c.c'.
  The only change that is needed is marked as TODO and involves
  extending the stack to make space for local variables that must be in
  memory.  Examine this code and discuss with lab staff how to grow the
  stack to fit the required local variables.


QUIZ Questions
~~~~~~~~~~~~~~

Stack Space
-----------

  To create enough stack space for 2 integers in x86-64, the stack must
  grow by this amount
  - ( ) 2 bytes
  - ( ) 4 bytes
  - ( ) 8 bytes
  - ( ) 16 bytes


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 rbx 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


Moving data to main memory
--------------------------

  This code appears in `order2_asm.s'.
  ,----
  | 	movl	$17, 0(%rsp)
  | 	movl	$12, 4(%rsp)
  `----
  Which following instructions best describes the sequence
  - ( ) Copies the integer 17 to memory where the stack pointer points
    and the integer 12 to memory 4 bytes about the stack pointer
  - ( ) Copies the value 17 to the stack pointer and then ovewrites that
    with 17+4=21 to the stack pointer which grows the stack
  - ( ) Copies data from memory where the stack pointer points to memory
    address 17 and copies data from 4 bytes above the stack pointer to
    memory address 12
  - ( ) Compares the stack pointer address to 17 and to 12 to determine
    if it should be extended by 4 bytes


PROBLEM 2B: order3
==================

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)
  `----


QUIZ Questions
~~~~~~~~~~~~~~

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


call / callq effects on Stack Pointer
-------------------------------------

  When calling a function via the `call / 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.

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.

Web Accessibility
Author: Chris Kauffman (profk@umd.edu)
Date: 2025-10-18 Sat 10:50