CS211: Pointers

The finger pointing at the moon is not the moon — Buddhist saying¹

The great benefit C provides over other programming languages is the fact that its runtime system is about as close to the hardware as any high-level programming language can conceivably get. To the novice programmer, this fact reveals itself to be a double-edged sword. C, unlike Java or other meticulously managed runtime languages, requires the programmer to be not just an expert in understanding programming abstractions, but to also be an expert in understanding how memory is managed during a program's execution. The average Python programmer likely has little to no idea about how the data they are manipulating is actually being handled by their machine. Conversely, the average C programmer must have some understanding as to what is happening under the hood during their computations. This reality flows forth from the most maligned and feared part of the language: pointers².

This is often the most difficult topic of the semester. Do not be discouraged if it does not make sense right away!

Recall that all variables in C represent locations in memory. Again, every variable that we declare in C code is nothing more than a named, symbolic stand-in for the physical location within the machine that holds data. When we declare a variable, say int x = 5, x is a useful symbol for the programmer because it is easier to reason about a symbol x than to reason about the relative address -4(%rbp).

All memory in C is "byte addressable". This means that the smallest memory unit that a C program can target is a byte³. Every single byte of memory then must have an address associated with it. The structure that maintains the addresses for a program's memory is called the address space. Below is a diagram which represents one in the abstract:

High Address (0xFFFFFFFFFFFFFFFF)
+------------------+
|      Stack       |  <- Local variables, function calls
|                  |     grows downward
|        |         |
|        v         |
|                  |
|                  |
|        ^         |
|        |         |
|                  |     grows upward
|       Heap       |  <- Dynamically allocated memory
+------------------+
|       BSS        |  <- Uninitialized global/static variables
+------------------+
|      Data        |  <- Initialized global/static variables
+------------------+
|      Text        |  <- Program code (read-only)
+------------------+
Low Address (0x0000000000000000)

There are a few things to note. One, the two dynamic memory regions, the stack and the heap, "grow" towards one another. This is what makes them dynamic—the size of each is not settled beforehand. Two, we can see that program code itself is contained within the address space in the text segment. Three, that the addresses are bounded between two hexadecimal numners, 0x0 and 0xFFFFFFFFFFFFFFFF, the latter of which is equivalent to 2^64-1. This is due to the fact that x86-64 machines will run 64-bit Operating Systems which provide processes with 64-bit addresses⁴.

A pointer is a variable type which stores a memory location. Despite all of the difficulties involved with dealing with pointers in code, the definition is rather simple. For example, if I declare a pointer int* p, then p can be assigned the memory location of another variable:

1: int main(){
2:   int x = 10;  // Declaring an integer x
3:                // with a value of 10
4: 
5:   int *p = &x; // Declaring an integer pointer p
6:                // with a value of the memory location of x
7: }

(All of the operators will be dealt with in more detail below.) Here, p does not store 10, but rather the memory location that the variable x represents. If x is at the relative address -4(%rbp) then p stores -4(%rbp), not the value contained at that address. Again, p is storing a reference to x. Before we get into more examples, I think it's best to describe all of the operators associated with pointers.

Listing 2 defines an integer pointer p on Line 5. It does so using the type declarator *. Adding a * prior to the variable name indicates that it is a pointer type variable. For example, char *cp is a char pointer, double *dp is a double pointer, int *ip is an int pointer, and float *fp is a float pointer.

Pointer types can have multiple levels of indirection. This means that I can further alter some of the above definitions to include something like char **cpp which defines cpp as a pointer to a char pointer. This can be done arbitrarily⁵.

One of the holdovers of C development ocurring in the 1970s is that the symbol set to represent a multitude of operators was rather small. That paired with a desire to cut down on the potential visual noise of many bespoke operators led the language designers to reuse operators in different contexts. Many of these symbols we've seen in different contexts, but here they are used for pointer-specific purposes.

One of the trickiest parts when working with pointers is understanding what it means to dereference them. Dereferencing just means that you are telling the C runtime to "look into" the reference that is stored inside of the pointer. Again, the pointer points to something. Dereferencing has the program trying to get the thing that is being pointed to. Here's a simple example which takes Listing 2 and modifies it slightly:

1: #include <stdio.h>
2: int main(){
3:     int x = 10;
4:     int *p = &x;        // Here, * is used as a declarator
5:     printf("%d\n", *p); // Here, * is used as a dereference operator
6:   }

