1 Intermediate C

1.1 Objectives

• Recalling C types with a focus on pointers.
• Focus on more advanced features like void *s and function pointers.
• Practice thinking about C programs as memory.

1.2 Types

1.2.1 Basic types

• char - think “one byte”. Same as signed char.
• short int - think “two bytes”. Same as short.
• int - think “four bytes”.
• long int - think “potentially larger int”. Most commonly known solely as long.
• float, double - floating point values (not used in the class).
• void - the lack of a type. Variables cannot have this type.

/* `void` is fine to denote "no variables/return values", ... */
int
main(void)
{
    /* ...but not fine on variables */
    void a;

    return 0;
}

Program output:

inline_exec_tmp.c: In function main:
inline_exec_tmp.c:6:14: error: variable or field a declared void
    6 |         void a;
      |              ^
make[1]: *** [Makefile:33: inline_exec_tmp] Error 1

• enum - an int or short int with some “named” values.

#include <stdio.h>

enum weekdays {
    MON, TUES, WED, THURS, FRI
};

int
main(void)
{
    printf("MON = %d, TUES = %d, ..., FRI = %d\n", MON, TUES, FRI);

    return 0;
}

Program output:

gcc -Wall -Wextra -I. -c -o prog.o prog.c
gcc -Wall -Wextra -fpic -I. -c -o example.o example.c
gcc -Wall -Wextra -fpic -I. -c -o example2.o example2.c
gcc -Wall -Wextra -fpic -I. -c -o example2b.o example2b.c
gcc -o prog_naive prog.o example.o example2.o example2b.o
gcc -Wall -Wextra -I. -c -o prog2.o prog2.c
gcc -o prog2_naive prog2.o example.o example2.o example2b.o
ar -crs libexample.a example.o
ar -crs libexample2.a example2.o example2b.o
gcc -o prog_static prog.o -L. -lexample -lexample2
gcc -o prog2_static prog2.o -L. -lexample -lexample2
gcc -shared -o libexample.so example.o
gcc -shared -o libexample2.so example2.o example2b.o
gcc -o prog_dynamic prog.o -L. -lexample -lexample2
gcc -o prog2_dynamic prog2.o -L. -lexample -lexample2
gcc -Wall -Wextra -fpic -I. -c -o main.o main.c
main.c: In function main:
main.c:11:17: warning: ignoring return value of malloc declared with attribute warn_unused_result [-Wunused-result]
   11 |                 malloc(1024);
      |                 ^~~~~~~~~~~~
gcc -o main.bin main.o
gcc -Wall -Wextra -fpic -I. -c -o ml.o ml.c
gcc -shared -o libmalloclog.so ml.o -ldl
rm main.o
MON = 0, TUES = 1, ..., FRI = 4

You can choose the values explicitly (e.g. enum grades { MON = 1, TUES = 2, WED = 3, THURS = 4, FRI = 5};).

Modifiers

• unsigned - variables that cannot be negative. Given that variables have a fixed bit-width, they can use the extra bit (“negative” no longer needs to be tracked) to instead represent numbers twice the size of signed variants.
• signed - signed variables. You don’t see this modifier as much because char, int, long all default to signed.
• long - Used to modify another type to make it larger in some cases. long int can represent larger numbers and is synonymous with long. long long int (or long long) is an even larger value!
• static - this variable should not be accessible outside of the .c file in which it is defined.
• const - an immutable value. We won’t focus much on this modifier.
• volatile - this variable should be “read from memory” every time it is accessed. Confusing now, relevant later, but not a focus.

1.2.1.1 Examples

int
main(void)
{
    char a;
    signed char a_signed;     /* same type as `a` */
    char b;                   /* values between [-128, 127] */
    unsigned char b_unsigned; /* values between [0, 256] */
    int c;
    short int c_shortint;
    short c_short;            /* same as `c_shortint` */
    long int c_longint;
    long c_long;              /* same type as `c_longint` */

    return 0;
}

Program output:

You might see all of these, but the common primitives, and their sizes:

#include <stdio.h>

/* Commonly used types that you practically see in a lot of C */
int
main(void)
{
    char c;
    unsigned char uc;
    short s;
    unsigned short us;
    int i;
    unsigned int ui;
    long l;
    unsigned long ul;

    printf("char:\t%ld\nshort:\t%ld\nint:\t%ld\nlong:\t%ld\n",
        sizeof(c), sizeof(s), sizeof(i), sizeof(l));

    return 0;
}

Program output:

char:   1
short:  2
int:    4
long:   8

1.2.2 Common POSIX types and values

• stddef.h¹:

  • size_t, usize_t, ssize_t - types for variables that correspond to sizes. These include the size of the memory request to malloc, the return value from sizeof, and the arguments and return values from read/write/… ssize_t is signed (allows negative values), while the others are unsigned.
  • NULL - is just #define NULL ((void *)0)

• limits.h²:

  • INT_MAX, INT_MIN, UINT_MAX - maximum and minimum values for a signed integer, and the maximum value for an unsigned integer.
  • LONG_MAX, LONG_MIN, ULONG_MAX - minimum and maximum numerical values for longs and unsigned longs.
  • Same for short ints (SHRT_MAX, etc…) and chars (CHAR_MAX, etc…).

1.2.3 Format Strings

Many standard library calls take “format strings”. You’ve seen these in printf. The following format specifiers should be used:

• %d - int
• %ld - long int
• %u - unsigned int
• %c - char
• %x - unsigned int printed as hexadecimal
• %lx - long unsigned int printed as hexadecimal
• %p - prints out any pointer value, void *
• %s - prints out a string, char *

Format strings are also used in scanf functions to read and parse input.

You can control the spacing of the printouts using %NX where N is the number of characters you want printed out (as spaces), and X is the format specifier above. For example, "%10ld"would print a long integer in a 10 character slot. Adding \n and \t add in the newlines and the tabs. If you need to print out a “\”, use \\.

1.2.3.1 Example

#include <stdio.h>
#include <limits.h>

int
main(void)
{
    printf("Integers: %d, %ld, %u, %c\n"
           "Hex and pointers: %lx, %p\n"
           "Strings: %s\n",
           INT_MAX, LONG_MAX, UINT_MAX, '*',
           LONG_MAX, &main,
           "hello world");

    return 0;
}

Program output:

Integers: 2147483647, 9223372036854775807, 4294967295, *
Hex and pointers: 7fffffffffffffff, 0x650838c45149
Strings: hello world

1.2.4 Compound types

• struct - A collection of different values. Example: objects with many different fields.
• union - One of a set of values. Example: what if you want to represent data for one food item among others.

Unions are not very common, but are sometimes useful. The size of a union is the maximum size of its fields. In contrast, the struct is the sum of the sizes of each of its fields.

1.2.4.1 Example

#include <stdio.h>

struct hamburger {
    int num_burgers;
    int cheese;
    int num_patties;
};

union food {
    int num_eggs;
    struct hamburger burger;
};

/* Same contents as the union. */
struct all_food {
    int num_eggs;
    struct hamburger burger;
};

int
main(void)
{
    union food f_eggs, f_burger;

    /* now I shouldn't access `.burger` in `f_eggs` */
    f_eggs.num_eggs = 10;
    /* This is just syntax for structure initialization. */
    f_burger.burger = (struct hamburger) {
        .num_burgers = 5,
        .cheese      = 1,
        .num_patties = 1
    };
    /* now shouldn't access `.num_eggs` in `f_burger` */

    printf("Size of union:  %ld\nSize of struct: %ld\n",
           sizeof(union food), sizeof(struct all_food));

    return 0;
}

Program output:

Size of union:  12
Size of struct: 16

We can see the effect of the union: The size is max(fields) rather than sum(fields). What other examples can you think of where you might want unions?

An aside on syntax: The structure initialization syntax in this example is simply a shorthand. The struct hamburger initialization above is equivalent to:

f_burger.burger.num_burgers = 5;
f_burger.burger.cheese      = 1;
f_burger.burger.num_patties = 1;

Though since there are so many .s, this is a little confusing. We’d typically want to simply as:

struct hamburger *h = &f_burger.burger;
h->num_burgers = 5;
h->cheese      = 1;
h->num_patties = 1;

More on -> in the next section.

1.2.5 Pointers & Arrays

Variables can have be pointer types (e.g. int *a). Variables with pointer types are pointers and hold an address to the a variable of the type to which they point, or to NULL. NULL denotes that the pointer is not valid. You want to imagine that variables hold data, for example int a = 6:

a---+
| 6 |
+---+

A pointer, int *b = &a should be imagined as a pointer:

b ---> a---+
       | 6 |
       +---+

Note that the “address of”, & operator takes a variable and returns its address. If you print out the pointer, printf("%p", b), you’ll get the address (i.e. the arrow) To follow the arrow, you must dereference the pointer: *b == 6.

#include <stdio.h>

static int value;

/* here, the `*` is part of the type "int *", i.e. a pointer to an `int` */
void
foo(int *ptr)
{
    /*
     * Here, the `*` is the dereference operation, and
     * gives us the value that is pointed to.
     */
    *ptr = 1;
}

int
main(void)
{
    printf("value is initialized to %d\n", value);

    foo(&value); /* `&` gives us the address of the variable `value` */
    printf("value updated to %d\n", value);

    return value - 1;
}

Program output:

value is initialized to 0
value updated to 1

Pointers are necessary as they enable us to build linked data-structures (linked-lists, binary trees, etc…). Languages such as Java assume that every single object variable is a pointer, and since all object variables are pointers, they don’t need special syntax for them.

Arrays are simple contiguous data items, all of the same type. int a[4] = {6, 7, 8, 9} should be imagined as:

a ---> +---+---+---+---+
       | 6 | 7 | 8 | 9 |
       +---+---+---+---+

When you access an array item, a[2] == 8, C is really treating a as a pointer, doing pointer arithmetic, and dereferences to find offset 2.

