Computer Systems Fundamentals

            call_return.c
        
C Function with No Parameters or Return Value

#include <stdio.h>

void f(void);

int main(void) {
    printf("calling function f\n");
    f();
    printf("back from function f\n");
    return 0;
}

void f(void) {
    printf("in function f\n");
}

        
            call_return.broken.s
        

        
simple example of returning from a function
loops because main does not save return address



    
main:
    la   $a0, string0   # printf("calling function f\n");
    li   $v0, 4
    syscall

    jal  f              # set $ra to following address

    la   $a0, string1   # printf("back from function f\n");
    li   $v0, 4
    syscall

    li   $v0, 0         # fails because $ra changes since main called
    jr   $ra            # return from function main


f:
    la   $a0, string2   # printf("in function f\n");
    li   $v0, 4
    syscall
    jr   $ra            # return from function f


    .data
string0:
    .asciiz "calling function f\n"
string1:
    .asciiz "back from function f\n"
string2:
    .asciiz "in function f\n"

        
            call_return_raw.s
        

        
simple example of placing return  address on stack
note stack grows down



    
main:
    addi $sp, $sp, -4    # move stack pointer down to make room
    sw   $ra, 0($sp)    # save $ra on $stack

    la   $a0, string0   # printf("calling function f\n");
    li   $v0, 4
    syscall

    jal  f              # set $ra to following address

    la   $a0, string1   # printf("back from function f\n");
    li   $v0, 4
    syscall

    lw   $ra, 0($sp)    # recover $ra from $stack
    addi $sp, $sp, 4    # move stack pointer back to what it was

    li   $v0, 0         # return 0 from function main
    jr   $ra            #


f:
    la   $a0, string2   # printf("in function f\n");
    li   $v0, 4
    syscall
    jr   $ra            # return from function f


    .data
string0:
    .asciiz "calling function f\n"
string1:
    .asciiz "back from function f\n"
string2:
    .asciiz "in function f\n"

        
            call_return.s
        

        
simple example of placing return  address on stack
begin, end, push pop are pseudo-instructions provided by mipsy but not spim



    
main:
    push $ra            # save $ra on $stack

    la   $a0, string0   # printf("calling function f\n");
    li   $v0, 4
    syscall

    jal  f              # set $ra to following address

    la   $a0, string1   # printf("back from function f\n");
    li   $v0, 4
    syscall

    pop $ra             # recover $ra from $stack

    li   $v0, 0         # return 0 from function main
    jr   $ra            #


# f is a leaf function so it doesn't need an epilogue or prologue
f:
    la   $a0, string2   # printf("in function f\n");
    li   $v0, 4
    syscall
    jr   $ra            # return from function f


    .data
string0:
    .asciiz "calling function f\n"
string1:
    .asciiz "back from function f\n"
string2:
    .asciiz "in function f\n"

        
            return_answer.c
        
simple example of returning a value from a function

#include <stdio.h>

int answer(void);

int main(void) {
    int a = answer();
    printf("%d\n", a);
    return 0;
}

int answer(void) {
    return 42;
}

        
            return_answer.s
        

        
simple example of returning a value from a function
note storing of return address $ra


code for function main

    
main:
    begin               # move frame pointer
    push  $ra           # save $ra onto stack

    jal   answer        # call answer(), return value will be in $v0

    move  $a0, $v0      # printf("%d", a);
    li    $v0, 1        #
    syscall             #

    li    $a0, '\n'     # printf("%c", '\n');
    li    $v0, 11       #
    syscall             #

    pop   $ra           # recover $ra from stack
    end                 # move frame pointer back

    li    $v0, 0        # return
    jr    $ra           #


# code for function answer
answer:
    li   $v0, 42        # return 42
    jr   $ra            #

        
            more_calls.c
        
example of function calls

#include <stdio.h>

int sum_product(int a, int b);
int product(int x, int y);

int main(void) {
    int z = sum_product(10, 12);
    printf("%d\n", z);
    return 0;
}

