Why C?

Fast

Good optimizing compilers

Not too high-level (Java, Python, Lisp)
Not too low-level (Assembly)
Easy manipulation of bits, bytes, words, and pointers (addresses)
Many C types map directly to registers

int x =3, y = 7;

x = x + y;

==>

movl $3, %eax

movl $7, %ebx

addl %ebx, %eax

Explicit memory allocation
Most OS kernels written in C with some assembly
See the Go language

C Basics

In C there are two main concepts

Functions
Variables

Global
Local

File structure

.c files hold functions and variable definitions
.h files hold macros, function and variable declarations

Comments

/* comment here, can span multiple lines */
// comment to end of line

Blocks enclosed in braces {}
Statements terminated with semicolon ;
See helloloop.c:

helloloop.c

#include<stdio.h>

int main(int argc, char *argv[])
{
    int i;
    
    for (i = 0; i < 3; i++) {
        printf("Hello World %d\n", i);
    }

    return 0;
}

C Data Types

Native types

char, unsigned char, int unsigned int, float, double
bool, arrays, enum
structs
pointers

Programmer-defined types

structs and unions
typedef - an abbreviation

Different Architectures

32bit vs 64bit

Most laptops, desktops, and servers are 64bit today
Mobile devices are often 32bit
32bit int and pointer is 4 bytes
64bit int and pointer is 8 bytes

Processors - instructuion set architecture

x86 family
ARM family
Others

C Operators

Bitwise operators (used for masking/accessing bits)

and (&)
or (|)
not (~)

Relational operators

<, >, <=, >=, ==, !=

Use parentheses to force evaluation order

if (~(a&b)) == c) { x = 1; }

Control Statements

if / else / else if
for (x = 1; x < N; x++) { /* code */ }
while (x > 1) { /* code */ }
switch / case / default / break
goto

C Functions

Parameters, arguments, local variables, return value
Basic execution

Caller sets arguments (in registers or on stack)
call/jump to address of function
Function body creates activation frame for local variables
Function body sets return value (in register, e.g., eax) the returns (return or jr instruction)

C Practice

All arguments to functions are passed by value

Use pointers to "pass by reference"
Technically no "pass by reference" in C

Explicit memory allocation and deallocation with malloc() and free()

Memory is a bit more complicated in the kernel, will learn more in Project 0

Structs with pointers to build linked data structures
Pointers to functions
Macros for speed
Global variables are not always bad
Use bool for true/false
New types with typedef (typically not used in kernel code)

The C Library

The Standard C Library (libc)

Strings: strcpy(), strlen(), etc.

Pintos: strlcpy, strlcat, strnlen

I/O: open(), close(), read(), write(), printf(), etc.
Math: sin(), cos(), pos(), etc.
Others

Man pages:

man 3 <function_name>

Command Line Arguments

C and UNIX define a way to pass arguments to a program
int main(int argc, char *argv[])
argc is the number of args (including the command name itself)
argv is an array of strings

Really it is an array of pointers to strings

See args.c:

$ cat args.c

/* args.c - demonstrate command-line processing */

/* Standard C header file with prototypes and */

/* constants for basic input/output operations */

/* (e.g., printf) */

#include <stdio.h>

int main(int argc, char *argv[])

{

/* All variable declarations must go at the top of a function */

/* declaration, even variables for loops */

int i;

printf("argc = %d\n", argc);

for (i = 0; i < argc; i++) {

printf("argv[%d] = %s\n", i, argv[i]);

}

/* return exit code to shell */

return 0;

}

Basic Output with printf

printf is a sophisticated function for generating output
printf can output the values of C variables
printf can format output
See printf.c:

$ cat printf.c

/* printf.c - program to demonstrate printf output */

#include<stdio.h>

int main(int argc, char **argv)

