David Chiu

Professor of Computer Science
University of Puget Sound
dchiu@pugetsound.edu


home | teaching | research | people | service | faq for students

CS 475 - Operating Systems

Lab 3: Dynamic Memory Allocation (Not Graded)

Pointers are still a bit mysterious, because we still haven’t seen a real need for them yet. Sure, it was cool to know that they are intrinsically connected to arrays, but still, with exception to swap(), all the code examples shown in the previous tutorial can be done easily without pointers. In this section, we introduce the prevailing motivation for pointers: heap memory allocation.

Student Outcomes

Instructions

Open your VS Code and get connected to your Remote Development environment.

Part 1: Motivation

In most of the programs we write, the exact space requirements may not be known until runtime. Consider the following code that asks the user how many employees they need to store, and then creates an array to store that many employees. This approach works in Java but not C!:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <stdio.h>
#include "employee.h"

int getNumEmployees() {
    int num;
    do {
        printf("Number of employees you need to store: ");
        scanf("%d", &num);
    } while (num <= 0);
    return num;
}


int main(int argc, char *argv[]) {
    int num_employees = getNumEmployees();  // ask for the array size first
    Employee my_employees[num_employees];   // <--- this could crash the program!!!

    // (code omitted)
}

If the number is big enough, this code will crash the C program when it’s run! It’s really important to understand why (Stack Overflow), so we need to have a handle on how the OS manages a process’ memory during execution.

Part 2: Process Address Spaces

When your program is in execution (it’s called a process at that point), the OS assigns it an address space. Think of this space as the process’ very own sandbox. It’s where all its resources (variables, open files, etc.) will live, and you can rest assured that it’s private and protected from other processes. The OS organizes each process’ address space in the following segments:

How the Program Stack Works (And What Is a Stack Overflow?)

When a process starts running, the OS allocates RLIMIT_STACK bytes for that process’ stack. A user cannot increase this stack size without changing the OS’s configuration. Here’s how the stack is used:

Part 3: Revisiting the Problem of Unknown Space Requirements at Runtime

Now that we understand how the program stack works, we return to our problematic code:

Part 4: Program Heap to the Rescue!!
Part 5: Dynamic Memory Allocation Examples

So we’ve seen how to create an array on the heap, but malloc() is more general than that. It can be used to allocate any amount of memory on the heap, even a single int, double, or just a struct. It is often the case that we’ll need to malloc to create new structs and strings of varying size. Here are a couple oft-used examples.

Part 5a: Creating Strings (Know this!)

Pay attention here, because you’ll be doing this a lot! We can now use malloc() to create just enough space to hold strings. For instance, suppose I wanted to write a function createEmail() that accepts two strings user and domain, and returns the string user@domain.

1
2
3
4
5
6
7
8
9
10
11

  #include <string.h>
  char* createEmail(char* user, char* domain) {
    // create a new string buffer on the heap
    char *email = (char*) malloc(strlen(user) + strlen(domain) + 2);    
    email[0] = '\0';  // empty the string (just good habit)

    strcpy(email, user); // copy user over
    strcat(email, "@"); // append @
    strcat(email, domain);  // append domain
    return email;
  }

In the above code:

Check-In Exercise Doing the exercise below will be fruitful, because you’ll likely use it for future assignments.

Part 5b: Instantiating Structs and the Arrow Syntax (->)

A great strength of malloc() lies in allowing us to create and manage dynamic data structures that are unbounded in size, like linked lists and trees. Assume we’ve declared the following struct for a Linked List node:

1
2
3
4
5

/** Here's a node for a linked list, say */
typedef struct Node {
    int data;
    struct Node *next;
} Node;

We can use malloc() to create a single struct element on the heap as follows.

1
2
3
4
5
6

// here's how to construct a Node element
Node *newNode = (Node*) malloc(sizeof(Node));

// here's how to initialize it (note the '->' operator!!!!)
newNode->data = 0;
newNode->next = NULL;

Notice the new operator -> that can be used to access pointers to structs. It automatically dereferences the pointer. The alternative way to access data and next is to use dot-notation after de-referencing the struct pointer, as follows:

1
2

(*newNode).data = 0;
(*newNode).next = NULL;

But the arrow operator -> just provides a much cleaner syntax to de-reference a pointer to a struct’s data member!

Food for Thought

These will come back to us in future assignments, but it won’t hurt to think about these problems early.

Credits

Written by David Chiu. 2022.