int sum_product(int a, int b) {
    int p = product(6, 7);
    return p + a + b;
}

int product(int x, int y) {
    return x * y;
}

        
            more_calls.s
        

        
example of function calls
note storing of return address $a0, $a1 and $ra on stack



    
main:
    begin                # move frame pointer
    push  $ra            # save $ra onto stack

    li   $a0, 10         # sum_product(10, 12);
    li   $a1, 12
    jal  sum_product

    move $a0, $v0        # printf("%d", z);
    li   $v0, 1
    syscall

    li   $a0, '\n'       # printf("%c", '\n');
    li   $v0, 11
    syscall

    pop   $ra            # recover $ra from stack
    end                  # move frame pointer back

    li   $v0, 0          # return 0 from function main
    jr   $ra             # return from function main



sum_product:
    begin                # move frame pointer
    push  $ra            # save $ra onto stack
    push  $s0            # save $s0 onto stack
    push  $s1            # save $s1 onto stack

    move  $s0, $a0       # preserve $a0 for use after function call
    move  $s1, $a1       # preserve $a1 for use after function call

    li    $a0, 6         # product(6, 7);
    li    $a1, 7
    jal   product



    add   $v0, $v0, $s0  # add a and b to value returned in $v0
    add   $v0, $v0, s1  # and put result in $v0 to be returned

    pop   $s1            # recover $s1 from stack
    pop   $s0            # recover $s0 from stack
    pop   $ra            # recover $ra from stack
    end                  # move frame pointer back

    jr    $ra            # return from sum_product


product:                # product doesn't call other functions
                        # so it doesn't need to save any registers
    mul  $v0, $a0, $a1  # return argument * argument 2
    jr   $ra            #

        
            two_powerful.c
        
recursive function which prints first 20 powers of two in reverse

#include <stdio.h>

void two(int i);

int main(void) {
    two(1);
}

void two(int i) {
    if (i < 1000000) {
        two(2 * i);
    }
    printf("%d\n", i);
}

        
            two_powerful.s
        

        
simple example of placing return address ($ra) and $a0 on the stack
recursive function which prints first 20 powers of two in reverse



    
main:
    begin               # move frame pointer
    push  $ra           # save $ra onto stack

    li    $a0, 1
    jal   two           # two(1);

    pop   $ra           # recover $ra from stack
    end                 # move frame pointer back

    li    $v0, 0        # return 0
    jr    $ra           #


two:
    begin               # move frame pointer
    push  $ra           # save $ra onto stack
    push  $s0           # save $s0 onto stack

    move  $s0, $a0

    bge   $a0, 1000000, two_end_if
    mul   $a0, $a0, 2
    jal   two
two_end_if:

    move  $a0, $s0
    li    $v0, 1        # printf("%d");
    syscall

    li    $a0, '\n'     # printf("%c", '\n');
    li    $v0, 11
    syscall

    pop   $s0           # recover $s0 from stack
    pop   $ra           # recover $ra from stack
    end                 # move frame pointer back

    jr    $ra           # return from two

        
            squares.c
        

        
store first 10 squares into an array which is a local variable then print them from array



    
#include <stdio.h>

int main(void) {
    int squares[10];
    int i = 0;
    while (i < 10) {
        squares[i] = i * i;
        i++;
    }
    i = 0;
    while (i < 10) {
        printf("%d", squares[i]);
        printf("%c",'\n');
        i++;
    }
    return 0;
}

        
            squares.s
        

        
i in register $t0
registers $t1, and $t2, used to hold temporary results



    
main:
    begin               # move frame pointer
    addi $sp, $sp, -40  # move stack pointer down to make room to store array numbers on stack

    li   $t0, 0         # i = 0
loop0:
    bge  $t0, 10, end0  # while (i < 10) {

    mul  $t1, $t0, 4    #    calculate &numbers[i]
    add  $t2, $t1, $sp  #
    mul  $t3, $t0, $t0  #    calculate i * i
    sw   $t3, ($t2)     #    store in array

    addi $t0, $t0, 1    #    i++;
    b    loop0          # }