{

char name[] = "Some string";

int i,j;

float fi;

double di;

int *ptr;

/* use %s to print a string, \n is a "newline" */

printf("Here is: %s\n", name);

/* usr %d to print integers */

/* just use multiple specifiers to print multiple variables */

i = 16;

j = 32768;

printf("i is %d and j is %d\n", i, j);

/* use %f to print a float */

fi = 22.0/7.0;

printf("fi is %f\n", fi);

/* use %lf to print a double */

/* also can specify the "format" */

di = 22.0/7.0;

printf("di is %2.20lf\n", di);

printf("fi is %2.20lf\n", fi);

/* use %X and %x to print in hexidecimal (good for pointers) */

ptr = &i;

printf("ptr is %X\n", ptr);

printf("ptr is %x\n", ptr);

/* use %c to print a single character */

printf("%c%c%c\n", 'a', 'b', 99);

/* stdout and stderr */

printf("Hello there printf\n");

fprintf(stdout, "Hello there fprintf\n");

fprintf(stderr, "Hello there stderr\n");

return 0;

}

Working with C Strings

In C, strings are an array of characters with a null termination character '\0' at the end.
The length of a string does not include the null terminator
The storage for a string must include space for the termination character

Note: other languages work differently, e.g., Pascal includes length at beginning of string.

Arrays and pointers can be used to access strings
Be sure to know where the string is stored

E.g., if you put it on the stack of a function, then return, the storage will be reused.

See strings.c:

$ cat strings.c

/* strings.c - show how to use C strings */

#include <stdio.h> /* for printf, etc. */

#include <string.h> /* for str functions */

#include <stdlib.h> /* for malloc and free */

/* static memory allocation */

char *s1 = "This is string one";

char *s2 = "and this is string two";

char t1[256];

char t2[256];

int main(int argc, char *argv[])

{

char *p1;

/* basics */

printf("string s1 = %s\n", s1);

printf("length of string s1 = %d\n", strlen(s1));

/* copying */

strcpy(t1, s1); /* note: s1 must be null terminated */

printf("string t1 = %s\n", t1);

printf("length of string t1 = %d\n", strlen(t1));

/* concatenation */

strcpy(t2, s1);

strcat(t2, " "); /* add a space */

strcat(t2, s2);

printf("string t2 = %s\n", t2);

printf("length of string t2 = %d\n", strlen(t2));

/* comparison */

printf("is s1 equal to s1? strcmp = %d\n", strcmp(s1, s1));

printf("is s1 equal to t1? strcmp = %d\n", strcmp(s1, t1));

printf("is s1 equal to t2? strcmp = %d\n", strcmp(s1, t2));

/* see the "n" versions of the str functions */

/* dynamic memory allocation */

p1 = (char *) malloc(256);

strcpy(p1, t2);

printf("string p1 = %s\n", p1);

printf("length of string p1 = %d\n", strlen(p1));

free(p1);

return 0;

}

The C Preprocessor

Before compilation, C source files are preprocessed (e.g., translated)
The C Preprocessor (cpp) handles:

Include files: #include<foo.h>
Macro expansion: #define NMAX 3
Conditional compilation

Most C programs use the preprocessor, especially OS kernels

Include Files

System include files (where are they?)

#include <stdio.h>

Program local include files

#include "foo.h"

General rule: do not define storage (variables) within an include file, only data types, function prototypes, and macros
Add an include directory to the search path:

gcc -o main main.c -I/home/benson/src
Now you can use: #include <foo.h>

Preprocessor Macros

Simple

#define MAX_COUNT 3

Parameterized

#define ADD(x,y) x + y

Complex:

#define insert(e, l) do { \

e->next = l->head; \

l->head = e; \

} while(0)

What is going on here?

Conditional Compilation

Used for portability and testing

#ifdef __LINUX___

printf("Linux\n");

#else

printf("Unknown\n");

#endif /* __LINUX__ */

Include File Management

Conditional compilation can be used to make sure only one instance of an include file is preprocessed

#ifndef _FOO_H_

#define _FOO_H_

... include file contents ...

#endif /* _FOO_H_ */

C Pointers

Declare a pointer variable with "*" in type declarations:

int *p;
char *str;
double *dp;
struct foo *foo_ptr;

Dereference a pointer with "*" in expressions:

x = *p;
*p = 1;

Use address of "&" to get the address of a variable:

p = &x;
foo_ptr = &foo;

Use arrow "->" operator to access struct members through a pointer:

foo.x = 1;
foo_ptr->x = 1;
(*foo_ptr).x = 1; /* same as above */

All pointers are the same size:

32 bits (4 bytes)
64 bits (8 bytes)

See pointers.c

$ cat pointers.c

/* pointers.c - pointer usage examples */

#include <stdio.h>

struct foo {

int x;

int y;

int z;

char name[32];

};

