Pointers, Dynamic memory, and Segmentation faults

We’ve alluded to pointers a few times in the previous sections, and it seems about time we actually cover them. Pointers in C have a reputation for being confusing. Don’t worry though! We’ll go through plenty of examples. You’ll be past this hurdle to learning C in no time. Indeed, we’ve already been using them.

All variables, named constants, even functions, in your program have to be stored in memory somewhere. Memory is separated (roughly) into 1 byte blocks, and each block has an address. Pointers are variables that store these addresses.

Reference and dereference operators

The fundamental operators for producing and interacting with pointers are the reference & and dereference * (unary) operators. For any given variable, the reference operator & produces a pointer to that variable. That is to say, it finds the address of where that variable resides in memory. The dereference operator does precisely the opposite. Dereferencing a pointer gives back whatever is actually stored at that location.

Consider this code snippet:

/* File: pointers1.c
 * Author: Ian May
 * Purpose: Demonstrate reference and dereference operators
 */

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

int main()
{
  /* Declare a few variables */
  int n = 5;
  double q = 1.3;
  
  /* Declare a few pointers */
  int *pn; /* Uninitialized pointer */
  double *pq = &q; /* Pointer initialized to address of variable q */
  
  /* Use these pointers */
  pn = &n; /* Assignment into a pointer */
  printf("n = %d, and is stored at address %p\n",n,pn);
  printf("q = %f, and is stored at address %p\n",q,pq);

  /* Equivalently we could print q using */
  printf("q = %f, and is stored at address %p\n",*pq,pq);

  /* Assign value to variable by dereferencing a pointer */
  double r = *pq; /* Equivalent to 'double r = q;' */
  printf("r = %f\n",r);

  /* Modify a variable through a pointer to it */
  *pq = -5.2;
  printf("Now q = %f, and is stored at address %p\n",q,pq);
  
  /* There can be multiple pointers to one location */
  double *po;
  po = pq; /* Assigning pointer to pointer copies address, not value */
  *po = 68.8; /* Modify q through the other pointer */
  printf("Now q = %f, and is stored at address %p\n",q,pq);
  
  return 0;
}

Download this code

This can be compiled by calling:

gcc pointers1.c -o pointers1.ex

Let’s walk through this program rather carefully. First consider how a pointer is declared, e.g.:

int *pn;

Note that the dereference operator is present within the declaration. There are two ways to think about what is happening here, and it is beneficial to turn this declaration into an English sentence. As written you could say “pn is a variable that dereferences into an int”. The declaration can equivalently be written as:

int* pn;

which you might interpret as meaning “pn has type int*, which denotes a pointer to an int”. This is arguably the correct interpretation in C++, but the former is more common in C as it more accurately reflects how the type system works. You can say either one to yourself, and the key message is that turning statements with pointers into full sentences can help you reason about what is happening.

Let’s make the same observations about the next line:

double *pq = &q;

Again, the left hand side says pq is something that dereferences into a double. Furthermore, we are initializing pq to hold the address of the variable q by using the reference operator.

Later, we print the value q and the address where it is stored. Note that addresses are most conveniently written in hexadecimal, which can be done through the %p format specifier. What can you observe about the relationship between the address of n and of q?

The previous question raises another: if all pointers are just addresses in memory, and thus just integers of some width, why do pointers have types associated with them? Addresses vary at the byte level, but the data stored there very likely occupies multiple bytes. The pointer corresponds to the first address in memory where something resides, but to get the actual data item we need to know how many additional bytes should also be considered.

The integer n resides in memory starting at the address printed by the program, but occupies an additional 3 bytes after this too (4 bytes total).

There are a few other observations we should make here:

• Line 28 creates another double variable, and sets it equal to q through the pointer pq

• Similarly, line 32 modifies the value of q through the pointer pq

• There can be multiple pointers to one address, for instance line 37 also modifies q through a pointer, but now using po instead of pq

  • Note that either way, the variable q has changed value

Remark: Does this last point remind you of anything from Python?