end0:

    li   $t0, 0         # i = 0
loop1:
    bge  $t0, 10, end1  # while (i < 10) {

    mul  $t1, $t0, 4
    add  $t2, $t1, $sp  #   calculate &numbers[i]

    lw   $a0, ($t2)     #   load numbers[i] into $a0
    li   $v0, 1         #   printf("%d", numbers[i])
    syscall             #

    li   $a0, '\n'      #   printf("%c", '\n');
    li   $v0, 11        #
    syscall             #

    addi $t0, $t0, 1    #   i++
    b    loop1          # }
end1:

    addi $sp, $sp, 40   # move stack pointer back up to what it was when main called
    end                 # move frame pointer back

    li   $v0, 0         # return 0
    jr   $ra            #

        
            frame_pointer.c
        
example of function where frame pointer useful
because stack grows during function execution

#include <stdio.h>

void f(int a) {
    int length;
    scanf("%d", &length);
    int array[length];
    // ... more code ...
    printf("%d\n", a);
}

        
            frame_pointer.broken.s
        
example stack growing during function execution
breaking the function return

f:
    addi $sp, $sp, -8    # move stack pointer down to make room
    sw   $ra, 4($sp)     # save $ra on $stack
    sw   $a0, 0($sp)     # save $a0 on $stack

    li   $v0, 5          # scanf("%d", &length);
    syscall

    mul  $v0, $v0, 4     # calculate array size
    sub  $sp, $sp, $v0   # move stack_pointer down to hold array

    # ...

                        # breaks because stack pointer moved down to hold array
                        # so we won't restore the correct value
    lw   $ra, 4($sp)    # restore $ra from $stack
    addi $sp, $sp, 8    # move stack pointer back up to what it was when main called

    jr   $ra            # return from f

        
            frame_pointer.s
        
using a frame pointer to handle stack growing during function execution

f:
    begin                # move frame pointer
    push  $ra            # save $ra on stack

    li    $v0, 5         # scanf("%d", &length);
    syscall

    mul   $v0, $v0, 4    # calculate array size
    sub   $sp, $sp, $v0  # move stack_pointer down to hold array

    # ... more code ...

    pop  $ra             # restore $ra
    end
    jr   $ra             # return

        
            strlen_array.c
        

        
calculate the length of a string using a strlen like function



    
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
    while (s[length] != 0) {
        length++;
    }
    return length;
}

        
            strlen_array.simple.c
        

        
calculate the length of a string using a strlen like function



    
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
loop:;
    if (s[length] == 0) goto end;
       length++;
    goto loop;
end:;
    return length;
}

        
            strlen_array.s
        

        
simple example of placing return address ($ra) on the stack
calculate the length of a string using a strlen like function



    
main:
    begin               # move frame pointer
    push  $ra           # save $ra onto stack

    la   $a0, string    # my_strlen("Hello");
    jal  my_strlen

    move $a0, $v0       # printf("%d", i);
    li   $v0, 1
    syscall

    li   $a0, '\n'      # printf("%c", '\n');
    li   $v0, 11
    syscall

    pop   $ra           # recover $ra from stack
    end                 # move frame pointer back

    li   $v0, 0         # return 0 from function main
    jr   $ra            #


my_strlen:              # length in t0, s in $a0
    li   $t0, 0
loop:                   # while (s[length] != 0) {
    add  $t1, $a0, $t0  #   calculate &s[length]
    lb   $t2, ($t1)     #   load s[length] into $t2
    beq  $t2, 0, end    #
    addi $t0, $t0, 1    #   length++;
    b    loop           # }
end:
    move $v0, $t0       # return length
    jr   $ra            #


    .data
string:
    .asciiz "Hello"

        
            strlen_pointer.c
        

        