int x;

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

int y;

int *p1;

int *p2;

x = 1;

y = 2;

printf("x = %d, y = %d\n", x, y);

p1 = &x;

p2 = &y;

(*p1) = 101;

(*p2) = 102;

printf("x = %d, y = %d\n", x, y);

printf("p1 = %p, p2 = %p\n", p1, p2);

return 0;

}

C Struct Offsets

#define offsetof(TYPE, MEMBER) \

(unsigned) &(((TYPE *) 0)->MEMBER)

struct point {

int x;

int y;

int z;

char c;

float f;

double d;

};

0: x (4 byte int)

4: y (4 byte int)

8: z (4 byte int)

12: c (1 byte char)

13: 3 byte padding

16: f (4 byte float)

20: d (8 byte float)

How does this work?

$ cat offsetof.c

#include <stdio.h>

#define offsetof(TYPE, MEMBER) \

(unsigned) &(((TYPE *) 0)->MEMBER)

struct point {

int x;

int y;

int z;

char c;

float f;

double d;

};

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

printf("Offset of x: %d\n", offsetof(struct point, x));

printf("Offset of y: %d\n", offsetof(struct point, y));

printf("Offset of z: %d\n", offsetof(struct point, z));

printf("Offset of c: %d\n", offsetof(struct point, c));

printf("Offset of f: %d\n", offsetof(struct point, f));

struct point *p = (struct point *) 0;

p->x = 1;

}

Structures and Linked Lists

Pointers and linked structures are used extensively inside an OS kernel
Basic idea:

allocate memory
create links between allocated memory blocks

Used for lists, trees, hash tables, etc.
Can be tricky to debug, so we need to have a good understanding to avoid mistakes
See namelist example:

$ cat nametest.c

/* nametest.c - test the namelist implementation */

#include <stdio.h>

#include <stdlib.h>

#include "namelist.h"

int main(int argc, char *argv[])

{

struct namelist *list;

struct namelist_node *node;

list = namelist_new();

node = namelist_node_new("Greg Benson", "benson@usfca.edu");

namelist_add(list, node);

node = namelist_node_new("Peter Pacheco", "peter@usfca.edu");

namelist_add(list, node);

node = namelist_node_new("Dave Wolber", "wolber@usfca.edu");

namelist_add(list, node);

namelist_print(list);

return 0;

}

namelist.h

/* namelist.h - list interface */

#define MAX_STR_SIZE 256

struct namelist_node {

struct namelist_node *next; /* next pointer */

char name[MAX_STR_SIZE];

char email[MAX_STR_SIZE];

};

struct namelist {

struct namelist_node *head, *tail;

};

/* namelist node functions */

struct namelist_node *namelist_node_new(char *name, char *email);

/* namelist functions */

struct namelist *namelist_new(void);

struct namelist *namelist_add(struct namelist *list, struct namelist_node *node);

void namelist_print(struct namelist *list);

namelist.c

/* namelist.c - implementation of the namelist interface */

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "namelist.h"

/* namelist nodes */

struct namelist_node *namelist_node_new(char *name, char *email)

{

struct namelist_node *new;

new = (struct namelist_node *) malloc(sizeof(struct namelist_node));

if (new == NULL) {

printf("namelist_node_new: malloc failed\n");

exit(1);

}

new->next = NULL;

strncpy(new->name, name, MAX_STR_SIZE);

strncpy(new->email, email, MAX_STR_SIZE);

return new;

}

struct namelist *namelist_new()

{

struct namelist *new;

new = (struct namelist *) malloc(sizeof(struct namelist));

if (new == NULL) {

printf("namelist_new: malloc failed\n");

exit(1);

}

new->head = NULL;

new->tail = NULL;

return new;

}

struct namelist *namelist_add(struct namelist *list, struct namelist_node *node)

{

if (list->head == NULL) {

node->next = NULL;

list->head = node;

list->tail = node;

} else {

node->next = NULL;

list->tail->next = node;

list->tail = node;

}

return list;

}

void namelist_print(struct namelist *list)

{

struct namelist_node *node;

node = list->head;

while (node != NULL) {

printf("[name] %-20s [email] %-20s \n",

node->name, node->email);

node = node->next;

}

}

To compile:

gcc -o nametest nametest.c namelist.c