Putting Ownership Into Practice

Each of the subsequent programs possesses a memory leak. Lets use the ownership memory management discipline discussed in the reading to understand and, ultimately, fix these programs.

For this lab, you will turn in three debugged programs, prog1.c, prog2.c, and prog3.c. For each program:

1. Identify the source of the memory leak, using a comment at the line where the leak occurs. Explain in a comment why the leak occurs, using a sentence or two.
2. For each pointer in the program, identify if that pointer is an owning pointer or a borrowing pointer for that chunk of memory. Along the way, also identify any points in the program where ownership transitions between pointers.
3. Once you have identified the appropriate owners of the leaked memory, modify the code so that the chunk is freed through the owning pointer before that pointer is deallocated.

Program 1

// prog1.c
#include <stdio.h>
#include <stdlib.h>

int* make_blob() {
    int *ret = (int*) malloc(sizeof(int));
    *ret = 0;
    return ret;
}

void mutate(int *v) {
    *v = 22;
}

int main(void) {
    int *p = make_blob();
    mutate(p);
    printf("%d", *p);
    return 0;
}

Program 2

// prog2.c
#include <stdio.h>
#include <stdlib.h>

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

typedef struct list {
    node *first;
} list;

node* make_node(char *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;
}


void free_list(list *l) {
    node *cur = l->first;
    while (cur != NULL) {
        node *to_del = cur;
        cur = cur->next;
    }
    free(l);
}

void print_list(list *l) {
    node *cur = l->first;
    while (cur != NULL) {
        printf("%s", cur->value);
        cur = cur->next;
    }
}

char* get_input(void) {
    char *buf = NULL;
    size_t sz = 0;
    // `getline` is a POSIX library function. The function prompts the user for
    // a line of input and modifies the first argument to point to a
    // heap-allocated chunk that holds that input!
    printf("Enter a name: ");
    getline(&buf, &sz, stdin);
    return buf;
}

int main(void) {
    list *l = make_list();
    l->first = make_node(get_input(), make_node(get_input(), make_node(get_input(), NULL)));
    print_list(l);
    free_list(l);
    return 0;
}

Program 3

(Hint: for this program, it may not be obvious who is the owner of the relevant memory blocks. Think about making some heavyweight changes to the code, e.g., copying values around, to make it obvious who owns each heap-allocated block.)

// prog3.c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

const int INITIAL_CAPACITY = 8;
const int NUM_PEOPLE = 3;

typedef struct {
    char **names;
    int size;
    int capacity;
} name_list;

name_list* make_list() {
    name_list *ret = (name_list*) malloc(sizeof(name_list));
    ret->names = (char**) malloc(INITIAL_CAPACITY * sizeof(char*));
    ret->size = 0;
    ret->capacity = INITIAL_CAPACITY;
    return ret;
}

void free_list(name_list *list) {
    free(list->names);
    free(list);
}

void list_add(char* name, name_list *list) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->names = realloc(list->names, list->capacity);
    }
    list->names[list->size++] = name;
}

char* list_get(int index, name_list *list) {
    return list->names[index];
}

char* get_input(void) {
    char *buf = NULL;
    size_t sz = 0;
    printf("Enter a name: ");
    getline(&buf, &sz, stdin);
    return buf;
}

int main() {
    srand(time(NULL));

    name_list *people = make_list();
    for (int i = 0; i < NUM_PEOPLE; i++) {
        list_add(get_input(), people);
    }

    name_list *pool_a = make_list();
    name_list *pool_b = make_list();

    // The people are shuffled between the pools arbitrarily.
    // A person can be in both pools at once. All people
    // end up in at least one of the pools.
    for (int i = 0; i < NUM_PEOPLE; i++) {
        int k = rand() % 3;
        switch (k) {
        case 0:
            list_add(list_get(i, people), pool_a);
            break;
        case 1:
            list_add(list_get(i, people), pool_b);
            break;
        case 2:
            list_add(list_get(i, people), pool_a);
            list_add(list_get(i, people), pool_b);
            break;
        }
    }

    free(pool_a);
    free(pool_b);
    free(people);
}