calculate the length of a string using a strlen like function



    
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello Andrew");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
    while (*s != 0) {
        length++;
        s++;
    }
    return length;
}

        
            strlen_pointer.simple.c
        

        
calculate the length of a string using a strlen like function



    
#include <stdio.h>

int my_strlen(char *s);

int main(void) {
    int i = my_strlen("Hello Andrew");
    printf("%d\n", i);
    return 0;
}

int my_strlen(char *s) {
    int length = 0;
loop:;
    if (*s == 0) goto end;
        length++;
        s++;
        goto loop;
end:;
    return length;
}

        
            strlen_pointer.s
        

        
simple example of placing return address ($ra) on the stack
calculate the length of a string using a strlen like function



    
main:
    begin               # move frame pointer
    push  $ra           # save $ra onto stack

    la   $a0, string    # my_strlen("Hello");
    jal  my_strlen

    move $a0, $v0       # printf("%d", i);
    li   $v0, 1
    syscall

    li   $a0, '\n'      # printf("%c", '\n');
    li   $v0, 11
    syscall

    pop   $ra           # recover $ra from stack
    end                 # move frame pointer back

    li   $v0, 0         # return 0 from function main
    jr   $ra            #


my_strlen:              # length in t0, s in $a0
    li   $t0, 0
loop:                   #
    lb   $t1, ($a0)    # load *s into $t1
    beq  $t1, 0, end    #
    addi $t0, $t0, 1    # length++
    addi $a0, $a0, 1    # s++
    b    loop           #
end:
    move $v0, $t0       # return length
    jr   $ra            #


    .data
string:
    .asciiz "Hello Andrew"

        
            stack_inspect.c
        

        

    
#include <stdio.h>
#include <stdint.h>

