Datarep/Assembly Exercises Section

College students: Attendance at section is required and recorded for all college students. All college students should fill out this attendance form when attending section. For more on the attendance policy and what to do if you miss section refer to the syllabus here and here.

Extension School students: Extension School students are required to self-report weekly section participation using this participation form. There are two ways to participate in section: (1) attend section live (for most students, this is one of the zoom sections, but local students are welcome to attend in-person sections) OR (2) watch a section recording (Canvas > Zoom > Published Recordings). Both participation methods are equally valid towards your participation grade.

In today’s section, we’ll walk through a selection of our data representation exercises and assembly exercises, which are problems taken from prior exams. Also take the opportunity to ask questions about the problem set and class material.

All exercises assume a 64-bit x86-64 architecture unless otherwise stated.

The main subjects of these exercises are:

• DATAREP-1: Size and alignment rules.
• DATAREP-38: Memory layout.
• ASM-1: Assembly properties.
• ASM-3: Assembly and data structures.
• ASM-4: Assembly control flow.
• ASM-12: Assembly and data structures.

DATAREP-1. Sizes and alignments

QUESTION DATAREP-1A. True or false: For any non-array type X, the size of X (sizeof(X)) is greater than or equal to the alignment of type X (alignof(X)).

True. This follows from the array layout rule: arrays are laid out sequentially in memory with no gaps. If the alignment of a type were greater than the size, then the array layout rule would cause element 1 in an array to be misaligned—a contradiction.

The requirement that size ≥ alignment is also mostly true that for array types. The exception is zero-length arrays. Given an array type AT equivalent to T[N], sizeof(AT) == 0, but alignof(AT) == alignof(T).

QUESTION DATAREP-1B. True or false: For any type T, the size of struct Y { T a; char newc; } is greater than the size of T.

True. This follows from the struct layout rule.

QUESTION DATAREP-1C. True or false: For any types T1...Tn (with n ≥ 1), the size of struct Y is greater than the size of struct X, given:

struct X {
    T1 m1;
    ...
    Tn mn;
};

struct Y {
    T1 m1;
    ...
    Tn mn;
    char newc;
};

False. It’s possible for newc to slip into some padding that would otherwise be required to preserve alignment. (For example, let n=2, T1=int, and T2=char.)

QUESTION DATAREP-1D. True or false: For any types T1...Tn (with n ≥ 1), the size of struct Y is greater than the size of union X, given:

union X {
    T1 m1;
    ...
    Tn mn;
};

struct Y {
    T1 m1;
    ...
    Tn mn;
};

False, because of the special case n=1.

QUESTION DATAREP-1E. Assume that structure struct Y { ... } contains K char members and M int members, with K≤M, and nothing else. Write an expression defining the maximum sizeof(struct Y).

4M + 4K. This happens if the chars and ints alternate: C++ will add 3 bytes of padding after every char.

QUESTION DATAREP-1F. Given struct Z { T1 a; T2 b; T3 c; }, which contains no padding, what does (sizeof(T1) + sizeof(T2) + sizeof(T3)) % alignof(struct Z) equal?

0. If the struct contains no padding, then its size equals the sum of the sizes of its members; and the size of any object is a multiple of its alignment.