#include <stdio.h>

int main(void) {
    int a[] = {6, 7, 8, 9};
    int n = 1;

    printf("0th index: %p == %p; %d == %d\n", a,     &a[0], *a,       a[0]);
    printf("nth index: %p == %p; %d == %d\n", a + n, &a[n], *(a + n), a[n]);

    return 0;
}

Program output:

0th index: 0x7ffeb5d86320 == 0x7ffeb5d86320; 6 == 6
nth index: 0x7ffeb5d86324 == 0x7ffeb5d86324; 7 == 7

Making this a little more clear, lets understand how C accesses the nth item. Lets make a pointer int *p = a + 1 (we’ll just simply and assume that n == 1 here), we should have this:

p ---------+
           |
           V
a ---> +---+---+---+---+
       | 6 | 7 | 8 | 9 |
       +---+---+---+---+

Thus if we dereference p, we access the 1st index, and access the value 7.

#include <stdio.h>

int
main(void)
{
    int a[] = {6, 7, 8, 9};
    /* same thing as the previous example, just making the pointer explicit */
    int *p = a + 1;

    printf("nth index: %p == %p; %d == %d\n", p, &a[1], *p, a[1]);

    return 0;
}

Program output:

nth index: 0x7ffe91c27844 == 0x7ffe91c27844; 7 == 7

We can see that pointer arithmetic (i.e. doing addition/subtraction on pointers) does the same thing as array indexing plus a dereference. That is, *(a + 1) == a[1]. For the most part, arrays and pointers can be viewed as very similar, with only a few exceptions³.

Pointer arithmetic should generally be avoided in favor of using the array syntax. One complication for pointer arithmetic is that it does not fit our intuition for addition:

#include <stdio.h>

int
main(void)
{
    int a[] = {6, 7, 8, 9};
    char b[] = {'a', 'b', 'c', 'd'};
    /*
     * Calculation: How big is the array?
     * How big is each item? The division is the number of items.
     */
    int num_items = sizeof(a) / sizeof(a[0]);
    int i;

    for (i = 0; i < num_items; i++) {
        printf("idx %d @ %p & %p\n", i, a + i, b + i);
    }

    return 0;
}

Program output:

idx 0 @ 0x7fff5c67dda0 & 0x7fff5c67ddb4
idx 1 @ 0x7fff5c67dda4 & 0x7fff5c67ddb5
idx 2 @ 0x7fff5c67dda8 & 0x7fff5c67ddb6
idx 3 @ 0x7fff5c67ddac & 0x7fff5c67ddb7

Note that the pointer for the integer array (a) is being incremented by 4, while the character array (b) by 1. Focusing on the key part:

idx 0 @ ...0 & ...4
idx 1 @ ...4 & ...5
idx 2 @ ...8 & ...6
idx 3 @ ...c & ...7
           ^      ^
           |      |
Adds 4 ----+      |
Adds 1 -----------+

Thus, pointer arithmetic depends on the size of the types within the array. There are types when one wants to iterate through each byte of an array, even if the array contains larger values such as integers. For example, the memset and memcmp functions set each byte in an range of memory, and byte-wise compare two ranges of memory. In such cases, casts can be used to manipulate the pointer type (e.g. (char *)a enables a to not be referenced with pointer arithmetic that iterates through bytes).

1.2.5.1 Example

#include <stdio.h>

/* a simple linked list */
struct student {
    char *name;
    struct student *next;
};

struct student students[] = {
    {.name = "Penny", .next = &students[1]}, /* or `students + 1` */
    {.name = "Gabe",  .next = NULL}
};
struct student *head = students;
/*
 * head --> students+------+
 *          | Penny | Gabe |
 *          | next  | next |
 *          +-|-----+---|--+
 *            |     ^   +----->NULL
 *            |     |
 *            +-----+
 */
int
main(void)
{
    struct student *i;

    for (i = head; i != NULL; i = i->next) {
        printf("%s\n", i->name);
    }

    return 0;
}

Program output:

Penny
Gabe

1.2.5.2 Generic Pointer Types

Generally, if you want to treat a pointer type as another, you need to use a cast. You rarely want to do this (see the memset example below to see an example where you might want it). However, there is a need in C to have a “generic pointer type” that can be implicitly cast into any other pointer type. To get a sense of why this is, two simple examples:

1. What should the type of NULL be?

NULL is used as a valid value for any pointer (of any type), thus NULL must have a generic type that can be used in the code as a value for any pointer. Thus, the type of NULL must be void *.

2. malloc returns a pointer to newly-allocated memory. What should the type of the return value be?

C solves this with the void * pointer type. Recall that void is not a valid type for a variable, but a void * is different. It is a “generic pointer that cannot be dereferenced*. Note that dereferencing a void * pointer shouldn’t work as void is not a valid variable type (e.g. void *a; *a = 10; doesn’t make much sense because *a is type void).

#include <malloc.h>

int
main(void)
{
    int *intptr = malloc(sizeof(int)); /* malloc returns `void *`! */

    *intptr = 0;

    return *intptr;
}

Program output:

Data-structures often aim to store data of any type (think: a linked list of anything). Thus, in C, you often see void *s to reference the data they store.

1.2.5.3 Relationship between Pointers, Arrays, and Arrows

Indexing into arrays (a[b]) and arrows (a->b) are redundant syntactic features, but they are very convenient.

• &a[b] is equivalent to a + b where a is a pointer and b is an index.
• a[b] is equivalent to *(a + b) where a is a pointer and b is an index.
• a->b is equivalent to (*a).b where a is a pointer to a variable with a structure type that has b as a field.

Generally, you should always try and stick to the array and arrow syntax were possible, as it makes your intention much more clear when coding than the pointer arithmetic and dereferences.

1.3 Memory Allocation

Dynamic memory allocations

• void *malloc(size_t size) - allocate size memory, or return NULL.
• void *calloc(size_t nmemb, size_t size) - allocate nmemb * size bytes, and initialize them to 0.
• void *realloc(void *ptr, size_t size) - pass in a previous allocation, and either grow/shrink it to size, or allocate a new chunk of memory and copy the data in ptr into it. Return the memory of size size, or NULL on error.
• void free(void *ptr) - deallocate previously allocated memory (returned from any of the above).

A few things to keep in mind:

1. If you want to allocate an array, then you have to do the math yourself for the array size. For example, int *arr = malloc(sizeof(int) * n); to allocate an array of ints with a length of n.
2. malloc is not guaranteed to initialize its memory to 0. You must make sure that your array gets initialized. It is not uncommon to do a memset(arr, 0, sizeof(int) * n); to set the memory 0.
3. calloc is guaranteed to initialize all its allocated memory to 0.

1.3.1 Common Errors

• Allocation error. You must check the return value of memory allocation functions for NULL, and handle the error appropriately.

#include <malloc.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    /* Error: did not check return value! */
    *a = 1;
    free(a);

    return 0;
}

Program output:

• Dangling pointer. If you maintain a pointer to a chunk of memory that you free, and then dereference that pointer, bad things can happen. The memory might have already been re-allocated due to another call to malloc, and is used for something completely different in your program. It is up to you as a programmer to avoid freeing memory until all references to it are dropped.

#include <malloc.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    if (a == NULL) return -1;
    free(a);

    /* Error: accessing what `a` points to after `free`! */
    return *a;
}

Program output:

inline_exec_tmp.c: In function main:
inline_exec_tmp.c:11:16: warning: pointer a used after free [-Wuse-after-free]
   11 |         return *a;
      |                ^~
inline_exec_tmp.c:8:9: note: call to free here
    8 |         free(a);
      |         ^~~~~~~
make[1]: *** [Makefile:30: inline_exec] Error 86

• Memory leaks. If you remove all references to memory, but don’t free it, then the memory will never get freed. This is a memory leak.

#include <malloc.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    if (!a) return -1;
    a = NULL;
    /* Error: never `free`d `a` and no references to it remain! */

    return 0;
}

Program output:

• Double free. If you free the memory twice, bad things can happen. You could confuse the memory allocation logic, or you could accidentally free an allocation made after the first free was called.

#include <malloc.h>

int
main(void)
{
    int *a = malloc(sizeof(int));
    if (!a) return -1;
    free(a);
    free(a);
    /* Error: yeah, don't do that! */

    return 0;
}

Program output:

inline_exec_tmp.c: In function main:
inline_exec_tmp.c:9:9: warning: pointer a used after free [-Wuse-after-free]
    9 |         free(a);
      |         ^~~~~~~
inline_exec_tmp.c:8:9: note: call to free here
    8 |         free(a);
      |         ^~~~~~~
free(): double free detected in tcache 2
make[1]: *** [Makefile:30: inline_exec] Aborted (core dumped)

valgrind will help you debug the last three of these issues, and later in the class, we’ll develop a library to help debug the first.

1.4 Function Pointers

It is not uncommon for programs to require some dynamic behavior. A data structure might need to do different types of comparisons between its data (depending on what data is being stored). This means that a generic data-structure (think: a hash-table) needs to somehow compare equality of the data objects it stores without knowing what they are! In Java, think about the equals method. Each object can define its own equals method to compare between objects of the same type.

In C, this is implemented using function pointers. These are pointers to functions of a particular type. They can be passed as arguments to functions, and can be dereferenced to call the function. Let look at an example from man 3 lsearch:

void *lfind(const void *key, const void *base, size_t *nmemb, size_t size,
            int(*compar)(const void *, const void *));

This is a function to find a value in an array. The implementation needs to understand how to compare a key with each of the items in the array. For this purpose, the compar function pointer is the last argument.

1.4.1 Typedefs

Function pointer syntax is not natural in C. Thus, it is common to use a typedef to create the type name for a function pointer for a given API. The syntax for this is perhaps even less natural, but only needs be done once.