/*
$ clang --version
Ubuntu clang version 11.0.0-2~ubuntu20.04.1
$ clang stack_inspect.c
$ a.out
 0: Address 0x7ffe7d80defc contains        3     <- e[0]
 1: Address 0x7ffe7d80df00 contains        7     <- e[1]
 2: Address 0x7ffe7d80df04 contains        5     <- d
 3: Address 0x7ffe7d80df08 contains        9     <- c
 4: Address 0x7ffe7d80df0c contains       2a     <- b
 5: Address 0x7ffe7d80df10 contains 7d80df30     <- saved frame pointer of main (lower 32 bits)
 6: Address 0x7ffe7d80df14 contains     7ffe     <- saved frame pointer of main (upper 32 bits)
 7: Address 0x7ffe7d80df18 contains   4011d3     <- saved return address of main (lower 32 bits)
 8: Address 0x7ffe7d80df1c contains        0     <- saved return address of main (upper 32 bits)

 9: Address 0x7ffe7d80df20 contains 7d80e020     <- STACK pointer (???) (lower 32 bits)
10: Address 0x7ffe7d80df24 contains     7ffe     <- STACK pointer (???) (upper 32 bits)
11: Address 0x7ffe7d80df28 contains        9     <- a
12: Address 0x7ffe7d80df2c contains        0     <- padding (for next 64-bit pointer ^)
13: Address 0x7ffe7d80df30 contains        0     <- saved frame pointer of _start (lower 32 bits)
14: Address 0x7ffe7d80df34 contains        0     <- saved frame pointer of _start (upper 32 bits)
15: Address 0x7ffe7d80df38 contains 9fbb30b3     <- saved return address of _start (lower 32 bits)
16: Address 0x7ffe7d80df3c contains     7f98     <- saved return address of _start (upper 32 bits)
17: Address 0x7ffe7d80df40 contains       71     <- ???
18: Address 0x7ffe7d80df44 contains        0     <- ???
19: Address 0x7ffe7d80df48 contains 7d80e028     <- source information
20: Address 0x7ffe7d80df4c contains     7ffe     <- source information

$ gcc --version
gcc (Ubuntu 10.3.0-1ubuntu1~20.04) 10.3.0
$ gcc stack_inspect.c
$ a.out                                          # GCC stores local arrays first in the stack, so some things are missing from the start of the output.
                                           9     <- c
                                          2a     <- b
                                                 <- TEXT pointer (???)
                                                 <- TEXT pointer (???)
                                           0     <- padding (for next 64-bit pointer ^)
                                           5     <- d
 0: Address 0x7ffccc6e6e90 contains        3     <- e[0]
 1: Address 0x7ffccc6e6e94 contains        7     <- e[1]
 2: Address 0x7ffccc6e6e98 contains f08e2f00     <- ???
 3: Address 0x7ffccc6e6e9c contains 8c526a01     <- ???
 4: Address 0x7ffccc6e6ea0 contains cc6e6ec0     <- saved frame pointer of main (lower 32 bits)
 5: Address 0x7ffccc6e6ea4 contains     7ffc     <- saved frame pointer of main (upper 32 bits)
 6: Address 0x7ffccc6e6ea8 contains 11c6a221     <- saved return address of main (lower 32 bits)
 7: Address 0x7ffccc6e6eac contains     5582     <- saved return address of main (upper 32 bits)

 8: Address 0x7ffccc6e6eb0 contains cc6e6fb0     <- STACK pointer (???) (lower 32 bits)
 9: Address 0x7ffccc6e6eb4 contains     7ffc     <- STACK pointer (???) (upper 32 bits)
10: Address 0x7ffccc6e6eb8 contains        0     <- padding (for next 64-bit pointer ^)
11: Address 0x7ffccc6e6ebc contains        9     <- a
12: Address 0x7ffccc6e6ec0 contains        0     <- saved frame pointer of _start (lower 32 bits)
13: Address 0x7ffccc6e6ec4 contains        0     <- saved frame pointer of _start (upper 32 bits)
14: Address 0x7ffccc6e6ec8 contains 6f6d70b3     <- saved return address of _start (lower 32 bits)
15: Address 0x7ffccc6e6ecc contains     7fba     <- saved return address of _start (upper 32 bits)
16: Address 0x7ffccc6e6ed0 contains       71     <- ???
17: Address 0x7ffccc6e6ed4 contains        0     <- ???
18: Address 0x7ffccc6e6ed8 contains cc6e6fb8     <- source information
19: Address 0x7ffccc6e6edc contains     7ffc     <- source information
20: Address 0x7ffccc6e6ee0 contains 6f898618     <- ??? (upper 32 bits)
*/

void f(int b, int c) {
    int d = 5;
    uint32_t e[2] = { 3, 7 };

    for (int i = 0; i < 20; i++)
        printf("%2d: Address %p contains %8x\n", i, &e[i], e[0 + i]);
}

int main(void) {
    int a = 9;
    f(42, a);
    return 0;
}

        
            invalid0.c
        

        



Run at CSE like this


$ clang -Wno-everything invalid0.c -o invalid0
$ ./invalid0
42 77 77 77 77 77 77 77 77 77






    
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int a[10];
    int b[10];
    printf("a[0] is at address %p\n", &a[0]);
    printf("a[9] is at address %p\n", &a[9]);
    printf("b[0] is at address %p\n", &b[0]);
    printf("b[9] is at address %p\n", &b[9]);

    for (int i = 0; i < 10; i++) {
        a[i] = 77;
    }

    // loop writes to b[10] .. b[12] which don't exist -
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // b[12] is stored where a[0] is stored
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // b[10] is stored where a[0] is stored

    for (int i = 0; i <= 12; i++) {
        b[i] = 42;
    }

    // prints 42 77 77 77 77 77 77 77 77 77 on x86_64/Linux
    // prints 42 42 42 77 77 77 77 77 77 77 at CSE
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

        
            invalid1.c
        
Run at CSE like this

$ clang -Wno-everything invalid1.c -o invalid1
$ ./invalid1
i is at address 0x7ffe2c01cd58
a[0] is at address 0x7ffe2c01cd30
a[9] is at address 0x7ffe2c01cd54
a[10] would be stored at address 0x7ffe2c01cd58

