Programming in C

The second-year C programming course, at EPITA Toulouse, in 2019-2020.

Eight chapters, a supplement and seven exercise sheets. Chapters 0 and 1 place C in context and show how a source file becomes a program; chapters 2 to 4 are the heart of the language: pointers, memory, data structures. The supplement that follows chapter 2, “The memory table”, is my way of explaining variables and pointers to those who have not understood C: it is missing, I find, from every C course. Chapters 5 to 7 talk to the system: files and pipes, processes, then threads.

The examples compile without warnings with gcc -std=c11 -Wall -Wextra -Werror on Linux, except those that are there to show a warning or an error; those that touch the system also need -D_DEFAULT_SOURCE or -pthread. This is stated each time. Type them in, compile them, modify them: a C program is only understood by running it, and by making it crash.

Lecture notes

1. Introduction : Why C, what “compiled” and “low-level” mean, and the few writing rules we will keep to all semester.
2. Compiling and running : From the source file to the running program - preprocessor, compiler, assembler, linker and loader. The sections of the executable (text, rodata, data, bss) and their permissions. gcc's options, programs in several files, header files and make.
3. Pointers and arrays : An address is a value like any other. The & and * operators, passing by address, void *, arrays and what sets them apart from pointers, pointer arithmetic, strings and const.
4. The memory table : Following pointers by hand without drawing arrows - one row per variable, with its address, its contents, its name, its type and its size. A pointer to a pointer, an array, passing by address and a string, read in the table. Then why only the size matters, the type being only an illusion, and the sizes to know depending on the machine.
5. A program's memory : Where data lives - static area, stack and heap. Constants and initialisers, the lifetime of local variables, malloc and free, virtual memory, brk and mmap, pools and arenas. And two tools to find memory errors.
6. Data structures : Structures and typedef, abstract types, and the classics of algorithmics written in C - linked lists, queues, binary trees, vectors. Passing a pointer by value or by address, and reading it in the signature.
7. Input and output : Under Unix, everything is a file - descriptors, read and write, opening and closing, seeking, redirecting, pipes. Then the buffers of stdio.h, and a file seen as memory with mmap.
8. Processes : Launching programs from your own code, as a shell does - fork to duplicate a process, wait to wait for it to end, exec to make it run another program. Orphans and zombies, redirections and pipes between processes, and signals.
9. Parallelism : Several threads of execution sharing the same memory - why a simple counter goes wrong, how to protect a critical section (Peterson, locks, conditions, semaphores), the producer-consumer problem, and programming with POSIX threads.

Exercise sheets

1. Compiling and running : Recognise which stage fails, read what the preprocessor does, split a program into modules properly, and write a Makefile. Chapter 1.
2. Pointers and arrays : Follow pointers by hand, predict sizeof values, find classic bugs, then write code with addresses - minmax, strings, matrices. Chapter 2.
3. The memory of a program : Place each piece of data in its area, outwit macros, find leaks and overflows, then write code with malloc - concatenation, matrices, and a recycling pool. Chapter 3.
4. Data structures : Read signatures, write list functions with a pointer to a pointer, find the bugs in a module, a stack and a binary search tree as abstract types. Chapter 4.
5. Input and output : Predict what a program writes depending on whether its output goes to the terminal or to a file, write wc, tee and tail with read, write and lseek, follow shared file offsets, send integers through a pipe. Chapter 5.
6. Processes : Count the processes created by fork, understand what fork copies, write system and a small shell, reap your zombies, count signals. Chapter 6.
7. Parallelism : Interleavings and lost updates, finding and fixing a deadlock, debugging a bounded queue, passing arguments to threads, a rendezvous with semaphores, and the cost of a lock. Chapter 7.