Lists and Pointer Diagrams

As we begin our study of linked lists, it is important we recognize the importance of our memory diagrams in understanding and designing linked list code. Memory diagrams are our lynchpin for moving between high-level intent into low-level code. And with the complexities of non-trivial pointer movement, heap-allocation, and structures, diagrams become more important than ever to ensure that our code matches our intent.

In this lab, we'll go through a number of exercises involving moving between linked list diagrams and code, mirroring how you might use diagrams in real-world coding situations.

Problem 1: Linked Tracing

Assume we have standard definitions of node and list types with associated make functions:

typedef struct node {
    int value;
    struct node *next;
} node;

typedef struct list {
    node *first;
} list;

node* make_node(int value, node *next) {
    node *ret = (node*) malloc(sizeof(node));
    ret->value = value;
    ret->next = next;
    return ret;
}

list* make_list(void) {
    list *ret = (list*) malloc(sizeof(list));
    ret->first = NULL;
    return ret;
}

For each of the following programs, give memory diagrams for each of the following indicated points:

Program 1

int main(void) {
    list *l = make_list();
    node *n1 = make_node(0, NULL);
    node *n2 = make_node(1, NULL);
    // Point A
    n2->next = n1;
    l->first = n2;
    // Point B
    n1->next = make_node(2, make_node(3, NULL));
    l->first = n1;
    // Point C
    return 0;
}

Program 2

void f(int n, list *l) {
    // Point B
    node *n1 = make_node(n, NULL);
    node *n2 = make_node(n+1, NULL);
    node *n3 = make_node(n+2, NULL);
    l->first = n3;
    n3->next = n2;
    n2->next = n1;
}

int main(void) {
    list *l = make_list();
    l->first = make_node(0, make_node(1, NULL));
    // Point A
    f(5, l);
    // Point C
    return 0;
}

Program 3

int main(void) {
    list *l = make_list();
    l->first = make_node(0, make_node(1, make_node(2, NULL)));
    // Point A
    node *n1 = make_node(10, NULL);
    n1->next = l->first;
    l->first = n1;
    // Point B
    node *n2 = make_node(20, n1);
    n1->next = n2;
    // Point C
    return 0;
}

Problem 2: Forth-and-back

Suppose that you have the standard linked list definitions found above. For each set of sequential memory diagrams, give a code snippet that produces those diagrams.

Program 1

// Point A
Stack            Heap
-----            ----
l1 [o]---------->[o]--->[18][o]--->[27][o]--->[32][/]

// Point B
Stack            Heap
-----            ----
l1 [o]---------->[o]--->[18][o]--->[27][o]--->[32][o]--->[80][/]
                          ∧          ∧
n1 [o]--------------------|          |
                                     |
l2 [o]---------->[o]-----------------|

// Point C
Stack            Heap
-----            ----
l1 [o]---------->[o]--->[18][o]--->[27][o]--->[32][o]--->[80][/]
                          ∧          ∧         ∧
n1 [o]--------------------|          |         |
                                     |         |
l2 [o]-------------------------------|         |
                                     |         |
l2 [o]---------->[o]-----------------|         |
                                               |
n2 [o]-----------------------------------------|

Program 2

// Point A
Stack           Heap
-----           ----
l1 [o]--------->[o]--->[0][/]

// Point B
Stack           Heap
-----           ----
l1 [o]--------->[o]--->[0][/]
                        ^
n2 [o]------------------|

n3 [o]------------------------->[1][/]

n4 [o]------------------------------------>[2][/]

// Point C
Stack           Heap
-----           ----
l1 [o]--------->[o]-------------------------|      [0][/]
                                            |       ∧
n2 [o]----------------------------------------------|
                                            |       |
n3 [o]------------------------->[1][o]------|-------|     
                                 ∧          ∨
n4 [o]------------------------------------>[2][o]
                                 |             |
                                 |-------------|

Program 3: Concrete Motions

Each of the following programs represents a concrete instance of one of the linked list motions we will learn about in our next class. As a preview, for each of the following programs, give memory diagrams for each of the following indicated points. In a sentence, describe what behavior the program performed.

Program 1

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, NULL));
    // Point A
    node *n = make_node(0, NULL);
    n->next = l->first;
    l->first = n;
    // Point B 
    return 0;
}

Program 2

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, make_node(3, NULL)));
    // Point A
    node *cur = l->first;
    node *n1 = cur->next;
    cur = n1;
    node *n2 = cur->next;
    cur = n2;
    node *n3 = cur->next;
    cur = n3;
    // Point B
    return 0;
}

Program 3

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, make_node(3, NULL)));
    node *n = l->first;
    node *m = l->first->next;
    // Point A
    n->next = m->next;
    // Point B
    return 0;
}

Program 4: Oh Yeah, Safety

We have introduced function that heap-allocate lists and nodes, but have not discussed how to deallocate these structures! Doing so requires the linked list motions we'll introduce in tomorrow's class. For now, let's introduce a common, errorenous approach to cleaning up a list, a new tool for detecting memory leaks, and how we might fix the resulting memory leak on a concrete linked list instance.

Consider the following code snippet (with suitable auxiliary definitions for node, list, make_node, and make_list):

#include <stdlib.h>

// Definitions of node and list structures and associated functions...

int main(void) {
    list *l = make_list();
    l->first = make_node(1, make_node(2, make_node(3, NULL)));
    // Point A
    free(l);
    return 0;
}

Draw a memory diagram representing the state of memory at Point A in the code.
Observe that the next line calls the stdlib.h free function which frees a heap-allocated chunk of memory. This ought to clean up the memory and indeed, try compiling and running the program: it seems to complete without errors. However, there is more than what meets the eye here!

Let's use a dynamic analysis tool, AddressSanitizer (ASan), to show that there is actually a memory leak present! ASan is built into recent versions of GCC and Clang and is accessible via the compiler flag, -fsanitize=address. We must compile our program in debug mode, i.e., with -g, and this additional flag to use ASan. ASan is then injected into our code and executes alongside our program. If ASan detects any memory errors, e.g., memory leaks, it will throw an error at runtime and report relevant information.

If you stored your code in a file called leak.c, use the following clang invocation to compile leak.c to leak with ASan support:
```
$> clang leak.c -o leak -g -fsanitize=address -fno-omit-frame-pointer
```
After running your program, you should observe 3 detected memory leaks. Here is an example of one such leak you should encounter. The general form of the error should be the same, but the specific line numbers and addresses will likely be different.
```
Direct leak of 16 byte(s) in 1 object(s) allocated from:
#0 0x7f3eb3881867 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
#1 0x559eb36bc205 in make_node /home/osera/csc161-old-materials/repo/labs/16-linked-lists-setup/leak.c:13
#2 0x559eb36bc302 in main /home/osera/csc161-old-materials/repo/labs/16-linked-lists-setup/leak.c:27
#3 0x7f3eb35cefcf in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
```
This error reports (a) the size of the leaked chunk of memory and (b) a stack trace capturing when and where the leaked memory was initially allocated.

Using this error report, describe in a few sentences:

a. What did the free(l) call actually free? b. What did the free(l) call not free that was leaked?
Fix the code snippet so that it allocates the linked list of three elements but no longer leaks memory. When you rerun the code, it should execute without ASan reporting errors.

CSC 161 Readings (Fall 2023)

Lists and Pointer Diagrams

Problem 1: Linked Tracing

Problem 2: Forth-and-back

Program 3: Concrete Motions

Program 4: Oh Yeah, Safety