doesn't terminate

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int i;
    int a[10];
    printf("i is at address %p\n", &i);
    printf("a[0] is at address %p\n", &a[0]);
    printf("a[9] is at address %p\n", &a[9]);
    printf("a[10] would be stored at address %p\n", &a[10]);

    // loop writes to a[10] .. a[11] which don't exist -
    // but on CSE servers  (clang 7.0 x86_64/Linux)
    // i would be stored where a[11] is stored

    for (i = 0; i <= 11; i++) {
        a[i] = 0;
    }

    return 0;
}

        
            invalid2.c
        
Run at CSE like this

$ clang -Wno-everything  invalid2.c -o invalid2
$ ./invalid2
answer=42

#include <stdio.h>

void f(int x);

int main(void) {
    int answer = 36;
    printf("answer is stored at address %p\n", &answer);

    f(5);
    printf("answer=%d\n", answer); // prints 42 not 36

    return 0;
}

void f(int x) {
    int a[10];

    // a[18] doesn't exist
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // variable answer in main happens to be where a[19] would be

    printf("a[18] would be stored at address %p\n", &a[18]);

    a[18] = 42;
}

        
            invalid3.c
        

        



Run at CSE like this


$ clang -Wno-everything invalid3.c -o invalid3
$ ./invalid3

I hate you.
$




    
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

void f(void);

int main(void) {
    f();

    printf("I love you and will never say,\n");
    printf("I hate you.\n");

    return 0;
}

void f(void) {
    uint64_t a[1];

#ifdef __clang__
#if __clang_major__ >= 16
#error "Don't know the correct offset for this clang version"
#elif __clang_major__ >= 14
    a[2] += 14;
#elif __clang_major__ >= 4
    a[2] += 17;
#elif __clang_major__ == 3
#if __clang_minor__ >= 5
    a[2] += 17;
#elif __clang_minor__ >= 4
    a[2] += 15;
#else
// clang 3.0-3.3 are broken on godbolt.org
#error "Don't know the correct offset for this clang version"
#endif
#else
// clang <3.0 are not avalible on godbolt.org
#error "Don't know the correct offset for this clang version"
#endif
#else
#error "This program must be compiled with clang"
#endif

    // function f has it return address on the stack
    // the call of function f from main should return to
    // the next statement which is:  printf("I love you and will never say,\n");
    //
    // on CSE servers  (clang 11.0 x86_64/Linux)
    // f's return address is stored where a[2] would be
    //
    // so changing a[2] changes where the function returns
    //
    // adding 17 to a[12] happens to cause it to return 2 statements later
    // at:  printf("I hate you.\n");
}

        
            invalid4.c
        

        



Run at CSE like this


$ clang invalid4.c -o invalid4
$ ./invalid4
authenticated is at address 0xff94bf44
password is at address 0xff94bf3c

Enter your password: 123456789

Welcome. You are authorized.
$




    
#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
    int authenticated = 0;
    char password[8];

    printf("authenticated is at address %p\n", &authenticated);
    printf("password[8] would be at address %p\n", &password[8]);

    printf("Enter your password: ");
    int i = 0;
    int ch = getchar();
    while (ch != '\n' && ch != EOF) {
        password[i] = ch;
        ch = getchar();
        i = i + 1;
    }
    password[i] = '\0';

    if (strcmp(password, "buffalo") == 0) {
        authenticated = 1;
    }

    // a password longer than 8 characters will overflow the array password
    // on CSE servers  (clang 7.0 x86_64/Linux)
    // the variable authenticated is at the address where
    // where password[8] would be and gets overwritten
    //
    // This allows access without knowing the correct password

    if (authenticated) {
        printf("Welcome. You are authorized.\n");
    } else {
        printf("Welcome. You are unauthorized.  Your death will now be implemented.\n");
        printf("Welcome. You will experience a tingling sensation and then death. \n");
        printf("Remain calm while your life is extracted.\n");
    }

    return 0;
}