Line 3 declares an int, x, and sets its value equal to 10. Line 4 declares a pointer to an int, p, and sets its value equal to the memory location of x. Line 5 dereferences the p by jumping to the memory location stored in the variable p and returning the value contained therein. We can compile and run the program like so:

josephraskind@stargazer:/tmp/pointers$ gcc deref.c -o deref; ./deref
10

Why is 10 returned and not the memory location of x? Again, its because the C runtime has looked inside of the memory location stored in p and retrieved the value that it was storing.

Let's expand Listing 3 somewhat:

 1: #include <stdio.h>
 2: int main(){
 3:     int x  = 10;
 4:     int *p = &x;
 5:     printf("Value of &x:  0x%p\n", &x);  // Memory location of x
 6:     printf("Value of p:   0x%p\n", p);   // Value stored in p
 7:     printf("Value of &p:  0x%p\n", &p);  // Memory location of p
 8:     printf("Value of *p:  %d\n", *p);    // Dereferencing p
 9:     printf("Value of x:   %d\n", x);     // Value stored in x
10:   }

Let's compile and run the above:

1: josephraskind@stargazer:/tmp/pointers$ gcc deref_exp.c -o deref_exp; ./deref_exp
2: Value of &x:  0x0x7ffe140349ac
3: Value of p:   0x0x7ffe140349ac
4: Value of &p:  0x0x7ffe140349b0
5: Value of *p:  10
6: Value of x:   10

Let's take the output of Listing 6 one line at a time. Line 2 shows the output of &x which is the memory address that x was assigned. Line 3 shows that the p variable was storing exactly that memory address—this should make sense as p is a pointer to x. Line 4 shows the memory address of p; p's memory address is distinct from x's because they are two different variables. Line 5 shows the result from dereferencing p; the C runtime looks inside of 0x0x7ffe140349ac and finds the value 10. Line 6 shows the value of x, which we would expect to be 10.

Let's expand this one level further by introducing a double pointer pp:

 1: #include <stdio.h>
 2: int main(){
 3:     int x   = 10;
 4:     int *p  = &x;
 5:     int **p = &p;
 6:     printf("Value of &x:   0x%p\n", &x);   // Memory location of x
 7:     printf("Value of p:    0x%p\n", p);    // Value stored in p
 8:     printf("Value of &p:   0x%p\n", &p);   // Memory location of p
 9:     printf("Value of *p:   %d\n", *p);     // Dereferencing p
10:     printf("Value of x:    %d\n", x);      // Value stored in x
11:     printf("\n");
12:     printf("Value of pp:   0x%p\n", pp);   // Value stored in pp
13:     printf("Value of &pp:  0x%p\n", &pp);  // Memory location of pp
14:     printf("Value of *pp:  0x%p\n", *pp);  // Dereferencing pp
15:     printf("Value of **pp: 0x%p\n", **pp); // Dereferencing pp, twice
16:   }

And then we compile and run it:

 1: josephraskind@stargazer:/tmp/pointers$ gcc deref_exp_pp.c -o deref_exp_pp; ./deref_exp_pp
 2: Value of &x:   0x0x7fffb54bd364
 3: Value of p:    0x0x7fffb54bd364
 4: Value of &p:   0x0x7fffb54bd368
 5: Value of *p:   10
 6: Value of x:    10
 7: 
 8: Value of pp:   0x0x7fffb54bd368
 9: Value of &pp:  0x0x7fffb54bd370
10: Value of *pp:  0x0x7fffb54bd364
11: Value of **pp: 10

The same line by line analysis should be helpful. Line 9 outputs the address stored by pp which is equivalent to the address of p on Line 4. Line 10 outputs the address of pp. Line 11 outputs the value stored at the location pointed to by 0x0x7fffb54bd368 which happens to be the memory address of x, or what is stored in p. Line 12 shows that we can stack dereferences: (1) We dereference to look inside of the memory location of p to grab the memory location of x; (2) We dereference the memory location of x to get the value of x which is 10.

This works because a pointer is nothing more than a variable that stores a memory location:

     pp                p                 x
+----------+      +----------+      +----------+
|  0x7ffd  |----->|  0x7fff  |----->|    10    |
+----------+      +----------+      +----------+
   0x7ffc            0x7ffe            0x7fff