Remark: On line 16 the pointer pn is declared but not initialized. We’ve seen before that using uninitialized values can lead to unintended effects. What happens if we try to dereference this uninitialized pointer? For instance, try assigning n = *pn before pn is set. This might give you a segmentation fault, it might fill n with random garbage. The behavior is undefined, and typically not reproducible.

One way to avoid bugs, or at least hard to understand bugs, is to give your pointers some initial address, like on line 17. You may not have a specific address ready where you declare the pointer, and in this case you can use NULL. This is a special address, typically 0x0, that will always give a segmentation fault when dereferenced. It seems odd that you would want this, but de-bugging reproducible errors is much easier than dealing with random or silent errors.

Exercise: Try assigning n from *pn before pn is set. Observe the claimed behavior above, and try running the program through Valgrind or GDB.

Passing by reference

So, we can see the memory addresses where variables live, and we can interact with those variables through these pointers, but what can we actually do with pointers that we couldn’t do before?

For one thing, we can pass variables to functions by reference instead of by value. Consider this small example:

/* File: refsAndVals.c
 * Author: Ian May
 * Purpose: Demonstrate passing arguments by reference and by value
 */

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

void modify1(int n)
{
  printf("Inside modify1, n = %d\n",n);
  n += 10; /* Make n larger by 10 */
  printf("Inside modify1, n = %d\n",n);
}

void modify2(int *pn)
{
  printf("Inside modify2, n = %d\n",*pn);
  *pn = 10; /* Set to a value of 10 */
  printf("Inside modify2, n = %d\n",*pn);
}

int main()
{
  /* Declare a variable in the main scope */
  int n = 5;
  printf("In main, n = %d\n",n);

  /* Call modify1 and print value again */
  modify1(n);
  printf("In main, n = %d\n",n);
  
  /* Call modify2 and print value again */
  modify2(&n);
  printf("In main, n = %d\n",n);
  return 0;
}

Download this code

This can be compiled by calling:

gcc refPassing.c -o refPassing.ex

Some questions to ponder:

• Why precisely does the first method not propagate the value out to the variable n in the main program? The variable in modify1 is called n isn’t it?

• If C passes by value, what is being passed when calling the second method? Is a copy still happening?

Exercise: Make the print statements in the modify functions also report out the address of what they are modifying, and observe the results. Does that help to demonstrate the above questions?

Pointer arithmetic and arrays

Another huge use of pointers is to support the array types we’ve already looked at. Before we examine arrays in detail, let’s look at another operation you can do on pointers: arithmetic.

Just like you can add numbers together, or increment loop counters, you can add, subtract, increment, and decrement pointers. What does this actually mean though?

• Incrementing a pointer sets it to look further ahead in memory, that is, it shifts the address that it looks at forward.

  • In particular, it shifts it forward by an amount matching the width of the data type it points to

• Adding a number larger than 1 corresponds to shifting the address by that many steps of the data width.

• Decrementing a pointer does the opposite, and again respects the width of the data type it points to

In fact, the square brackets we’ve already been using to access elements of an array are actually a fancy operator that combines pointer addition and dereferencing. This deserves an example:

/* File: pointerArith.c
 * Author: Ian May
 * Purpose: Demonstrate basic pointer arithmetic and arrays
 */

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


int main()
{
  /* Declare an array to work with */
  double u[] = {1.2,3.7,-13.2,66.5,15.0,1.2e2};

  /* See that u is actually a pointer to the first array element */
  printf("u = %p, and &u[0] = %p\n",u,&u[0]);

  /* Set a pointer to the second element, and increment */
  double *pu = &u[1];
  pu++;
  printf("pu = %p, and points to the value *pu = %f\n",pu,*pu);

  /* Decrement pu by 2, where does it point now? */
  pu -= 2;
  printf("pu = %p, and points to the value *pu = %f\n",pu,*pu);

  /* Print all values in u, can you do this only using pu? */
  printf("u contains:");
  for (int i=0; i<6; i++) {
    printf(" %1.2f |", u[i]);
  }
  printf("\n");

  return 0;
}

Download this code

This can be compiled by calling:

gcc pointerArith.c -o pointerArith.ex

Exercise: Print values from the last loop without using any square brackets. How exactly are the square brackets equivalent to a pointer sum and dereference? Does this explain why C uses zero-based indexing?

Solution: The following code snippet shows what square brackets really are underneath:

int n = 3; /* Some index, value doesn't matter too much */
double q;
double u[] = {1.2, 3.7, -13.2, 66.5, 15., 1.2e2};
double *pu = &u[0];
/* The following four lines are completely equivalent */
q = u[n];
q = *(pu+n);
q = *(u+n);
q = pu[n];

Remark: You should absolutely still use square brackets when indexing into an array. These demonstrations are just to build some confidence with how pointers work and some of the things we can do with them.

Let’s look at another example. We could set a pointer to look at a location inside an array, and then treat that pointer as if it were an array itself. This might be useful if you have a problem where negative indices are meaningful. Consider this sample program:

/* File: pointerAlias.c
 * Author: Ian May
 * Purpose: Use a pointer to generate an array where negative indices are allowed
 */

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


int main()
{
  /* Declare an array to work with */
  double u[] = {1.2, 3.7, -13.2, 66.5, 15., 1.2e2};
  
  /* Create a pointer that aliases to the third element of u */
  double *v = &u[2];
  
  /* v has the same values, but at different indices */
  printf("v contains:\n");
  for(int i=-2; i<4; i++) {
    printf("v[%d] =  %1.2f\n", i, v[i]);
  }

  return 0;
}

Download this code

This can be compiled by calling:

gcc pointerAlias.c -o pointerAlias.ex

Initially, writing a negative index into an array seems like it is just asking for trouble. However, consider what the square brackets are really doing from the perspective above.

Exercise: Re-write line 16 without using any square brackets. Consider re-writing the print statement without using them either. Does this make the negative indexing more clear?

Pointers to structs

So far we’ve seen how to create a pointer to a variable, and how arrays are really just pointers to the start of a block of memory holding a contiguous sequence of values of the same type.

If you recall from before, we can also define our own derived types, and create instances of these types. Here we’ll look at what happens when we create pointers to these instances, and what capability we can gain by doing so.

Consider again the small example struct given at the start of that section:

struct S {
  int n;
  char *s;
  double q;
};

You may recall that when we create an instance of this struct we can access its member variables by using a period. What happens if we only have a pointer to the instance? We do precisely what we did above to access the value of a primitive variable behind a pointer, we dereference it. Consider this small example:

/* File: structPointers.c
 * Author: Ian May
 * Purpose: Demonstrate pointers to structs
 */

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

struct S {
  int n;
  char *s;
  double q;
};

int main()
{
  /* Declare an instance of the struct */
  struct S a = {2,"Hello",2.3e-4};

  /* Do something with the struct */
  printf("From the struct instance:\n");
  for (int i=0; i<a.n; i++) {
    printf("%s %e\n",a.s,a.q);
  }

  /* Create a pointer to this struct */
  struct S *pa = &a;

  /* and do the same thing, using only pa */
  printf("From the pointer:\n");
  for (int i=0; i<(*pa).n; i++) {
    printf("%s %e\n",(*pa).s,(*pa).q);
  }

  return 0;
}

Download this code

This can be compiled by calling:

gcc structPointers.c -o structPointers.ex

Now hold on, why do we have all of these parenthesis around? This is due to operator precedence. Just like in math, there is an established order of operations that the language obeys. Now though, there are a bunch of additional operators to account for. Again, let’s try to say in full sentences what each of these lines mean:

struct S a = {2,"Hello",2.3e-4};
struct S *pa = &a;

/* Valid */
int m = (*pa).n;

/* Invalid */
int m = *pa.n;

The valid form says “dereference pa and get field n from that”, while the second says “dereference field n from struct pa”. The second one fails because pa is not a struct. To make matters more confusing, the second could be valid if you have a struct which internally has a data field that is a pointer.