QUESTION DATAREP-1G. Arrange the following types in increasing order by size. Sample answer: “1 < 2 = 4 < 3” (choose this if #1 has smaller size than #2, which has equal size to #4, which has smaller size than #3).

1. char
2. struct minipoint { uint8_t x; uint8_t y; uint8_t z; }
3. int
4. unsigned short[1]
5. char**
6. double[0]

#6 < #1 < #4 < #2 < #3 < #5. The sizes are:

1. sizeof(char) == 1 (for all C++ implementations no matter what!)
2. sizeof(minipoint) == 3 (no need for padding)
3. sizeof(int) == 4
4. sizeof(unsigned short[1]) == 1 * sizeof(unsigned short) == 2
5. sizeof(char**) == 8
6. sizeof(double[0]) == 0 * sizeof(double) == 0 (tricky)

DATAREP-38. Memory layout

The following code computes a Fibonacci number.

#include <cerrno>
#include <getopt.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <unistd.h>

// copied from <cstdio> for your reference:
#define EOF (-1)

// copied from <getopt.h> for your reference:
extern int optind;

static void usage() {
    fprintf(stderr, "Usage: ./fib NUMBER\n");
    exit(1);
}

unsigned long fib(unsigned long n) {
    if (n < 2) {
        return n;
    } else {
        unsigned long tmp1 = fib(n - 1);
        unsigned long tmp2 = fib(n - 2);
        return tmp1 + tmp2;
    }
}

int main(int argc, char *argv[]) {
    // process command line options
    char ch;
    while ((ch = getopt(argc, argv, "h")) != EOF) {
        switch (ch) {
        case 'h':
        case '?':
        default:
            usage();
        }
    }

    // skip processed options
    argc -= optind;
    argv += optind;

    // require 1 argument
    if (argc != 1) {
        usage();
    }

    // parse argument
    unsigned long n = strtoul(strdup(argv[0]), nullptr, 10);
    if (n == 0 && errno == EINVAL) {
        usage();
    }

    // print fib(n)
    unsigned long f = fib(n);
    printf("fib(%lu) = %lu\n", n, f);
}

QUESTION DATAREP-38A. What are fib(0), fib(1), and fib(2)?

0, 1, and 1, respectively. Since 0 < 2 and 1 < 2, line 18 means fib(0) == 0 and fib(1) == 1. fib(2) equals fib(0) + fib(1), which is 0 + 1 == 1.

QUESTION DATAREP-38B. What are sizeof(fib(0)), sizeof(fib(1)), and sizeof(fib(2))?

8, 8, and 8. sizeof(EXPRESSION) means the same thing as sizeof(TYPE OF EXPRESSION), which here is sizeof(unsigned long) == 8.

For parts C–H, select from the list below the part of memory that best describes where you will find the object.

1. In the heap
2. In the stack
3. Between the heap and the stack
4. In a read-only data segment
5. In a code segment
6. In a read/write data segment

QUESTION DATAREP-38C. The string "fib(%lu) = %lu\n" (line 58).

This is a C string constant, which has type const char*. These kinds of objects are stored in read-only data segments (#4).

QUESTION DATAREP-38D. optind (line 12)

This object is global, because it’s declared outside of any function. All global objects are stored in a global data segment. This object’s type is int, so it is writable, and is stored in a read/write data segment (#6).

QUESTION DATAREP-38E. tmp1 (line 23)

tmp1 is a local variable, and all local variables are stored on the stack (#2).

QUESTION DATAREP-38F. fib (lines 19-27)

This function is stored in the executable’s code segment (#5).

QUESTION DATAREP-38G. strdup (line 51)

All functions are represented as instructions stored in memory. Those instructions are typically stored in a code segment (#5). However, strdup is a library function, and if such functions are defined in a shared library, they are often loaded at an address between the heap and the stack (#3).

QUESTION DATAREP-38H. The string being passed to strtoul (line 51). (Read the manual page for strdup first!)

The argument to strtoul is returned from strdup, and strdup “returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc”. Thus, this argument is a pointer into the heap (#1).

QUESTION DATAREP-38I. Does this program contain a memory leak?

Yes! The string allocated and returned by strdup is never freed, so it is leaked, and a leak-checking sanitizer will warn about it.

QUESTION DATAREP-38J. Consider a call to fib(10) that was called from fib(11). Will fib(10)’s tmp1 variable have a larger, smaller, or equal address as fib(11)’s?

Smaller. Stacks grow down, so local variables in a callee function will have smaller addresses than local variables in the caller.

ASM-1. Assembly properties

Here’s some assembly produced by compiling a C program. (The instructions are labeled with byte offsets for your convenience.)

             .globl  f
             .align  16, 0x90
             .type   f,@function
f:
   0:        movl    $1, %r8d
   6:        jmp     b <f+0xb>

   8:        incl    %r8d

   b:        movl    %r8d, %ecx
   e:        imull   %ecx, %ecx
  11:        movl    $1, %edx

  16:        movl    %edx, %edi
  18:        imull   %edi, %edi
  1b:        movl    $1, %esi

  20:        movl    %esi, %eax
  22:        imull   %eax, %eax
  25:        addl    %edi, %eax
  27:        cmpl    %ecx, %eax
  29:        je      40 <f+0x40>
  2b:        cmpl    %edx, %esi
  2d:        leal    1(%rsi), %eax
  30:        movl    %eax, %esi
  32:        jl      20 <f+0x20>
  34:        cmpl    %r8d, %edx
  37:        leal    1(%rdx), %eax
  3a:        movl    %eax, %edx
  3c:        jl      16 <f+0x16>
  3e:        jmp     8 <f+0x8>

  40:        pushq   %rax
  41:        movl    $.L.str, %edi
  46:        xorl    %eax, %eax
  48:        callq   printf
  4d:        movl    $1, %eax
  52:        popq    %rcx
  53:        retq

             .type   .L.str,@object
.L.str:
             .asciz  "%d %d\n"
             .size   .L.str, 7

QUESTION ASM-1A. How many arguments might this function take? List all that apply.

1. 0
2. 1
3. 2
4. 3 or more

All are valid answers! The function does not use any parameters, but it might take parameters it doesn’t use.

We know that the function doesn’t use its parameters because none of the parameter registers (%rdi, %rsi, %rdx, %rcx, %r9, %r10) are used before they are defined, and the function doesn’t access its caller’s stack space either (as the function might if it took arguments that were passed on the stack). (Although %rdi, %rsi, %rdx, and %rcx are used in the function—for instance, at offset b—their entry-time values are not used: each register is assigned to some value on its first use.)

QUESTION ASM-1B. What might this function return? List all that apply.

1. 0
2. 1
3. −1
4. Its first argument, whatever that argument is
5. A square number other than 0 or 1
6. None of the above

It can only return 1. The only ret instruction in the function is its last instruction (at offset 53), and the immediately preceding assignment to %rax sets it to the constant 1 (at offset 4d).

QUESTION ASM-1C. Which callee-saved registers does this function save and restore? List all that apply.

1. %rax
2. %rbx
3. %rcx
4. %rdx
5. %rbp
6. %rsi
7. %rdi
8. None of the above

The callee-saved registers are %rbx, %rbp, %rsp, and %r12-%r15. The code does not modify any of these registers, so it doesn’t need to “save and restore” them either—and it does not.

QUESTION ASM-1D. This function handles signed integers. If we changed the C source to use unsigned integers instead, which instructions would change? List all that apply.

1. movl
2. imull
3. addl
4. cmpl
5. je
6. jl
7. popq
8. None of the above

jl. The jl instruction uses signed less-than; for unsigned less-than, jb would be used.

We accepted imull or not! Although x86 imull is signed, as used in C it behaves equivalently to the nominally-unsigned mull, and some compilers use imull for both kinds of integer. From the Intel manuals:

“[These] forms [of imul] may also be used with unsigned operands because the lower half of the product is the same regardless if the operands are signed or unsigned. The CF and OF flags, however, cannot be used to determine if the upper half of the result is non-zero.”

QUESTION ASM-1E. What might this function print? List all that apply.

1. 0 0
2. 1 1
3. 3 4
4. 4 5
5. 6 8
6. None of the above

Choice #3 (3 4) only. The function searches for a solution to x2 + y2 == z2, under the constraint that x ≤ y. When it finds one, it prints x and y and then returns. It always starts from 1 1 and increments x and y one at a time, so it can only print 3 4.

ASM-3. Assembly and Data Structures

For each code sample below, indicate the most likely type of the data being accessed. (If multiple types are equally likely, just pick one.)

QUESTION ASM-3A. movzbl %al, %eax

unsigned char

QUESTION ASM-3B. movl -28(%rbp), %edx

int or unsigned

QUESTION ASM-3C. movsbl -32(%rbp), %eax

[signed] char

QUESTION ASM-3D. movzwl -30(%rbp), %eax

unsigned short

For each code sample below, indicate the most likely data structure being accessed (assume that g_var is a global variable). Be as specific as possible.

QUESTION ASM-3E. movzwl 6(%rdx,%rax,8), %eax

unsigned short in an array of 8-byte structures

QUESTION ASM-3F. movl (%rdx,%rax,4), %eax

Array of ints or unsigned ints

QUESTION ASM-3G.

movzbl 4(%rax), %eax
movsbl %al, %eax

char field from a structure; or the 5th character in a string

For the remaining questions, indicate for what values of the register contents will the jump be taken.

QUESTION ASM-3H.

xorl %eax, %eax
jge LABEL

Always

QUESTION ASM-3I.

testb $1, %eax
jne LABEL

Any odd value (the fact that we're only looking at the lowest byte is pretty irrelevant)

QUESTION ASM-3J.

cmpl %edx, %eax
jl LABEL

When %eax is less than %edx, considered as signed integers

ASM-4. Assembly control flow

The next four questions pertain to the following four code samples.

f1

f1:
       subq    $8, %rsp
       call    callfunc
       movl    %eax, %edx
       leal    1(%rax,%rax,2), %eax
       testb   $1, %dl
       jne     .L3
       movl    %edx, %eax
       shrl    $31, %eax
       addl    %edx, %eax
       sarl    %eax
.L3:
       addq    $8, %rsp
       ret

f2

f2:
       pushq   %rbx
       xorl    %ebx, %ebx
.L3:
       movl    %ebx, %edi
       addl    $1, %ebx
       call    callfunc
       cmpl    $10, %ebx
       jne     .L3
       popq    %rbx
       ret

f3

f3:
       subq    $8, %rsp
       call    callfunc
       subl    $97, %eax
       cmpb    $4, %al
       ja      .L2
       movzbl  %al, %eax
       jmp     *.L4(,%rax,8)
.L4:
       .quad   .L3
       .quad   .L9
       .quad   .L6
       .quad   .L7
       .quad   .L8
.L3:
       movl    $42, %edx
       jmp     .L5
.L6:
       movl    $4096, %edx
       jmp     .L5
.L7:
       movl    $52, %edx
       jmp     .L5
.L8:
       movl    $6440, %edx
       jmp     .L5
.L2:
       movl    $0, %edx
       jmp     .L5
.L9:
       movl    $61, %edx
.L5:
       movl    $.LC0, %esi
       movl    $1, %edi
       movl    $0, %eax
       call    __printf_chk
       addq    $8, %rsp
       ret
.LC0:
       .string "Sum = %d\n"

f4

f4:
       subq    $40, %rsp
       movl    $1, (%rsp)
       movl    $0, 16(%rsp)
.L2:
       leaq    16(%rsp), %rsi
       movq    %rsp, %rdi
       call    callfunc
       movl    16(%rsp), %eax
       cmpl    %eax, (%rsp)
       jne     .L2
       addq    $40, %rsp
       ret

Now answer the following questions. Pick the most likely sample; you will use each sample exactly once.

QUESTION ASM-4A. Which sample contains a for loop?

f2

QUESTION ASM-4B. Which sample contains a switch statement?

f3

QUESTION ASM-4C. Which sample contains only an if/else construct?

f1

QUESTION ASM-4D. Which sample contains a while loop?

f4

ASM-12. Assembly and data structures

Consider the following assembly function.

func:
        xorl    %eax, %eax
        cmpb    $0, (%rdi)
        je      .L27
.L26:
        addq    $1, %rdi
        addl    $1, %eax
        cmpb    $0, (%rdi)
        jne     .L26
.L27:
        retq

QUESTION ASM-12A. How many parameters does this function appear to have?

1

QUESTION ASM-12B. What do you suppose the type of that parameter is?

const char* (or const unsigned char*, char*, etc.)

QUESTION ASM-12C. Write C++ code that corresponds to it.

It’s strlen!

int strlen(const char* x) {
    int n = 0;
    for (; *x; ++x)
        ++n;
    return n;
}