As per the C language spec, "The void type comprises an empty set of values; it is an incomplete object type that cannot be completed." This does not preclude the creation and use of a void pointer type. In fact, C programmers often use void pointers in their day to day tasks. Many standard library functions, like malloc, return void pointers as the absence of a type is necessary to preserving the abstraction associated with the function call.

Arrays refer to a special sort of type which represent contiguosly allocated nonempty values. Arrays have a base, or element, type associated with them. For example, we can define an integer array, arr, with ten elements using the following syntax: int arr[10]. Arrays are not guaranteed to have set default values. We can use an initializer to guarantee zeros with int arr[10] = {0}. Let's have a look:

1: #include <stdio.h>
2: int main(){
3:   int arr[5];                 // Declaring an int array of 5 elements
4:   for(int i = 0; i < 5; i++)
5:     printf("%d\n", arr[i]);   // The [] are used for selecting an element
6:   int arr_z[5] = {0};         // Declaring a new array initialized to 0
7:   for(int i = 0; i < 5; i++)
8:     printf("%d\n", arr_z[i]);
9: }

And after we compile and run the above:

 1: josephraskind@stargazer:/tmp/pointers$ gcc arr_init.c -o arr; ./arr
 2: 1894002662
 3: 32766
 4: 1254343277
 5: 22066
 6: -525053208
 7: 0
 8: 0
 9: 0
10: 0
11: 0

Lines 2-6 print out the elements of the unitialized array. Lines 7-11 print out the elements of the initialized array.

Arrays are contiguous in memory. This means that there is an entire block of memory reserved for the elements of that array side-by-side. When I write int x[5], that means that on my machine 20 bytes are reserved for the array x (5 4 byte ints). We can see this in code:

1: #include <stdio.h>
2: int main(){
3:   int arr[5] = {1,2,3,4,5};
4:   for(int i = 0; i < 5; i++)
5:     printf("0x%p: %d\n", &arr[i], arr[i]); // Print the memory location of each element and its value
6:   printf("%ld\n", sizeof(arr));            // Print the size of the array
7: }

After compiling and running the above:

1: josephraskind@stargazer:/tmp/pointers$ gcc contiguous.c -o arr; ./arr
2: 0x0x7ffd1aa80530: 1
3: 0x0x7ffd1aa80534: 2
4: 0x0x7ffd1aa80538: 3
5: 0x0x7ffd1aa8053c: 4
6: 0x0x7ffd1aa80540: 5
7: 20

You'll notice that every address is 4 spots higher than the last. Again, this is because each element is an int, and in x86-64 machines an int is usually 4 bytes.

Until now, memory allocation has been the compiler's job. We've never had to worry much about reserving space on the stack to make sure there was a place to store our data because the compiler would guarantee there was always enough room. Sometimes, however, it's advantageous to be more particular about memory management. The C standard library provides functions like malloc and calloc to do exactly that.

Our last for foray into pointers leads us into some really unintuitive territory with function pointers. It turns out that not only can we have pointers that point to data and other pointers, but we can also have pointers that point to functions. How is that possible? Recall that pointers store locations in memory. If we combine that with the knowledge that functions are also stored in memory then it's only logical that pointers should also be able to point to functions. Here's an example:

 1: #include <stdio.h>
 2: 
 3: int cube(int c){
 4:   return c * c * c;
 5: }
 6: 
 7: int square(int s){
 8:   return s * s;
 9: }
10: 
11: int add_one(int a){
12:   return a + 1;
13: }
14: 
15: int apply(int x, int (*fn)(int)){ // The second argument is a function pointer which takes an int and returns an int
16:   return fn(x);                   // Calling a function using the pointer
17: }
18: 
19: int main(){
20:   int (*funcs[3])(int) = {add_one, square, cube}; // An array of function pointers
21:   int v = 10;
22:   for(int i = 0; i < 3; i++){
23:     int res = apply(v, funcs[i]);                 // Providing function pointers as arguments to the apply function
24:     printf("%d\n", res);
25:   }
26: }

Wow…what a nightmare! If we restrict our view to the main method we can see a declaration of a variable funcs which is an array of function pointers. The pointers are to functions which take an int (shown to the right of the parentheses) and return an int (shown to the left of the parentheses). I then send each function pointer into a function called apply which also takes a regular int. Line 16 shows that apply calls the function pointer's function reference with the argument provided by the call to apply. We can see the the output below:

1: josephraskind@stargazer:/tmp/pointers$ gcc func_p.c -o func_p; ./func_p
2: 11
3: 100
4: 1000

First add_one is called, then square, then cube.

Function pointers are a very powerful abstraction that allows C to operate similarly to higher-level functional programming languages like Lisp and Haskell.

1. Compile and run Listing 5 on your own machine. Do the memory addresses match those shown in the lecture? Why or why not? What stays the same between runs on the same machine?

2. Draw a pointer diagram in the style of Listing 9 for the following code before running it, then verify by compiling and printing the addresses:

   int x = 42;
   int *p = &x;
   int **pp = &p;
   

3. Write a C program that declares an int x = 5 and a pointer int *p = &x. Using only *p (no direct reference to x), change the value of x to 100 and print it. Verify that printing x directly also shows 100.
4. The lecture shows that dereferencing a null pointer causes a segmentation fault as in Listing 12. Compile and run it yourself. Then run it under valgrind and record the output. What additional information does valgrind provide compared to just running the program?
5. Write a C program that declares int x = 0xFFFFFF41 and prints it as an int, a char, and a float by casting the pointer, as in Listing 14. Before running, predict what each output will be based on what you know about how each type interprets bits.
6. The lecture states that arrays and pointers behave similarly. Write a program based on Listing 22 that declares an int array of 5 elements and a pointer to its first element. Access the third element using four different methods: arr[2], *(arr+2), p[2], and *(p+2). Verify all four produce the same result.
7. Write a C program that declares an uninitialized int array of 5 elements as in Listing 16 and prints each element alongside its memory address. What is the distance in bytes between each address? Does this match what you expect given the size of an int?
8. The lecture states that the [] operator returns an lvalue. Write a program that uses [] on the left side of an assignment to modify elements of an array, then prints the modified array to verify.
9. Rewrite the static allocation version of make_greeting from Listing 24 to use malloc instead as shown in Listing 26. Compile both versions and compare the compiler warnings. Explain in your own words why the malloc version works and the static version does not.
10. Write a program that uses malloc to allocate an int array of 10 elements, sets each element to its index multiplied by 2, prints all elements, and then frees the memory. Run it under valgrind to confirm there are no leaks.
11. Write the same program as above using calloc instead of malloc. Print the array before setting any values. What do you observe and why does it differ from malloc?
12. The lecture shows that valgrind reports 24 bytes leaked for two malloc calls in Listing 30. Explain why the total is 24 bytes given that only 4 bytes were requested for the single int and 20 bytes for the int array. Does this match what you'd expect?
13. Write a program that intentionally creates a memory leak by calling malloc without a corresponding free. Run it under valgrind and record the output. Then fix the leak and run valgrind again to confirm it reports no leaks.
14. Declare a 3x4 int matrix as in Listing 20 and initialize it with values 1 through 12. Print each element alongside its memory address using nested for loops. Verify that the addresses are contiguous and separated by 4 bytes.
15. The lecture shows that the + operator on pointers accounts for the size of the type. Write a program that declares both an int array and a char array and prints the addresses of each element. What is the difference in byte offsets between elements of each array? Does it match what the lecture predicts?
16. Write a program using function pointers based on Listing 33 that defines three functions: one that doubles its input, one that negates it, and one that returns its absolute value. Store them in a function pointer array and apply each to the value -5 using an apply function.
17. The lecture states that void pointers cannot be dereferenced directly. Write a program that allocates memory with malloc, stores the result in a void *, then casts it to an int * and stores a value through it. Print the value by dereferencing the cast pointer.
18. Write a program that declares int x = 10, int *p = &x, and int **pp = &p. Using only **pp, change the value of x to 99. Print x, *p, and **pp to verify all three reflect the change.
19. The lecture mentions that the text segment stores program code in read-only memory. Based on what you know from the memory lecture about the .rodata section, explain why attempting to modify a string constant causes a segmentation fault but modifying a char array initialized from a string constant does not. Write a program demonstrating the difference between the two.
20. Write a program that uses a function pointer to implement a simple calculator. Define four functions for addition, subtraction, multiplication, and integer division, each taking two int arguments and returning an int. Store them in a function pointer array and loop through all four, applying each to the values 10 and 3 and printing the result.