Fortunately, there is a way out of this mess. Taking pointers to structs is so common that there is a special operator for dereferencing them, just like we had the square brackets above for array access. This is the arrow operator ->, and we can use it like this:

/* File: arrowOperator.c
 * Author: Ian May
 * Purpose: Demonstrate pointers to structs, now with the arrow operator
 */

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

struct S {
  int n;
  char *s;
  double q;
};

int main()
{
  /* Declare an instance of the struct */
  struct S a = {2,"Hello",2.3e-4};

  /* Create a pointer to this struct */
  struct S *pa = &a;

  /* Do something to a, using only pa */
  for (int i=0; i<pa->n; i++) {
    printf("%s %e\n",pa->s,pa->q);
  }

  return 0;
}

Download this code

This can be compiled by calling:

gcc arrowOperator.c -o arrowOperator.ex

How would you turn the arrow operator into part of an English sentence? Perhaps you could say pa->n as “go to where pa points, and get the member n”. This is a lot to take in. Perhaps an exercise will help.

Exercise: Modify the above program such that the for loop sits in its own function. Try writing this function to take the struct by value, and by reference. Which makes more sense? Is it problem dependent?

Exercise: Re-write the column major matrix code so that the structs are all passed by reference.

Dynamic memory

So far everything we’ve done has used a fixed amount of memory, and never too much of it at one time. We aren’t going to talk too much about the stack versus the heap, but it will suffice to say that at some large size we can’t rely on variable length arrays any longer. We looked briefly at how Fortran handles this problem through the allocate and deallocate intrinsics, as well as the property allocatable. Similarly, in C we will need some way to allocate and deallocate memory at run time if we want to handle large problems, especially if we don’t want to re-compile for every new size.

This dynamically allocated memory is obtained by the malloc and free functions (malloc being an abbreviation of “memory allocation”). The general format of these calls are:

<a pointer> = malloc(<number of bytes>);

/* Use that memory for something */
/* ... */

free(<a pointer>);

This seems a little daunting. Does this mean we need to account for how many bytes wide every data type is before we even use them? What if we want to allocate an array of structs without counting the width of every field? How do we know for sure the size of an integer on one system or another? Fortunately, like most times something seems too tedious to be true, there is a better way to do this. The sizeof operator, as its name might suggest tells you the size of whatever you apply it to. This operator can act on variables, types, even functions, and can be used like this:

/* File: sizeofOperator.c
 * Author: Ian May
 * Purpose: Demonstrate what the sizeof operator does
 */

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

struct S {
  int n;
  char *s;
  double q;
};

int main()
{
  int n = 12;
  double q = 2.6e2;

  /* Applied to a variable */
  printf("int n is %lu bytes wide\n",sizeof n);

  /* Parentheses are optional, but can help readability */
  printf("double q is %lu bytes wide\n",sizeof(q));

  /* Applied to a type, parentheses not optional here */
  printf("the int type is %lu bytes wide\n",sizeof(int));

  /* Applied to an expression */
  double *pq = &q;
  printf("double q is %lu bytes wide\n",sizeof(*pq));
  return 0;
}

Download this code

This can be compiled by calling:

gcc sizeofOperator.c -o sizeofOperator.ex

In particular this makes dynamically allocating arrays much easier, as demonstrated in this example:

/* File: dynamicMem.c
 * Author: Ian May
 * Purpose: Demonstrate basic usage of malloc/free
 */

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

struct S {
  int n;
  const char *s;
  double q;
};

int main(int argc, char **argv)
{
  /* Let's set an array size from the command line */
  int N = argc>1 ? atoi(argv[1]) : 5;
  
  /* Allocate an array of doubles */
  double *u = malloc(N*sizeof(*u));

  /* Fill with something */
  for (int i=0; i<N; i++) {
    u[i] = 1./(1.+i*i);
  }

  /* Allocate an array of structs */
  struct S *data = malloc(N*sizeof(*data));

  /* Fill with something */
  for (int i=0; i<N; i++) {
    data[i].n = i+1;
    data[i].s = "Some string";
    data[i].q = u[i]*u[i];
  }

  /* Print out one of these structs like we did before */
  int idx = N-1;
  for (int i=0; i<data[idx].n; i++) {
    printf("%s %e\n",data[idx].s,data[idx].q);
  }

  /* Don't forget to clean up after yourself!!! */
  free(u);
  free(data);
  
  return 0;
}