typedef int (*compare_fn_t)(const void *, const void *);
void *lfind(const void *key, const void *base, size_t *nmemb, size_t size, compare_fn_t compar);

Now the function declaration is more clear, and the _fn_t postfix, by convention, denotes a function pointer.

1.5 Exercises

1.5.1 C is a Thin Language Layer on Top of Memory

We’re going to look at a set of variables as memory. When variables are created globally, they are simply allocated into subsequent addresses.

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

void print_values(void);

unsigned char a = 1;
int b = 2;
struct foo {
    long c_a, c_b;
    int *c_c;
};
struct foo c = (struct foo) { .c_a = 3, .c_c = &b };
unsigned char end;

int
main(void)
{
    size_t vars_size;
    unsigned int i;
    unsigned char *mem;

    /* Q1: What would you predict the output of &end - &a is? */
    printf("Addresses:\na   @ %p\nb   @ %p\nc   @ %p\nend @ %p\n"
           "&end - &a = %ld\n", /* Note: you can split strings! */
           &a, &b, &c, &end, &end - &a);
    printf("\nInitial values:\n");
    print_values();
    /* Q2: Describe what these next two lines are doing. */
    vars_size = &end - &a;
    mem = &a;
    /* Q3: What would you expect in the following printout (with the print uncommented)? */
    printf("\nPrint out the variables as raw memory\n");
    for (i = 0; i < vars_size; i++) {
        unsigned char c = mem[i];
//      printf("%x ", c);
    }
    /* Q4: What would you expect in the following printout (with the print uncommented)? */
    memset(mem, 0, vars_size);
    /* memset(a, b, c): set the memory starting at `a` of size `c` equal `b` */
    printf("\n\nPost-`memset` values:\n");
//  print_values();

    return 0;
}

void
print_values(void)
{
    printf("a     = %d\nb     = %d\nc.c_a = %ld\nc.c_b = %ld\nc.c_c = %p\n",
           a, b, c.c_a, c.c_b, c.c_c);
}

Program output:

Addresses:
a   @ 0x6543733b8010
b   @ 0x6543733b8014
c   @ 0x6543733b8020
end @ 0x6543733b8039
&end - &a = 41

Initial values:
a     = 1
b     = 2
c.c_a = 3
c.c_b = 0
c.c_c = 0x6543733b8014

Print out the variables as raw memory


Post-`memset` values:

Question Answer Q1-4 in the code, uncommenting and modifying where appropriate.

1.5.1.1 Takeaways

1. Each variable in C (including fields in structs) want to be aligned on a boundary equal to the variable’s type’s size. This means that a variable (b) with an integer type (sizeof(int) == 4) should always have an address that is a multiple of its size (&b % sizeof(b) == 0, so an int’s address is always divisible by 4, a long’s by 8).
2. The operation to figure out the size of all the variables, &end - &a, is crazy. We’re used to performing math operations values on things of the same type, but not on pointers. This is only possible because C sees the variables are chunks of memory that happen to be laid out in memory, one after the other.
3. The crazy increases with mem = &a, and our iteration through mem[i]. We’re able to completely ignore the types in C, and access memory directly!

Question: What would break if we changed char a; into int a;? C doesn’t let us do math on variables of any type. If you fixed compilation problems, would you still get the same output?

1.5.2 Quick-and-dirty Key-Value Store

Please read the man pages for lsearch and lfind. man pages can be pretty cryptic, and you are aiming to get some idea where to start with an implementation. An simplistic, and incomplete initial implementation:

#include <stdio.h>
#include <assert.h>
#include <search.h>

#define NUM_ENTRIES 8
struct kv_entry {
    int key; /* only support keys for now... */
};
/* global values are initialized to `0` */
struct kv_entry entries[NUM_ENTRIES];
size_t num_items = 0;

/**
 * Insert into the key-value store the `key` and `value`.
 * Return `0` on successful insertion of the value, or `-1`
 * if the value couldn't be inserted.
 */
int
put(int key, int value)
{
    return 0;
}

/**
 * Attempt to get a value associated with a `key`.
 * Return the value, or `0` if the `key` isn't in the store.
 */
int
get(int key)
{
    return 0;
}

int
compare(const void *a, const void *b)
{
    /* We know these are `int`s, so treat them as such! */
    const struct kv_entry *a_ent = a, *b_ent = b;

    if (a_ent->key == b_ent->key) return 0;

    return -1;
}

int
main(void)
{
    struct kv_entry keys[] = {
        {.key = 1},
        {.key = 2},
        {.key = 4},
        {.key = 3}
    };
    int num_kv = sizeof(keys) / sizeof(keys[0]);
    int queries[] = {4, 2, 5};
    int num_queries = sizeof(queries) / sizeof(queries[0]);
    int i;

    /* Insert the keys. */
    for (i = 0; i < num_kv; i++) {
        lsearch(&keys[i], entries, &num_items, sizeof(entries) / sizeof(entries[0]), compare);
    }

    /* Now lets lookup the keys. */
    for (i = 0; i < num_queries; i++) {
        struct kv_entry *ent;
        int val = 0;

        ent = lfind(&queries[i], entries, &num_items, sizeof(entries[0]), compare);
        if (ent != NULL) {
            val = ent->key;
        }

        printf("%d: %d @ %p\n", i, val, ent);
    }

    return 0;
}

Program output:

0: 4 @ 0x5da33433804c
1: 2 @ 0x5da334338044
2: 0 @ (nil)

You want to implement a simple “key-value” store that is very similar in API to a hash-table (many key-value stores are implemented using hash-tables!).

Questions/Tasks:

• Q1: What is the difference between lsearch and lfind? The manpages should help here (man 3 lsearch) (you can exit from a man page using ‘q’). What operations would you want to perform with each (and why)?
• Q2: The current implementation doesn’t include values at all. It returns the keys instead of values. Expand the implementation to properly track values.
• Q3: Encapsulate the key-value store behind the put and get functions.
• Q4: Add testing into the main for the relevant conditions and failures in get and put.

2 C Memory Model, Data-structures, and APIs

C presents some unique opportunities for how to structure your code and data-structures, but also requires that you’re careful about how data is passed around a program.

2.1 Memory Allocation Options

In C, when creating a variable, you have the option of allocating it in one of multiple different types of memory:

• In another existing structure.
• In the heap using malloc or its sibling functions.
• In global memory.
• On the stack.

It might be surprising, but it is quite uncommon in programming languages to have this flexibility.

2.1.1 Internal Allocation

What does it look like to do internal allocation of one struct or array inside of another? See the following as an example.

#include <stdlib.h>

struct bar {
    /*
     * `arr` is allocated internally to `bar`, whereas `bytes` is a pointer to
     * a separate allocation. `arr` must have a *fixed size*, and `bytes` does not
     * because its allocation can be as large as you want!
     */
    int arr[64];
    unsigned char *bytes;
};

struct foo {
    /* The `bar` structure is allocated as *part of* the `struct foo` in `internal` */
    struct bar internal;
    /* But we can *also* allocate another `bar` separately if we'd prefer */
    struct bar *external;
};

int
main(void)
{
    /*
     * We didn't have to separately allocate the `struct bar internal` as
     * it was allocated with the enclosing `a` allocation. However, we do have to
     * allocate the `external` allocation. In both cases, we have access to a
     * `struct bar` from within `struct foo`.
     */
    struct foo *a = malloc(sizeof(struct foo)); /* should check return value */
    a->external   = malloc(sizeof(struct bar)); /* and this one ;-( */

    /*
     * Note the difference in needing to use `->` when `external` is a pointer
     * versus simply using `.` with `internal`.
     */
    a->internal.arr[0] = a->external->arr[0];

    return 0;
}

Program output:

One of the more interesting uses of internal allocation is in linked data-structures (e.g. like linked lists). It is common in languages like java to implement linked data-structures to have “nodes” that reference the data being tracked.

// This could be made generic across the data types it could store by instead
// using `class LinkedList<T>`, but I'm keeping it simple here.
class LinkedListOfStudents {
    Node head;

    class Node {
        Student s;
        Node next;

        Node(Student s, Node next) {
            this.s    = s;
            this.next = next;
        }
    }

    void add(Student s) {
        // The program has *previously* allocated `data`.
        // Now we have to additionally allocate the `node` separate from the data!
        Node n = new(s, this.head);

        this.head = n;
    }

    // ...
}
// This looks like the following. Note separate allocations for Node and Student
//
// head --> Node------+    ,-->Node-----+
//          | s  next |---'    | s next |---...
//          +-|-------+        +-|------+
//            v                  V
//          Student-+           Student-+
//          | ...   |           | ...   |
//          +-------+           +-------+

Lets see the same in C.

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

struct linked_list_node {
    void *data;
    struct linked_list_node *next;
};

struct linked_list {
    struct linked_list_node *head;
};

struct student {
    // student data here...
    struct linked_list_node list;
};

void
add(struct linked_list *ll, struct linked_list_node *n, void *data)
{
    n->next  = ll->head;
    n->data  = data;
    ll->head = n;
}

struct linked_list l;

int
main(void)
{
    struct student *s = malloc(sizeof(struct student));
    /* Should check that `s != NULL`... */
    add(&l, &s->list, s); /* note that `&s->list` is the same as `&(s->list)` */

    printf("student added to list!\n");

    return 0;
}

/*
 * This looks something like the following. Linked list is *internal* to student.
 *
 * head ----> student-+     ,-> student-+
 *            | ...   |    ,    | ...   |
 *            | next  |---'     | next  |--> NULL
 *            +-------+         +-------+
 */

Program output:

student added to list!

A few interesting things happened here:

1. We’re using void * pointers within the linked_list_node so that the linked list can hold data of any pointer type. You can see that in our list implementation, there is nothing that is student-specific.
2. The list is inline-allocated inside the student structure, which completely avoids the separate node allocation.

