.. _ch06_c_pointers: ================================================== 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: .. literalinclude:: ./codes/pointers1.c :language: c :linenos: :download:`Download this code <./codes/pointers1.c>` This can be compiled by calling: .. code-block:: console gcc pointers1.c -o pointers1.ex Let's walk through this program rather carefully. First consider how a pointer is declared, e.g.: .. code-block:: C 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: .. code-block:: C 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: .. code-block:: C 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: .. literalinclude:: ./codes/refPassing.c :language: c :linenos: :download:`Download this code <./codes/refPassing.c>` This can be compiled by calling: .. code-block:: console 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: .. literalinclude:: ./codes/pointerArith.c :language: c :linenos: :download:`Download this code <./codes/pointerArith.c>` This can be compiled by calling: .. code-block:: console 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: .. code-block:: C 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: .. literalinclude:: ./codes/pointerAlias.c :language: c :linenos: :download:`Download this code <./codes/pointerAlias.c>` This can be compiled by calling: .. code-block:: console 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: .. code-block:: C 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: .. literalinclude:: ./codes/structPointers.c :language: c :linenos: :download:`Download this code <./codes/structPointers.c>` This can be compiled by calling: .. code-block:: console 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: .. code-block:: C 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: .. literalinclude:: ./codes/arrowOperator.c :language: c :linenos: :download:`Download this code <./codes/arrowOperator.c>` This can be compiled by calling: .. code-block:: console 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. .. _ch06_c_dynamicmemory: ^^^^^^^^^^^^^^^ 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: .. code-block:: C = malloc(); /* Use that memory for something */ /* ... */ free(); 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: .. literalinclude:: ./codes/sizeofOperator.c :language: c :linenos: :download:`Download this code <./codes/sizeofOperator.c>` This can be compiled by calling: .. code-block:: console gcc sizeofOperator.c -o sizeofOperator.ex In particular this makes dynamically allocating arrays much easier, as demonstrated in this example: .. literalinclude:: ./codes/dynamicMem.c :language: c :linenos: :download:`Download this code <./codes/dynamicMem.c>` This can be compiled by calling: .. code-block:: console 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: .. literalinclude:: ./codes/ColMajorOOC/ColMajorMat.h :language: c :linenos: :download:`Download this code <./codes/ColMajorOOC/ColMajorMat.h>` then change the source file to match: .. literalinclude:: ./codes/ColMajorOOC/ColMajorMat.c :language: c :linenos: :download:`Download this code <./codes/ColMajorOOC/ColMajorMat.c>` Finally, we'll need to modify the main file to match the new conventions: .. literalinclude:: ./codes/ColMajorOOC/Main.c :language: c :linenos: :download:`Download this code <./codes/ColMajorOOC/Main.c>` The makefile remains unchanged: .. literalinclude:: ./codes/ColMajorOOC/makefile :language: make :linenos: :download:`Download this code <./codes/ColMajorOOC/makefile>` 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: .. code-block:: C 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.