Download this code

This can be compiled by calling:

gcc dynamicMem.c -o dynamicMem.ex

There is a lot going on in this example. We should stop and gather our thoughts by making a few observations.

• The assignment for int N looks pretty strange, what’s that all about?

  • This is a ternary operator, similar to what we saw briefly in Python

• After allocating u and data we can interact with them just like any other array

  • Note that for the array of structs we can combine the square brackets and the dot operator naturally

  • Just like any other array (without a brace-closed initializer), declaring one will not initialize the entries to anything in particular. There is a similar function calloc that allocates, and zeros out a block of memory to address this.

• The malloc function requests space in memory to the resolution of bytes. On its own malloc has no idea what these bytes are for, hence we need to sizeof to allocate the appropriate number.

• Accordingly, we need to match every call to malloc with a call to free

  • A word of advice: Every time you write malloc, skip ahead and write the corresponding free statement. This won’t catch every bug, but prevents a few common ones.

Remark: You may notice that above we made a big deal about pointers having types. Why is it that malloc can assign to pointers of whatever type? This requires a discussion about a very special type, void*. We won’t get into much detail here, but it suffices to say that this acts as a go-between for pointer types.

A full example

Let’s return to our column-major matrix struct, and address some of the issues that code had. Above, we re-wrote part of it to start passing the structs by reference to functions that need them. The next thing to fix is the way we obtain memory for the internal data array.

Here we are going to use a design pattern inspired by the object oriented approach. C is not an object oriented language, but you can see that packaging this data together into a struct and interacting with it as one cohesive thing has an OOP feel to it. This involves quite a bit of pointer manipulation, and provides a wealth of examples to study.

First, we’ll re-write the header to look like this:

/* File: ColMajorMat.h
 * Author: Ian May
 * Purpose: Another iteration on the previous example, now modeling the OOC
 *          approach
 */

#ifndef COLMAJORMAT_H
#define COLMAJORMAT_H

/* We will only use a pointer to the struct, so make that the typedef */
typedef struct _p_ColMajorMat *ColMajorMat;

/* Define a structure that holds the matrix dimensions and a flattened array */
struct _p_ColMajorMat{
  int m, n;
  double *data;
};

/* Functions to create and destroy the matrix struct */
ColMajorMat CreateMatrix(int,int);
void DestroyMatrix(ColMajorMat);

/* Functions to interact with this matrix */
void FillMatrix(ColMajorMat);
void MatVecMult(ColMajorMat,double[*],double[*]);

#endif

Download this code

then change the source file to match:

/* File: ColMajorMat.c
 * Author: Ian May
 * Purpose: Another iteration on the previous example, now modeling the OOC
 *          approach
 */

#include <stdlib.h>

#include "ColMajorMat.h"

/* Matrix creation handles allocation */
ColMajorMat CreateMatrix(int m, int n)
{
  /* Allocate and fill struct */
  ColMajorMat mat = malloc(sizeof(*mat));
  mat->m = m;
  mat->n = n;
  mat->data = malloc(m*n*sizeof(*mat->data));
  /* Pass this struct back out */
  return mat;
}

/* Destruction frees everything creation allocated */
/* Can you see a possible bug here? */
void DestroyMatrix(ColMajorMat A)
{
  /* Free the data array inside the struct */
  free(A->data);
  /* Free the struct */
  free(A);
}

void FillMatrix(ColMajorMat A)
{
  for (int i=0; i<A->m; i++) {
    for (int j=0; j<A->n; j++) {
      A->data[j*A->m + i] = ((double) i*j+1);
    }
  }
}

void MatVecMult(ColMajorMat A, double x[A->m], double b[A->m])
{
  for (int i=0; i<A->m; i++) {
    b[i] = 0;
    for (int j=0; j<A->n; j++) {
      b[i] += A->data[j*A->m + i]*x[j];
    }
  }
}