Most serious data-structure implementations enable this inlining of data-structure nodes even without requiring the data pointer in the node. We won’t cover that, but you can see a sample implementation.

2.1.2 Heap Allocation

We’ve already seen malloc, calloc, realloc, and free which are our interface to the heap. These provide the most flexibility, but require that you track the memory and free it appropriately⁴

2.1.3 Global Allocation

We have already seen global allocations frequently in examples so far.

#include <stdio.h>

/* A globally allocated array! No `malloc` needed! */
int arr[64];
struct foo {
    int a, b;
    struct foo *next;
};
/* A globally allocated structure! */
struct foo s;

/* Globally allocated *and* initialized integer... */
int c = 12;
/* ...and array. */
long d[] = {1, 2, 3, 4};

int
main(void)
{
    printf("What is uninitialized global memory set to?\n"
           "Integer: %d\nPointer: %p (as hex: %lx)\n",
           arr[0], s.next, (unsigned long)s.next);
    /* Note that we use `.` to access the fields because `s` is not a pointer! */

    return 0;
}

Program output:

What is uninitialized global memory set to?
Integer: 0
Pointer: (nil) (as hex: 0)

Global variables are either initialized where they are defined, or are initialized to 0. Note that they are intialized to all 0s regardless their type. This makes more sense than it sounds because pointers set to 0 are NULL (because, recall, NULL is just (void *)0 – see the “hex” output above), and because strings (see later) are terminated by \0 which is also 0! Thus, this policy initializes all numerical data to 0, all pointers to NULL, and all strings to "".

2.1.4 Stack Allocation

Variables can also be allocated on the stack. This effectively means that as you’re executing in a function, variables can be allocated within the context/memory of that function. An example that allocates a structure and an array on the stack:

#include <stdio.h>
#include <assert.h>

#define ARR_SZ 12

/*
 * Find an integer in the array, reset it to `0`, and return its offset.
 * Nothing very interesting here.
 */
int
find_and_reset(int *arr, int val)
{
    int i;

    /* find the value */
    for (i = 0; i < ARR_SZ; i++) {
        if (arr[i] == val) {
            arr[i] = 0;
            return i;
        }
    }
    /* Couldn't find it! */
    return -1;
}

int
fib(int v)
{
    /* Allocate an array onto the stack */
    int fibs[ARR_SZ] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}; /* looks like a suspicious sequence... */
    int ret;

    ret = find_and_reset(fibs, v);
    /* should have been set to `0`, so this should return `-1` */
    assert(find_and_reset(fibs, v) == -1);

    return ret;
}

int
main(void)
{
    printf("Should find 8 @ 6: %d\n", fib(8));
    /* if the array was the same array for these two calls, it would be found at offset -1 (error) */
    printf("Should find 8 @ 6: %d (-1 is wrong here)\n", fib(8));

    return 0;
}

Program output:

Should find 8 @ 6: 6
Should find 8 @ 6: 6 (-1 is wrong here)

Key points to realize:

• fibs in fib is allocated on the stack and is initialized in fib!
• We are passing the array into find_and_reset which modifies the array directly as it is passed as a pointer.
• The first time that fib is called, it creates the arr. After we return from fib, the fibs goes away (strictly: its memory is reclaimed as part of returning from fib).
• The second time we call fib, it effectively is a new execution of fib, thus a new allocation of fibs that is now initialized a second time.

2.1.4.1 Stack Usage Example

How do we think about this? The stack starts out in main:

stack          |
|              |
+-main---------+
|              | <--- main's local data (note: no local variables)
+--------------+

What we’re drawing here is a “stack frame” for the main function. This includes all of the local data allocated within the function, and (at least conceptually) also includes the arguments passed into the function (main has none). When it calls fib, a stack frame is allocated for fib, the argument is passed in, and fibs variables are allocated:

stack          |
|              |
+-main---------+
|              |
+-fib----------+
| arg: v       | <--- argument to fib
| fibs[ARR_SZ] | <-+- local variables, allocated here!
| ret          | <-'
+--------------+

fib calls find_and_reset:

stack          |
|              |
+-main---------+
|              |
+-fib----------+
| v            |
| fibs[ARR_SZ] |<--+
| ret          |   | pointer to fibs passed as argument, and used to update arr[v]
+find_and_reset+   |
| arg: arr     |---+
| arg: val     |
| i            |
+--------------+

Since find_and_reset updates the array in fib’s stack frame, when it returns, the array is still properly updated. Importantly, once we return to main, we have deallocated all of the variables from the previous call to fib…

stack          |
|              |
+-main---------+
|              | <--- returning to main, deallocates the fibs array in fib
+--------------+

…thus the next call to fib allocates a new set of local variables including fibs.

stack          |
|              |
+-main---------+
|              |
+-fib----------+
| arg: v       |
| fibs[ARR_SZ] | <--- new version of fibs, re-initialized when we fib is called
| ret          |
+--------------+

2.1.4.2 Common Errors in Stack Allocation

A few common errors with stack allocation include:

• Uninitialized variables. You must always initialize all variables allocated on the stack, otherwise they can contain seemingly random values (see below).
• Pointers to stack allocated variables after return. After a function returns, its stack allocated variables are no longer valid (they were deallocated upon return). Any pointers that remain to any of those variables are no longer pointing to valid memory!

We discuss these next.

Initializing stack-allocated variables. For global memory, we saw that variables, if not intentionally initialized, would be set to 0. This is not the case with stack allocated variables. In fact, the answer is “it depends”. If you compile your code without optimizations, stack allocated variables will be initialized to 0; if you compile with optimizations, they are not initialized. Yikes. Thus, we must assume that they are not automatically initialized (similar to the memory returned from malloc). An example:

#include <stdio.h>

void
foo(void)
{
    /* don't manually initialize anything here */
    int arr[12];
    int i;

    for (i = 0; i < 12; i++) {
        printf("%d: %d\n", i, arr[i]);
    }
}

int
main(void)
{
    foo();

    return 0;
}

Program output:

inline_exec_tmp.c: In function foo:
inline_exec_tmp.c:11:17: warning: arr may be used uninitialized [-Wmaybe-uninitialized]
   11 |                 printf("%d: %d\n", i, arr[i]);
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
inline_exec_tmp.c:7:13: note: arr declared here
    7 |         int arr[12];
      |             ^~~
0: 0
1: 0
2: 0
3: 0
4: 0
5: 0
6: 0
7: 0
8: 0
9: 0
10: 0
11: 0

Yikes. We’re getting random values in the array! Where do you think these values came from?

References to stack variables after function return.

#include <stdio.h>

unsigned long *ptr;

unsigned long *
bar(void)
{
    unsigned long a = 42;

    return &a;            /* Return the address of a local variable. */
}

void
foo(void)
{
    unsigned long a = 42; /* Allocate `a` on the stack here... */

    ptr = &a;             /* ...and set the global pointer to point to it... */

    return;               /* ...but then we deallocate `a` when we return. */
}

int
main(void)
{
    unsigned long val;

    foo();
    printf("Save address of local variable, and dereference it: %lu\n", *ptr);
    fflush(stdout); /* ignore this ;-) magic sprinkles here */
    ptr = bar();
    printf("Return address of local variable, and dereference it: %lu\n", *ptr);

    return 0;
}

Program output:

inline_exec_tmp.c: In function bar:
inline_exec_tmp.c:10:16: warning: function returns address of local variable [-Wreturn-local-addr]
   10 |         return &a;            /* Return the address of a local variable. */
      |                ^~
inline_exec_tmp.c: In function foo:
inline_exec_tmp.c:18:13: warning: storing the address of local variable a in ptr [-Wdangling-pointer=]
   18 |         ptr = &a;             /* ...and set the global pointer to point to it... */
      |         ~~~~^~~~
inline_exec_tmp.c:16:23: note: a declared here
   16 |         unsigned long a = 42; /* Allocate `a` on the stack here... */
      |                       ^
inline_exec_tmp.c:3:16: note: ptr declared here
    3 | unsigned long *ptr;
      |                ^~~
Save address of local variable, and dereference it: 42
make[1]: *** [Makefile:30: inline_exec] Segmentation fault (core dumped)

You can see a few interesting facts from the output.

1. The value referenced by *ptr after foo is a random value, and dereferencing the return value frombar causes a segmentation fault.
2. foo and bar contain logic that feels pretty identical. In either case, they are taking a local variable, and passing its address to main where it is used. foo passed it through a global variable, and bar simply returns the address. Despite this, one of them causes a segmentation fault, and the other seems to return a nonsensical value! When you try and use stack allocated variables after they are been freed (by their function returning), you get unpredictable results.
3. The C compiler is aggressive about issuing warnings as it can tell that bad things are afoot. Warnings are your friend and you must do your development with them enabled.

Stack allocation is powerful, can be quite useful. However, you have to always be careful that stack allocated variables are never added into global data-structures, and are never returned.

2.1.5 Putting it all Together

Lets look at an example that uses inlined, global, and stack allocation. We’ll avoid heap-based allocation to demonstrate the less normal memory allocation options in C.

#include <stdio.h>
#include <search.h>
#include <assert.h>

struct kv_entry {
    unsigned long key;
    char *value;
};

struct kv_store {
    /* internal allocation of the key-value store's entries */
    struct kv_entry entries[16];
    size_t num_entries;
};

int
kv_comp(const void *a, const void *b)
{
    const struct kv_entry *a_ent = a;
    const struct kv_entry *b_ent = b;

    /* Compare keys, and return `0` if they are the same */
    return !(a_ent->key == b_ent->key);
}

int
put(struct kv_store *store, unsigned long key, char *value)
{
    /* Allocate a structure on the stack! */
    struct kv_entry ent = {
        .key = key,
        .value = value
    };
    struct kv_entry *new_ent;
    /* Should check if the kv_store has open entries. */

    /* Notice we have to pass the `&ent` as a pointer is expected */
    new_ent = lsearch(&ent, store->entries, &store->num_entries, sizeof(struct kv_entry), kv_comp);
    /* Should check if we found an old entry, and we need to update its value. */

    if (new_ent == NULL) return -1;

    return 0;
}

