Unstructured Control Flow

While the reading for today talked about good C practices, we spent our introductory time together talking about one of the bad parts of C that we should avoid: unstructured control flow. In this series of exercises, we'll get a concrete sense for why unstructured control flow is undesirable in most situations, and then explore a situation where it may be appropriate.

Problem 1: Unstructured Tracing

goto allows us to perform local unstructured jumping between labeled points within a function. For the following program, give stack/heap diagrams for each of the indicated points (1, 2, and 3). Check your work by compiling and running your program!

(Hint: labels of the form label: are just annotations in code. For the purposes of statement-by-statement execution, you should ignore them!)

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

int main(void) {
    int i = 0;
    int *z = (int*) malloc(sizeof(int));
    *z = 2;
    // Point A
    label_a:
        if (i < 5) goto label_b;
        *z *= *z;
        i++;
        // Point B (first time only)
        goto label_a;
    label_b:
        if (*z % 2 == 0)
            goto label_c;
        else
            goto label_d;
    label_c:
        *z += 1;
    label_d:
        i = 0;
    // Point C
    printf("%d %d\n", *z, i);
}

Even more fun than goto: the setjmp and longjmp functions from the standard header setjmp.h provide facilities for performing global unstructured jumps. With setjmp and longjmp, you can save the contents of the stack and magically "return" to that saved point, regardless of where you are in your program!

• int setjmp(jmp_buf env) loads env with values appropriate for remembering the state of the stack at the point of execution of the setjmp function. The function returns 0 on its "initial" invocation (see longjmp).
• void longjmp(jmp_buf env, int value) causes the state of the stack to be restored to the setjmp point corresponding to the jmp_buf call that populated env. Program execution continues as if the corresponding setjmp returned but with value produced rather than 0.

For the following program, give stack/heap diagrams for each of the indicated points (A, B, and C). Check your work by compiling and running your program!

#include <setjmp.h>
#include <stdio.h>

jmp_buf env;

int factorial_maybe(int n) {
    if (n == 0) {
        // Point B
        longjmp(env, 11);
        return 0;
    } else {
        int result = 0;
        if (n == 4) {
            // Point A
            if (!(result = setjmp(env))) {
                result = factorial_maybe(n - 1);
            }
        } else {
            result = factorial_maybe(n - 1);
        }
        return n * result;
    }
}

int main(void) {
    int result = factorial_maybe(5);
    // Point C
}

Problem 2: Exceptions to the Rule

Unstructured control flow like goto and setjmp/longjmp seem strictly inferior to structured control flow constructs. Indeed, we should minimize our usage of these constructs whenever possible. However, there are times in C where goto and setjmp/longjmp are actually useful!

Consider the following program:

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

typedef struct blob {
    char *data;
} blob;

char get_single_char(void) {
    char ch = getchar();    // assumes user enters a single character
    getchar();              // ...and get rid of the newline character!
    return ch;
}

bool init_blob(char ch, blob *b) {
    if (ch == 'x') {
        return false;
    }
    b->data = (char*) malloc(sizeof(char));
    *b->data = ch;
    return true;
}

int main(void) {
    blob b1, b2, b3;
    char ch = get_single_char();
    if (!init_blob(ch, &b1)) {
        printf("First round: entered x, fail!");
        return 0;
    }

    ch = get_single_char();
    if (!init_blob(ch, &b2)) {
        printf("Second round: entered x, fail!");
        return 0;
    }

    ch = get_single_char();
    if (!init_blob(ch, &b3)) {
        printf("Third round: entered x, fail!");
        return 0;
    }

    printf("Results: %c, %c, and %c\n", *b1.data, *b2.data, *b3.data);
    free(b3.data);
    free(b2.data);
    free(b1.data);
    return 0;
}

a. This program has a memory leak! Compile and test this program using -g -fsanitize=address to determine where the memory leak occurs. In a few sentences, describe the situations in which this program leaks memory and why this is the case. b. Give a version of this program (without using gotos) that maintains the intent and (as much as possible) keeps the structure of the code intact. c. Now, starting from the original program, use gotos to minimally change the code to make it memory safe. d. In a few sentences, compare and contrast the programs that you receive from parts (b) and (c). What are the strengths and weaknesses of each approach as you see them. e. Suppose someone told you the following:

> `goto`s are evil; Dijkstra said so.
> Never use `goto`s.

Would you agree or disagree with this person?
In a few sentences explain how you would respond to this person.