Download this code

Finally, we’ll need to modify the main file to match the new conventions:

/* File: Main.c
 * Author: Ian May
 * Purpose: Another iteration on the previous example, now modeling the OOC
 *          approach
 */

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

#include "ColMajorMat.h"

int main(int argc, char **argv)
{
  /* Matrix sizes, easily set from command line */
  int m = argc>1 ? atoi(argv[1]) : 4;
  int n = argc>2 ? atoi(argv[2]) : 3;

  /* Arrays to hold vectors we are using */
  double b[m];
  double x[n];
  for (int j=0; j<n; j++) {
    x[j] = 1.0/(1.0 + j*j);
  }

  /* Create and fill a matrix */
  ColMajorMat A =  CreateMatrix(m,n);
  FillMatrix(A);

  /* Store A*x into b, interpreted as matrix-vector product */
  MatVecMult(A,x,b);

  /* Print out result */
  printf("b =");
  for (int i=0; i<m; i++) {
    printf(" %1.2f |",b[i]);
  }
  printf("\n");

  /* Don't forget to clean up! */
  DestroyMatrix(A);
  
  return 0;
}

Download this code

The makefile remains unchanged:

CC = gcc
CFLAGS = -g -Wall -Wextra -pedantic -Wno-vla-parameter

OBJ = Main.o ColMajorMat.o

ColMajor.ex: $(OBJ)
	$(CC) $(CFLAGS) -o $@ $(OBJ)

%.o: %.c
	$(CC) $(CFLAGS) -c $<

.PHONY: clean

clean:
	rm -f ColMajor.ex *.o *~

Download this code

As before, download these to a new directory and compile them by calling make. The program is run by calling ./ColMajor.ex. There is a lot going on here, so let’s make some observations for each file.

The header ColMajorMat.h has changed slightly:

• Consider the typedef and struct declarations:

  typedef struct _p_ColMajorMat *ColMajorMat;
  struct _p_ColMajorMat{
    /* ... */
  };
  

  • The typedef declares ColMajorMat as a pointer to struct _p_ColMajorMat. This means that any time we use ColMajorMat we are really using a pointer to the actual struct.

  • The structure containing the actual data has the suggestive name struct _p_ColMajorMat, where the prefix indicates that this should be kept private, and not referred to directly by user code. Note: this privacy is purely stylistic, and not enforced by the language.

• The typedef now makes it easier to use pointers to the struct directly, and discourages ever passing the struct around by value. This means that ColMajorMat is now a pointer type.

• The FillMatrix and MatVecMult functions now just take ColMajorMat arguments. These are always by reference since ColMajorMat is a pointer type.

The matching source file ColMajorMat.c has also changed slightly:

• The FillMatrix and MatVecMult functions now use the arrow operator on A since it is a pointer type.

• The CreateMatrix function is responsible for doing all of the required memory allocation.

  • Since ColMajorMat is now a pointer type, we need to actually create an instance of the base struct for this thing to point to. The first malloc does this. Then we can fill this struct accordingly and hand it back.

• The DestroyMatrix function is responsible for deallocating all memory that the creation function took. Using this pattern means that the struct can hold many pieces of dynamically allocated memory, but the end user need only call one function to clean up.

  • Question: What happens if the user calls the destroy function multiple times? Can we plan around this possibility?

The main file now shows why we went through all of this effort:

• Lines 15-23 just set up the vectors to multiply against and store into

• Line 26 allocates all memory and fills in the fields of the struct

  • Now, when you declare a matrix you don’t need to think about all the struct fields. Consider creating multiple matrices through this approach compared to the previous one

• Lines 27 and 30 now use references by default, and copying is avoided without any special action.

• Line 40 handles all deallocation in one call

Hopefully you can see the merits of this pattern. However, as always, there is room for improvement. To see a mature and polished code base using this pattern please take a look at PETSc.

Exercise: Try calling the DestroyMatrix function twice. What happens? Try re-writing the function to be robust against this possibility.