int
main(void)
{
    /* Allocated the data-store on the stack, including the array! */
    struct kv_store store = { .num_entries = 0 };

    unsigned long key = 42;
    char *value = "secret to everything";
    put(&store, key, value);

    /* Validate that the store got modified in the appropriate way */
    assert(store.num_entries == 1);
    assert(store.entries[0].key == key);

    printf("%ld is the %s\n", store.entries[0].key, store.entries[0].value);

    return 0;
}

Program output:

42 is the secret to everything

In this program you might notice that we’ve used no dynamic memory allocation at all! The cost of this is that we had to create a key-value store of only a fixed size (16 items, here).

2.1.6 Comparing C to Java

C enables a high-degree of control in which memory different variables should be placed. Java traditionally has simple rules for which memory is used for variables:

• Primitive types are stored in objects and on the stack.
• Objects are always allocated using new in the heap, and references to objects are always pointers.
• The heap is managed by the garbage collector, thus avoiding the need for free.

Many aspects of this are absolutely fantastic:

• The programmer doesn’t need to think about how long the memory for an object needs to stick around – the garbage collector instead manages deallocation.
• The syntax for accessing fields in objects is uniform and simple: always use a . to access a field (e.g. obj.a) – all object references are pointers, so instead of having -> everywhere, just replace it with the uniform ..

However, there are significant downsides when the goal is to write systems code:

• Some systems don’t have a heap! Many embedded (small) systems don’t support dynamic allocation.
• Garbage collection (GC) isn’t free! It has some overhead for some applications, can result in larger memory consumption (as garbage is waiting to be collected), and can causes delays in processing when GC happens. That said, modern GC is pretty amazing and does a pretty good job at minimizing all of these factors.
• Many data-structures that might be allocated globally or on the stack, instead must be allocated on the heap, which is slower. Similarly, many objects might want other objects to be part of their allocation, but that isn’t possible as each must be a separate heap allocation, which adds overhead.

2.2 Strings

String don’t have a dedicated type in C – there is no String type. Strings are

1. arrays of chars,
2. with a null-terminator (\0) character in the last array position to denote the termination of the string.

In memory, a simple string has this representation:

char *str = "hi!"

str ---> +---+---+---+---+
         | h | i | ! |\0 |
         +---+---+---+---+

Note that \0 is a single character even though it looks like two. We can see this:

#include <stdio.h>
#include <assert.h>

int
main(void)
{
    int i;
    char *str = "hi!";
    char str2[4] = {'h', 'i', '!', '\0'};        /* We can allocate strings on the stack! */

    for (i = 0; str[i] != '\0'; i++) {           /* Loop till we find the null-terminator */
        assert(str[i] == str2[i]);               /* Verify the strings are the same. */
        printf("%c", str[i]);
    }
    assert(str[3] == str2[3] && str[3] == '\0'); /* Explicitly check that the null-terminator is there */
    printf("\n");
}

Program output:

hi!

So strings aren’t really all that special in C. They’re just arrays with a special terminating character, and a little bit of syntax support to construct them (i.e. "this syntax"). So what’s there to know about strings in C?

2.2.1 string.h Functions

Working with strings is not C’s strong point. However, you have to handle strings in every language, and C provides a number of functions to do so. You can read about each of these functions with man 3 <function>.

2.2.1.1 Core String Operations

• strlen - How many characters is a string (not including the null-terminator)?
• strcmp - Compare two strings, return 0 if they are the same, or -1 or 1, depending on which is lexographically less than the other. Similar in purpose to equals in Java.
• strcpy - Copy into a string the contents of another string.
• strcat - Concatenate, or append onto the end of a string, another string.
• strdup - Duplicate a string by mallocing a new string, and copying the string into it (you have to free the string later!).
• snprintf - You’re familiar with printf, but snprintf enables you to “print” into a string! This gives you a lot of flexibility in easily constructing strings. A downside is that you don’t really know how big the resulting string is, so the n in the name is the maximum length of the string you’re creating.

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

int
main(void)
{
    char result[256] = {'\0', };                /* initialize string to be "" */
    char *a = "hello", *b = "world";
    int c = 42;
    int ret;
    char *d;

    assert(strcmp(a, b) != 0);                  /* these strings are different */

    strcat(result, a);
    strcat(result, " ");
    strcat(result, b);
    assert(strcmp(result, "hello world") == 0); /* should have constructed this string properly */

    d = strdup(result);
    assert(strcmp(d, result) == 0);             /* a duplicate should be equal */
    free(d);

    strcpy(result, "");                         /* reset the `result` to an empty string */

    ret = snprintf(result, 255, "%s %s and also %d", a, b, c);
    printf("\"%s\" has length %d\n", result, ret);
}

Program output:

"hello world and also 42" has length 23

Many of these functions raise an important question: What happens if one of the strings is not large enough to hold the data being put into it? If you want to strcat a long string into a small character array, what happens? This leads us to a simple fact…

It is easy to use the string functions incorrectly. Many of these functions also have a strnX variant where X is the operation (strnlen, strncmp, etc..). These are safer variants of the string functions. The key insight here is that if a string is derived from a user, it might not actually be a proper string! It might not, for example, have a null-terminator – uh oh! In that case, many of the above functions will keep on iterating past the end of the buffer

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

char usr_str[8];

int
main(void)
{
    char my_str[4];

    /*
     * This use of `strcpy` isn't bugged as we know the explicit string is 7 zs,
     * and 1 null-terminator, which can fit in `usr_str`.
     */
    strcpy(usr_str, "zzzzzzz");

    /*
     * Also fine: lets limit the copy to 3 bytes, then add a null-terminator ourself
     * (`strlcpy` would do this for us)
     */
    strncpy(my_str, usr_str, 3);
    my_str[3] = '\0';

    printf("%s\n", my_str);
    fflush(stdout);  /* don't mind me, making sure that your print outs happen */

    /*
     * However, note that `strlen(usr_str)` is larger than the size of `my_str` (4),
     * so we copy *past* the buffer size of `my_str`. This is called a "buffer overflow".
     */
    strcpy(my_str, usr_str);

    return 0;
}

Program output:

zzz
*** stack smashing detected ***: terminated
make[1]: *** [Makefile:30: inline_exec] Aborted (core dumped)

2.2.1.2 Parsing Strings

While many of the previous functions have to do with creating and modifying strings, computers frequently need to “parse”, or try to understand the different parts of, a string. Some examples:

• The code we write in .c or .java files is just a long string, and the programming language needs to parse the string to understand what commands you’re trying to issue to the computer.
• The shell must parse your commands to determine which actions to perform.
• Webpages are simply a collection of html code (along with other assets), and a browser needs to parse it to determine what to display.
• The markdown text for this lecture is parsed by pandoc to generate a pdf and html.

Some of the core functions that help us parse strings include:

• strtol - Pull an integer out of a string. Converts the first part of a string into a long int, and also returns an endptr which points to the character in the string where the conversion into a number stopped. If it cannot find an integer, it will return 0, and endptr is set to point to the start of the string.
• strtok - Iterate through a string, and find the first instance of one of a number of specific characters, and return the string leading up to that character. This is called multiple times to iterate through the string, each time extracting the substring up to the specific characters. See the example in the man page for strtok for an example.
• strstr - Try and find a string (the “needle”) in another string (the “haystack”), and return a pointer to it (or NULL if you don’t find it). As such, it finds a string in another string (thus strstr).
• sscanf - A versatile function will enables a format string (e.g. as used in printf) to specify the format of the string, and extract out digits and substrings.

Some examples:

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

int
main(void)
{
    char *input = "1 42 the secret to everything";
    char *inputdup;
    char *substr;
    char *substr_saved;
    long int extracted;
    char sec[32];

    extracted = strtol(input, &substr, 10);                               /* pull out the first two integers */
    printf("extracted %ld, remaining string: \"%s\"\n", extracted, substr);
    extracted = strtol(substr, &substr, 10);
    printf("extracted %ld, remaining string: \"%s\"\n", extracted, substr);
    substr_saved = substr;

    /* what happens when we cannot extract a long? */
    extracted = strtol(substr_saved, &substr, 10);
    assert(extracted == 0 && substr_saved == substr);                     /* verify that we couldn't extract an integer */

    assert(strcmp(strstr(input, "secret"), "secret to everything") == 0); /* find secret substring */

    sscanf(input, "1 %ld the %s to everything", &extracted, sec);         /* extract out the number and the secret */
    printf("%ld and \"%s\"\n", extracted, sec);

    printf("Using strtok to parse through a string finding substrings separated by 'h' or 't':\n");
    inputdup = strdup(input);                                            /* strtok will modify the string, lets copy it */
    for (substr = strtok(inputdup, "ht"); substr != NULL; substr = strtok(NULL, "ht")) {
        printf("[%s]\n", substr);
    }

    return 0;
}

Program output:

extracted 1, remaining string: " 42 the secret to everything"
extracted 42, remaining string: " the secret to everything"
42 and "secret"
Using strtok to parse through a string finding substrings separated by 'h' or 't':
[1 42 ]
[e secre]
[ ]
[o every]
[ing]

2.2.2 Bonus: Explicit Strings

When you use an explicit string (e.g. "imma string") in your code, you’re actually asking C to allocate the string in global memory. This has some strange side-effects:

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

char c[5];

int
main(void)
{
    char *a = "blah";
    char *b = "blah";

    strncpy(c, a, 5);

    printf("%s%s%s\n", a, b, c);
    /* compare the three pointers */
    printf("%p == %p != %p\n", a, b, c);

    return 0;
}

Program output:

blahblahblah
0x565d43a13004 == 0x565d43a13004 != 0x565d43a15011

The C compiler and linker are smart enough to see that if you have already used a string with a specific value (in this case "clone"), it will avoid allocating a copy of that string, and will just reuse the previous value. Generally, it doesn’t make much sense to look at the address of strings, and certainly you should not compare them. You can see in this example how you must compare strings for equality using strncmp, and not to compare pointers.

2.3 API Design and Concerns

When programming in C, you’ll see quite a few APIs. Throughout the class, we’ll see quite a few APIs, most documented in man pages. It takes some practice in reading man pages to get what you need from them. One of the things that helps the most is to understand a few common patterns and requirements that you find these APIs, and in C programming in general.

2.3.1 Return Values

Function’s often need to return multiple values. C does not provide a means to return more than one value, thus is forced to use pointers. To understand this, lets look at the multiple ways that pointers can be used as function arguments.

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

/*
 * `arg` is used to pass an argument that happens to be an array here. In contrast,
 * `ret` is a *second return value*. This function will set the value that `ret` points
 * to -- which happens to be `retval` in the `main` stack frame -- to the value we are
 * getting from the array.
 */
int
get(int *arg, int offset, int *ret)
{
    if (arg == NULL) return -1;

    *ret = arg[offset];

    return 0;
}

/*
 * Again, the array is passed in as the first argument, but this time it is used to
 * store the new value.
 */
int
set(int *ret_val, int offset, int value)
{
    if (ret_val == NULL) return -1;

    ret_val[offset] = value;

    return 0;
}

/*
 * `arrdup`'s job is to duplicate an array by allocating and populating
 * a new array. It will return `0` or not `0` on success/failure. Thus
 * the new array must be returned using pointer arguments. `ret_allocated`
 * is a pointer to a pointer to an array in the calling function, and it
 * is used to return the new array.
 */
int
arrdup(int **ret_allocated, int *args, size_t args_size)
{
    size_t i;
    int *newarr;

    if (ret_allocated == NULL) return -1;

    newarr = calloc(args_size, sizeof(int)); /* 1 below */
    if (newarr == NULL) return -1;

    for (i = 0; i < args_size; i++) {
        newarr[i] = args[i];
    }
    *ret_allocated = newarr; /* 2 and 3 below */

    return 0;
}
/*
 * Lets draw this one. The stack setup when we call `arrdup`:
 *
 * |               |
 * +-main----------+
 * | arr           |<---+
 * | dup           |<-+ |
 * | ...           |  | |
 * +-arrdup--------+  | |
 * | ret_allocated |--+ |
 * | args          |----+
 * | ...           |
 * +---------------+
 *
 * `ret_allocated` points to `dup` in `main`.
 *
 *
 *    3. *ret_allocated = newarr
 *                          ^
 *                          |
 *            ,-------------'
 *           |
 * |         |     |
 * +-main----|-----+
 * | arr     |     |
 * | dup ---'  <------+
 * | ...           |  | -- 2. *ret_allocated
 * +-arrdup--------+  |
 * | ret_allocated ---+
 * | args          |
 * | newarr --------------> 1. calloc(...)
 * +---------------+
 *
 * 1. `arrdup` calls `calloc` to allocate on the heap
 * 2. Dereferencing `ret_allocated` gives us access to `dup`
 * 3. thus we can set dup equal to the new heap memory
 *
 * This effectively enables us to return the new memory into the
 * `dup` variable in main.
 */



int
main(void)
{
    int arr[] = {0, 1, 2, 3};
    int *dup;
    int retval;

    assert(get(arr, 2, &retval) == 0 && retval == 2);
    assert(set(arr, 2, 4) == 0);
    assert(get(arr, 2, &retval) == 0 && retval == 4);
    assert(arrdup(&dup, arr, 4) == 0);
    assert(get(dup, 2, &retval) == 0 && retval == 4);
    free(dup);

    printf("no errors!");

    return 0;
}

Program output:

no errors!

2.3.2 Errors

The first question is how we can detect that some error occurred within a function we have called? We’ll separate functions into two different classes:

1. Functions that return pointers. Functions that return pointers (e.g. that have declarations of the form type *fn(...)) are often relatively straightforward. If they return NULL, then an error occurred; otherwise the returned pointer can be used. malloc is an example here.
2. Functions that return integers. Integers are used as a relatively flexible indication of the output of a function. Is it common for a -1 to indicate an error. Sometimes any negative value indicates an error, each negative value designating that a different error occurred. Non-negative values indicate success. If a function wishes to return a binary success or failure, you’ll see that many APIs (counter-intuitively) return 0 for success, and -1 for failure.

It is common that you want more information than the return value can give you. You want more information about why the failure happened so that you can debug more easily. The errno variable is UNIX’s solution to this (see its man page), and can be referenced if you include errno.h. errno is simply an integer where specific values represent specific errors. You can view these values by looking them up in the source⁵ or, you can ask the errno program⁶. For example:

$ errno -l
EPERM 1 Operation not permitted
ENOENT 2 No such file or directory
ESRCH 3 No such process
EINTR 4 Interrupted system call
EIO 5 Input/output error
...

You can look up specific values:

$ errno 28
ENOSPC 28 No space left on device

You can imagine how that error might occur. What if you’re trying to add files on disk, and the disk runs out of room!?

If you want your program to print a useful error when you encounter such a problem, you can use the perror function (see its man page for documentation) to print out an error, or strerror (via string.h) if you just want a string corresponding to the error.

#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>

int
main(void)
{
    char *ret;

    printf("Lets get greedy: allocate %ld bytes!\n", LONG_MAX);
    ret = malloc(LONG_MAX);
    if (ret == NULL) {
        printf("Error: errno value %d and description: %s\n", errno, strerror(errno));
        fflush(stdout);
        perror("Error allocating memory");

        return -1;
    }

    return 0;
}

Program output:

Lets get greedy: allocate 9223372036854775807 bytes!
Error: errno value 12 and description: Cannot allocate memory
Error allocating memory: Cannot allocate memory
make[1]: *** [Makefile:30: inline_exec] Error 255

(Note: when you return from a program with a non-zero value, it designates that your program had an error. This is why we see the make error when it runs your program.)

To understand the return value of UNIX library functions:

• look at the function return values to understand the type (and identify if it is returning an int or a pointer)

SYNOPSIS
       #include <stdlib.h>

       void *malloc(size_t size);
       ...

• Read through the description of the function(s).
• Read through the RETURN VALUE and ERRORS sections of the man page.

RETURN VALUE
       The malloc() and calloc() functions return a pointer to the allocated memory, which is  suitably  aligned  for
       any  built-in type.  On error, these functions return NULL.  NULL may also be returned by a successful call to
       malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero.
...
ERRORS
       calloc(), malloc(), realloc(), and reallocarray() can fail with the following error:

       ENOMEM Out  of  memory.
       ...

This explains why we got the error we did.

2.3.3 Memory Ownership

One of the last, but most challenging aspects of APIs in C is that of memory ownership. The big question is: when a pointer passed into a function, or returned from a function, who is responsible for freeing the memory? This is due to a combination of factors, mainly:

1. C requires that memory is explicitly freed, so someone has to do it, and it should be freed only once, and
2. pointers are passed around freely and frequently in C, so somehow the function caller and callee have to understand who “owns” each of those pointers.

It is easiest to understand this issue through the concept of ownership: simply put, the owner of a piece of memory is the one that should either free it, or pass it to another part of the code that becomes the owner. In contrast, a caller can pass a pointer to memory into a function allowing it to borrow that memory, but the function does not free it, and after it returns it should not further access the memory. There are three general patterns:

• A caller passes a pointer into a function, and passes the ownership of that data to the function. This is common for data-structures whose job is to take a pointer of data to store, and at that point, they own the memory. Think: if we enqueue data into a queue.

  Examples: The key-value store’s put function owns the passed in data (assuming it takes a void *.

• A function returns a pointer to the function caller and passes the ownership to the caller. The caller must later free the data. This is also common in data-structures when we wish to retrieve the data. Think: if we dequeue data from a queue.

  Examples: strdup creates a new string, expecting the caller to free it.

• A caller passes a pointer into a function, but only allows the function to borrow the data. Thus the caller still owns the memory (thus is still responsible to free the data) after the function returns, and the function should not maintain any references to the data. Think: most of the string functions that take a string as an argument, perform some operation on it, and return expecting the caller to still free the string.

  Examples: Most other functions we’ve seen borrow pointers, perform operations, and then don’t maintain references to them.

• A function returns a pointer to the function caller that enables the caller to borrow the data. This requires a difficult constraint: the caller can access the data, but must not maintain a pointer to it after the function or API (that still owns the data) frees it.

  Examples: The key-value store’s get function transfers ownership to the caller.

The memory ownership constraints are an agreement between the calling function, and a function being called.

2.4 Exercises

2.4.1 Stack Allocation

An old interview question:

How can you write a function that determines if the execution stack grows upwards (from lower addresses to higher), or downwards?

Write this function!

2.4.2 Understanding Memory Ownership

Lets look at a simple key-value store that needs to learn to be more careful about memory. Above each function, we specify the ownership of pointers being passed – either passing ownership, or borrowing the memory. The current implementations do not adhere to these specifications.

#include <string.h>
#include <malloc.h>

/*
 * Lets just use a single key/value as a proxy for an entire kv/store.
 * You can assume that the stored values are strings, so `strdup` can
 * allocate the memory for and copy the values. You absolutely will
 * have to use `strdup` in some of the functions.
 */
static int   kv_key;
static char *kv_value;

/**
 * The returned value should not be maintained in the data-structure
 * and should be `free`d by the caller.
 */
char *
get_pass_ownership(int key)
{
    if (key != kv_key) return NULL;

    return kv_value;
}

/**
 * Pointers to the returned value are maintained in this data-structure
 * and it will be `free`d by the data-structure, not by the caller
 */
char *
get_borrow(int key)
{
    if (key != kv_key) return NULL;

    return kv_value;
}

/**
 * Pointers to the `value` passed as the second argument are maintained by
 * the caller, thus the `value` is borrowed here. The `value` will be `free`d
 * by the caller.
 */
void
set_borrow(int key, char *value)
{
    /* What do we do with `kv_value`? Do we `strdup` anything? */
    kv_key   = key;
    kv_value = value;

    return;
}

/**
 * Pointers to the `value` passed as the second argument are not maintained by
 * the caller, thus the `value` should be `free`d by this data-structure.
 */
void
set_pass_ownership(int key, char *value)
{
    /* What do we do with `kv_value`? Do we `strdup` anything? */
    kv_key   = key;
    kv_value = value;

    return;
}

int
main(void)
{
    /* The values we pass in. */
    char *v_p2p = strdup("value1"); /* calls `malloc` ! */
    char *v_p2b = strdup("value2");
    char *v_b2p = strdup("value3");
    char *v_b2b = strdup("value4");

    /* The return values */
    char *r_p2p, *r_p2b, *r_b2p, *r_b2b;

    /* p2p: passing ownership on set, passing ownership on get */
    set_pass_ownership(0, v_p2p);
    r_p2p = get_pass_ownership(0);
    /* The question: should we `free(v_p2p)`?, `free(r_p2p)`? */

    /* p2b: passing ownership on set, borrowing memory for get */
    set_pass_ownership(0, v_p2b);
    r_p2b = get_borrow(0);
    /* The question: should we `free(v_p2b)`?, `free(r_p2b)`? */

    /* b2p: borrowing ownership on set, passing ownership on get */
    set_borrow(0, v_b2p);
    r_b2p = get_pass_ownership(0);
    /* The question: should we `free(v_b2p)`?, `free(r_b2p)`? */

    /* b2b: borrowing ownership on set, borrowing on get */
    set_borrow(0, v_b2b);
    r_b2b = get_borrow(0);
    /* The question: should we `free(v_b2b)`?, `free(r_b2b)`? */

    if (kv_value) free(kv_value);

    printf("Looks like success!...but wait till we valgrind; then ;-(\n");

    return 0;
}

Program output:

Looks like success!...but wait till we valgrind; then ;-(

The above code is hopelessly broken. Run it in valgrind to see.

Tasks:

• In the above code, implement the malloc/free/strdup operations that are necessary both in the key-value implementation, and in the client (main) to make both the caller and callee abide by the memory ownership constraints.
• In which cases can stack allocation of the values be used in main? Why?
• In which cases can stack allocation of the values in the key-value store (i.e. in get/set) be used? Why?

3 Processes

Programming is hard. Really hard. When you write a program, you have to consider complex logic and the design of esoteric data-structures, all while desperately trying to avoid errors. It is an exercise that challenges all of our logical, creative, and risk management facilities. As such, programming is the act of methodically conquering complexity with our ability to abstract. We walk on the knives-edge of our own abstractions where we can barely, just barely, make progress and engineer amazing systems.

Imagine if when programming and debugging, we had to consider the actions and faults of all other programs running in the system? If your program crashed because one of your colleagues’ program had a bug, how could you make progress?

Luckily, we stand on the abstractions of those that came before us. A key abstraction provided by systems is that of isolation - that one program cannot arbitrarily interfere with the execution of another. This isolation is a core provision of Operating Systems (OSes), and a core abstraction they provide is the process. At the highest-level, each process can only corrupt its own memory, and a process that goes into an infinite loop cannot prevent another process for executing.

A process has a number of properties including:

• It contains the set of memory that is only accessible to that process. This memory includes the code, global data, stack, and dynamically allocated memory in the heap. Different processes have disjoint sets of memory, thus no matter how one process alters its own memory, it won’t interfere with the data-structures of another.
• A number of descriptors identified by integers that enable the process to access the “resources” of the surrounding system including the file system, networking, and communication with other processes. When we printf, we interact with the descriptor to output to the terminal. The OS prevents processes from accessing and changing resources they shouldn’t have access to.
• A set of unique identifiers including a process identifier (pid).
• The “current working directory” for the process, analogous to pwd.
• A owning user (e.g. gparmer) for whom the process executes on the behalf of.
• Each process has a parent - the process that created it, and that has the ability and responsibility oversee it (like a normal, human parent).
• Arguments to the process often passed on the command line.
• Environment variables that give the process information about the system’s configuration.

Throughout the class we’ll uncover more and more of these properties, but in this lecture, we’ll focus on the lifecycle of a process, and its relationship to its parent. Processes are the abstraction that provide isolation between users, and between computations, thus it is the core of the security of the system.

3.1 History: UNIX, POSIX, and Linux

UNIX is an old system, having its origins in 1969 at Bell Labs when it was created by Ken Thompson and Dennis Ritchie⁷. Time has shown it is an “oldie but goodie” – as most popular OSes are derived from it (OSX, Linux, Android, …). In the OS class, you’ll dive into an implementation of UNIX very close to what it was in those early years! The original paper is striking in how uninteresting it is to most modern readers. UNIX is so profound that it has defined what is “normal” in most OSes.

UNIX Philosophy: A core philosophy of UNIX is that applications should not be written as huge monolithic collections of millions of lines of code, and should instead be composed of smaller programs, each focusing on “doing one thing well”. Programs focus on inputting text, and outputting text. Pipelines of processes take a stream of text, and process on it, process after process to get an output. The final program is a composition of these processes composed to together using pipelines.

In the early years, many different UNIX variants were competing for market-share along-side the likes of DOS, Windows, OS2, etc… This led to differences between the UNIX variants which prevented programmers from effectively writing programs that would work across the variants. In response to this, in the late 1980s, POSIX standardized many aspects of UNIX including command-line programs and the standard library APIs. man pages are documentation for what is often part of the POSIX specification. I’ll use the term UNIX throughout the class, but often mean POSIX. You can think of Linux as an implementation of POSIX and as a variant of UNIX.

UNIX has been taken into many different directions. Android and iOS layer a mobile runtime on top of UNIX; OSX and Ubuntu layer modern graphics and system management on top of UNIX, and even Windows Subsystem for Linux (WSL) enables you to run a POSIX environment inside of Windows. In many ways, UNIX has won. However, it has won be being adapted to different domains – you might be a little hard-pressed looking at the APIs for some of those systems to understand that it is UNIX under the hood. Regardless, in this class, we’ll be diving into UNIX and its APIs to better understand the core technology underlying most systems we use.

The core UNIX philosophy endures, but has changed shape. In addition to the pervasive deployment of UNIX, Python is popular as it is has good support to compose together disparate services and libraries, and applications are frequently compositions of various REST/CRUD webservice APIs, and json is the unified language in which data is shared.

3.2 Process: Life and Death

When we construct a pipeline of processes…

$ ps aux | grep gparmer

we’re executing two processes that separately run the code of the programs ps and grep. The shell is the parent process that creates the ps and grep processes. It ensures the descriptor for the output of the ps process sends its data to the descriptor in the grep process for its input.

What are the functions involved in the creation, termination, and coordination between processes?

• fork - Create a new, child, process from the state of the calling process.
• getpid, getppid - get the unique identifier (the Process ID, or pid) for the process, or for its parent.
• exit - This is the function to terminate a process.
• wait - A parent awaits a child exiting.
• exec - Execute a new program using the current process⁸.

Lets be a little more specific. A program is an executable file. We see them in the file system (for example, see ls /bin), and create them when we compile our programs. When you compile your C programs, the generated file that you can execute, is a program. A process is an executing program with the previously mentioned characteristics (disjoint memory, descriptors to resources, etc…).

First, lets look at fork:

#include <stdio.h>
#include <unistd.h> /* fork, getpid */

int
main(void)
{
    pid_t pid; /* "process identifier" */

    printf("pre-fork:\n\t parent pid %d\n", getpid());
    fflush(stdout);
    pid = fork(); /* so much complexity in such a simple call! */
    printf("post-fork:\n\treturned %d,\n\tcurrent pid %d\n\tparent pid %d\n",
           pid, getpid(), getppid());

    return 0;
}

Program output:

pre-fork:
     parent pid 1127875
post-fork:
    returned 1127876,
    current pid 1127875
    parent pid 1127866
post-fork:
    returned 0,
    current pid 1127876
    parent pid 2850

We can see the fork creates a new process that continues running the same code, but has a separate set of memory. A few observations:

1. In this case, you can see that the pid variable is different for the two processes. In fact, after the fork call, all of memory is copied into the new process and is disjoint from that of the parent.
2. The getpid function returns the current process’ process identifier.
3. fork returns two values - one in the parent in which it returns the process id of the newly created child, and one in the child in which it returns 0. This return value is one of the main indicators of if the current process is the parent, or the child.

So much complexity for such a simple function prototype!

exit and wait. In contrast to fork that creates a new process, exit is the function that used to terminate the current process. exit’s integer argument is the “exit status” – 0 is equivalent to EXIT_SUCCESS, and denotes a successful execution of the program, and -1 is EXIT_FAILURE, and denotes execution failure. The return value from main is also this exit status. Where is the exit status used?

Parent processes have the responsibility to manage their children. This starts with the wait function. A parent that calls wait will “wait” for the child to exit. Then, wait enables a parent to retrieve the exit status of the child.

The relationship between wait (in the parent), and exit or return from main (in the child) is a little hard to understand. A figure always helps…

Adopting orphaned children. What happens if a parent exits before a child? Who is allowed to wait and get the child’s status? Intuition might tell you that it is the grandparent but that is not the case. Most programs are not written to understand that wait might return a pid other than ones they’ve created. Instead, if a parent terminates, the init process – the processes that is the ancestor of all processes – adopts the child, and waits for it. We’ll dive into init later in the class.

Interpreting exit status. Despite wait’s status return value being a simple int, the bits of that integer mean very specific things. See the man page for wait for details, but we can use a set of functions (really “macros”) to interpret the status value:

• WIFEXITED(status) will return 0 if the process didn’t exit (e.g. if it faulted instead), and non-0 otherwise.
• WEXITSTATUS(status) will get the intuitive integer value that was passed to exit (or returned from main), but assumes that this value is only 8 bits large, max (thus has a maximum value of 256).

3.2.1 Process Example

#include <unistd.h> /* fork, getpid */
#include <wait.h>   /* wait */
#include <stdlib.h> /* exit */
#include <stdio.h>

int
main(void)
{
    pid_t pid, child_pid;
    int i, status;

    /* Make four children. */
    for (i = 0; i < 4; i++) {
        pid = fork();
        if (pid == 0) { /* Are we the child? */
            printf("Child %d exiting with %d\n", getpid(), -i);
            if (i % 2 == 0) exit(-i);   /* terminate immediately! */
            else            return -i;  /* also, terminate */
        }
    }

    /*
     * We are the parent! Loop until wait returns `-1`, thus there are no more children. Note
     * that this strange syntax says "take the return value from `wait`, put it into the variable
     * `child_pid`, then compare that variable to `-1`".
     */
    while ((child_pid = wait(&status)) != -1) { /* no more children when `wait` returns `-1`! */
        /* wait treats the `status` as the second return value */
        if (WIFEXITED(status)) {
            /* Question: why the `(char)` cast? */
            printf("Child %d exited with exit status %d\n", child_pid, (char)WEXITSTATUS(status));
        }
    }

    return 0;
}

Program output:

Child 1127895 exiting with 0
Child 1127896 exiting with -1
Child 1127897 exiting with -2
Child 1127898 exiting with -3
Child 1127895 exited with exit status 0
Child 1127896 exited with exit status -1
Child 1127897 exited with exit status -2
Child 1127898 exited with exit status -3

3.2.2 Non-determinism Everywhere: Concurrency

The output of this program can actually vary, somewhat arbitrarily, in the following way: any of the output lines can be reordered with respect to any other, except that the parent’s print out for a specific child must come after it.

For example, all of the following are possible:

Child 4579 exiting with 0
Child 4580 exiting with -1
Child 4581 exiting with -2
Child 4582 exiting with -3
Child 4579 exited with exit status 0
Child 4580 exited with exit status -1
Child 4581 exited with exit status -2
Child 4582 exited with exit status -3

Child 4579 exiting with 0
Child 4579 exited with exit status 0
Child 4580 exiting with -1
Child 4580 exited with exit status -1
Child 4581 exiting with -2
Child 4581 exited with exit status -2
Child 4582 exiting with -3
Child 4582 exited with exit status -3

Child 4582 exiting with -3
Child 4582 exited with exit status -3
Child 4581 exiting with -2
Child 4581 exited with exit status -2
Child 4580 exiting with -1
Child 4580 exited with exit status -1
Child 4579 exiting with 0
Child 4579 exited with exit status 0

This non-determinism is a product of the isolation that is provided by processes. The OS switches back and forth between processes frequently (up to thousands of time per second!) so that if one goes into an infinite loop, others will still make progress. But this also means that the OS can choose to run any of the processes that are trying to execute at any point in time! We cannot predict the order of execution, completion, or wait notification. This non-deterministic execution is called concurrency. You’ll want to keep this in mind as you continue to learn the process APIs, and when we talk about IPC, later.

3.2.3 Taking Actions on exit

Lets dive into exit a little bit.

#include <stdlib.h>

int
main(void)
{
    exit(EXIT_SUCCESS);
}

Believe it or not, this is identical to

#include <stdlib.h>

int
main(void)
{
    return EXIT_SUCCESS;
}

…because when main returns, it calls exit.

Investigating main return → exit via gdb. You can see this by diving into the return.c program with gdb -tui, breakpointing before the return (e.g. b 5), and single-stepping through the program. You’ll want to layout asm to drop into “assembly mode”, and single step through the assembly and if you want to step through it instruction at a time use stepi or si. You can see that it ends up calling __GI_exit. __GI_* functions are glibc internal functions, so we see that libc is actually calling main, and when it returns, it is then going through its logic for exit.

Though exit is a relatively simple API, it has a few interesting features.

• on_exit which takes a function pointer to be called upon returning from main or calling exit. The function receives the status, and an argument pass to on_exit. So we can see that calling exit does not immediately terminate the process!
• atexit takes a simpler function pointer (that doesn’t receive any arguments) to call at exit.
• _exit terminates a process without calling any of the function pointers set up by on_exit nor atexit.

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

int value = 0;

void
destructor(int status, void *data)
{
    int *val = data;

    printf("post-exit: status %d, data %d\n", status, *val);
}

int
main(void) {
    on_exit(destructor, &value); /* `value` will get passed to the function */

    value = 1;

    printf("pre-exit\n");

    return 0;
}

Program output:

pre-exit
post-exit: status 0, data 1

3.2.4 fork Questions

1. How many processes (not including the initial one) are created in the following?

   #include <unistd.h>
   
   int
   main(void)
   {
       fork();
       fork();
   
       return 0;
   }

2. What are the possible outputs for:

   #include <unistd.h>
   #include <stdio.h>
   #include <sys/wait.h>
   
   int
   main(void)
   {
       pid_t parent = getpid();
       pid_t child;
   
       child = fork();
       if (getpid() == parent) {
           printf("p");
           wait(NULL); /* why is `NULL` OK here? */
           printf("w");
       } else {
           printf("c");
       }
   
       return 0;
   }

3.3 Executing a Program

Recall, a program is an executable that you store in your file-system. These are the output of your compilation, the “binaries”. So fork lets us make a new process from an existing process, both of which are executing within a single program. But how do we execute a new program?

The exec family of system calls will do the following:

• Stop executing in the current process.
• Reclaim all memory within the current process.
• Load the target program into the process.
• Start executing in the target program (i.e. starting normally, resulting in main execution).

The core insight is that the same process continues execution; it simply continues execution in the new program. This is a little unnatural, but has a few handy side-effects:

• The execution of the new program inherits the process identifier (pid_t) and the parent/child relationships of the process.
• Comparably, the descriptors are inherited into the new program’s execution.
• The environment variables (see section below) pass to the new program’s execution.
• Many other process properties are comparably inherited. With the exception of the process memory, you can assume, by default, that process properties are inherited across an exec.

3.3.1 exec APIs

There are a few ways to execute a program:

• execl
• execlp
• execle
• execv
• execvp

The naming scheme is quite annoying and hard to remember, but the man page has a decent summary. The trailing characters correspond to specific operations that differ in how the command-line arguments are passed to the main (l means pass the arguments to this exec call to the program, while v means pass the arguments as an array of the arguments into the exec call), how the program’s path is specified (by default, an “absolute path” starting with / must be used, but in a v variant, the binary is looked up using comparable logic to your shell), and how environment variables are passed to the program. For now, we’ll simply use execvp, and cover the rest in subsequent sections.

#include <stdio.h>
#include <assert.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdlib.h>

int
main(int argc, char *argv[])
{
    int status;
    pid_t pid;

    if (fork() == 0) { /* child */
        char *args[] = {"./03/hw.bin", NULL}; /* requires a NULL-terminated array of arguments */

        /* here we use a relative path (one that starts with `.`), so we must use the `p` postfix */
        if (execvp("./03/hw.bin", args)) {
            /*
             * This should really *not return* in the nromal case. This memory context
             * goes away when we `exec`, and is replaced by the new program, thus simply
             * removing this code. Thus, this will only continue executing if an error
             * occured.
             */
            perror("exec");

            return EXIT_FAILURE;
        }
    }

    pid = wait(&status);
    assert(pid != -1);

    printf("Parent: status %d\n", WEXITSTATUS(status));

    return 0;
}

Program output:

hello world!
Parent: status 42

3.4 Command Line Arguments

I think that we likely have a decent intuition about what the command-line arguments are`:

$ ls /bin /sbin

The ls program takes two arguments, /bin and /sbin. How does ls access those arguments?

Lets look at a chain of programs that exec each other. The first program (that you see here) is called inline_exec_tmp, and the programs 03/args?.c are subsequently executed.

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

char *prog = "./03/args1.bin";

int
main(int argc, char *argv[])
{
    char *args[] = {prog, "hello", "world", NULL};

    if (argc != 1) return EXIT_FAILURE;

    printf("First program, arg 1: %s\n", argv[0]);
    fflush(stdout);

    /* lets execute args1 with some arguments! */
    if (execvp(prog, args)) {
        perror("exec");
        return EXIT_FAILURE;
    }

    return 0;
}

Program output:

First program, arg 1: ./inline_exec_tmp
Inside ./03/args2.bin
arg 0: ./03/args2.bin
arg 1: hello
arg 2: world

args1.c is

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

char *prog = "./03/args2.bin";

int
main(int argc, char *argv[])
{
    int i;
    char **args;        /* an array of strings */

    printf("Inside %s\n", argv[0]);

    /* lets just pass the arguments on through to args2! */
    args = calloc(argc + 1, sizeof(char *));
    assert(args);

    args[0] = prog;
    for (i = 1; i < argc; i++) {
        args[i] = argv[i];
    }
    args[i] = NULL; /* the arguments need to be `NULL`-terminated */

    if (execvp(prog, args)) {
        perror("exec");

        return EXIT_FAILURE;
    }

    return 0;
}

…and args2.c is

#include <stdio.h>

int
main(int argc, char *argv[])
{
    int i;

    printf("Inside %s\n", argv[0]);

    for (i = 0; i < argc; i++) {
        printf("arg %d: %s\n", i, argv[i]);
    }

    return 0;
}