All of Programming [ PART I ]

We will note that it is common to end an array of strings with a NULL pointer, such as this: 1 const char * words2[] = {\"A\", \"cat\", \"likes\", \"sleeping.\", NULL}; This convention is common, as it allows for one to write loops that iterate over the array without knowing a priori how many elements are in the array. Instead, the loop can have a condition that checks for NULL, such as this: 1 const char ** ptr = words2; 2 while (*ptr != NULL) { 3 printf(\"%s \", *ptr); 4 ptr++; 5} 6 printf(\"\\n\"); It would be a beneficial exercise to execute this code by hand to make sure you understand all of the concepts involved. You can then put it into a source file (with appropriate #includes, and inside of main) to make sure you derived the correct answer. 10.3 Function Pointers The actual instructions your program executes are (of course) numbers, and they are stored in the computer’s memory, just like the program’s data is. Consequently, each instruction has an address, just like each piece of data does. As these instructions have addresses, we can have pointers to them. It is not generally useful to have a pointer to an arbitrary instruction, but it can be quite useful to have a pointer to the first instruction in a function—which we typically just think of as a pointer to the function itself and call a function pointer. Technically speaking, the name of any function is a pointer to that function (that is, “printf” is a pointer to the printf function); however, we do not typically think of them in this way. Instead, when we refer to a function pointer, we typically mean a variable or parameter that points at a function. However, the fact that a function’s name is a pointer to it is useful to initialize such variables and/or parameters. 1 void incAll(int * data, int n) { 1 void squareAll(int * data, int n) { 2 for (int i = 0; i < n; i++) { 2 for (int i = 0; i < n; i++) { 3 data[i] = data[i] + 1; 3 data[i] = data[i] * data[i]; 4} 4} 5} 5} (a) A function that increments all elements of an array. (b) A function that squares all elements of an array. Figure 10.11: Motivation for function pointers: four very similar pieces of code. The most useful application of function pointers arises from the ability to make a function pointer a parameter to a function we are writing (or that is provided by a library). To motivate this functionality, consider the four very similar pieces of code in Figure 10.11. Each of these functions does something to every element of an array (of ints)—the only difference between them is what they do to each element. Instead of duplicating the code—rewriting the entire function each time—it would be nicer if we could write one function that takes a parameter specifying “what to do to each item.” Then, we could simply call that function with an appropriate function for each task. While avoiding this duplication of code may not seem so important here (the function is only a few lines long), this concern can become much more significant as you write more complex functions that operate over more complex data structures.

We can achieve this behavior by passing in a function pointer for the parameter that specifies “what to do to each item.” 1 void doToAll(int * data, int n, int (*f)(int)) { 2 for (int i = 0; i < n; i++) { 3 data[i] = f(data[i]); 4} 5} Most of the code in this example should seem quite familiar, except the somewhat odd looking parameter declaration: int (*f) (int), which declares a parameter (called f) whose type is “a pointer to a function that takes an int as a parameter and returns an int.” Function pointer declarations are a bit unusual in that the name of the parameter (or variable—the declarations have the same syntax) is in the middle of the declaration. However, this syntax makes sense, as it looks a lot like the normal declaration of a function—the return type comes first, followed by the name, followed by the parameters in parentheses. Here, however, we only need to specify the parameter types; we do not name them. Note that the parentheses around *f are important—without them, the * becomes part of the return type (that is, the * is read as part of int*), and the declaration appears to be describing a function that returns an int*. There are times when both the parentheses and the * can be omitted (writing int f(int) ); however, it is generally best to be consistent (and avoid trying to remember when this is permissible; we mention it in case you see it). As with other types, we can use typedef with function pointers. The syntax is again more similar to function declarations than to other forms of typedef. We might re-write our previous example to use typedef, so that it is easier to read: 1 typedef int (*int_function_t) (int); 2 3 void doToAll(int * data, int n, int_function_t f) { 4 for (int i = 0; i < n; i++) { 5 data[i] = f(data[i]); 6} 7} Once we have this doToAll function defined, we can use it by passing in a pointer to any function of the appropriate type (i.e., one that takes an int and returns an int). Since the name of a function is a pointer to it, we can just write the name of the function we want to use as the value to pass in for that argument: 1 int inc(int x) { 2 return x + 1; 3} 4 int square(int x) { 5 return x * x; 6} 7 8 // ... 9 doToAll(array1, n1, inc); 10 // ... 11 doToAll(array2, n2, square); 12 // ... We will note that you may see such things written with the address-of operator, such as doToAll(array1, n1, &inc). This syntax is legal, but the & is superfluous, just as it is with the name of an array—the name of the function is already a pointer. Note that if we have a function pointer other than the name of a function (i.e., a variable or a parameter), then we could take the address of that variable, giving us a pointer to a pointer to a function. It is best to use only the address-of operator in this latter case, which comes up rather infrequently. Another example of using function pointers as parameters is a generic sorting function— one that can sort any type of data. We will discuss sorting in more detail in Chapter 26. For

now, it suffices to know that sorting an array is the process of arranging the elements of that array into increasing (or decreasing) order. Sorting an array is a common task in programs, as sorted data can be accessed more efficiently than unsorted data. We will formalize this notion of efficiency later, but for now, imagine trying to find a book in a library where the books are arranged alphabetically (i.e., sorted) versus in one where they are stored in no particular order. As we will see when we learn more about sorting, there are many different sorting algorithms, but none of them care about the specific type of data, just whether one piece of data is “less than,” “equal to,” or “greater than” another piece of data. Correspondingly, we could make a generic sorting function—one that can sort an array of any type of data—by having it take a parameter that is a pointer to a function that compares two elements of the array. In fact, the C library provides such a function (which sorts in ascending order— smallest to largest): 1 void qsort(void *base, 2 size_t nmemb, 3 size_t size, 4 int (*compar)(const void *, const void *)); The first parameter to this function, void * base, is the array to sort. Recall that void * is “a pointer to an unspecified type of data”—allowing qsort to take an array of any type. The second parameter, size_t nmemb specifies the number of elements (or members) in the array (recall that size_t is an unsigned integer type appropriate to use for the size of things). The third parameter, size_t size specifies the size of each element of the array—that is, how many bytes each elements takes in memory. This information is required because otherwise qsort has no way to tell where one element of the array ends and the next begins. The final parameter is the one we are most interested in for this discussion—compar is a pointer to a function that takes two const void *s and returns a int. Here, the const void *s point at the two elements to be compared (they are const since the comparison function should not modify the array). The function returns a positive number if the first pointer points at something greater than what the second pointer points at, 0 if they point at equal things, and a negative number for less than. This description of qsort may seem like a lot to take in, but is more easily understood by seeing a couple examples. These two examples will both be wrapper functions around qsort —small functions that do little or no real computation, but provide a simpler interface. The first example is a wrapper to sort arrays of ints: 1 int compareInts(const void * n1vp, const void * n2vp) { 2 const int * n1ptr = n1vp; //convert back to int* so we can dereference 3 const int * n2ptr = n2vp; 4 return *n1ptr - *n2ptr; //subtracting the two numbers compares them 5} 6 7 void sortIntArray(int * array, size_t nelements) { 8 qsort(array, nelements, sizeof(int), compareInts); 9} First, we write a comparison function, compareInts, whose behavior is compatible with the interface of qsort—it takes pointers, which are declared to be const void *s, and returns an int. Since this function is intended to be used only when sorting arrays of ints, it converts const void *s to const int *s, and dereferences them to get the actual ints in the array. Subtracting these two ints gives a result that conforms to the expectations of the qsort function (it will be positive if the first is greater, 0 if they are equal, or negative if the first is less). Once this function is written, we can write the sortIntArray function, which wraps the qsort function. Observe how sortIntArray does no real computation (it just calls qsort to do all the work), but provides a much simpler interface (you pass it an array of ints and the

number of elements in the array; you should be able to use this function to sort an array without any explanation). The sortIntArray function passes its arguments as the first two arguments to qsort, and then passes sizeof(int) as the third argument, since each element of the array will be sizeof(int) bytes large (probably four, but the correct way to write it is with the sizeof operator, in case you ever compile it somewhere where it is not four). For the fourth argument, the function passes a pointer to compareInts—recall that the name of the function is a pointer to that function. The qsort function will then call compareInts to determine the relative ordering of the elements in the array. We can make use of qsort in similar ways for other types. For example, we could write some similar functions to sort an array of strings (an array of const char *s): 1 int compareStrings(const void * s1vp, const void * s2vp) { 2 //first const: s1vp actually points at (const char *) 3 //second const: cannot change *s1vp (is a const void *) 4 const char * const * s1ptr = s1vp; 5 const char * const * s2ptr = s2vp; 6 return strcmp(*s1ptr, *s2ptr); 7} 8 9 void sortStringArray(const char ** array, size_t nelements) { 10 qsort(array, nelements, sizeof(const char *), compareStrings); 11 } We again start by writing a function to compare strings that conforms to the interface required by qsort. This function, compareStrings, looks much the same as compareInts. The main difference is that we use strcmp to perform the string comparison. We saw strcmp earlier (in Section 10.1.3) to test if two strings are equal; however, it returns a positive/zero/negative value based on the ordering of the strings, as qsort expects. Note that the pointers passed in are pointers to the elements in the array (that is, they point at the boxes in the array), even though those elements are themselves pointers (since they are strings). When we convert them from void *s, we must take care to convert them to the correct type—here, const char * const *—and use them appropriately, or our function will be broken in some way. For example, consider the following broken code: 1 //BROKEN DO NOT DO THIS! 2 int compareStrings(const void * s1vp, const void * s2vp) { 3 const char * s1 = s1vp; 4 const char * s2 = s2vp; 5 return strcmp(s1, s2); 6} This code will actually compile without any errors or warnings, but will not work correctly. This is a danger anytime you use void *—the flexibility gives you “enough rope to hang yourself” because you have no guarantees that you will use the pointer in the correct way. As we will see later, C++ has features in its type system that allow us to have generic functions in a much safer way. We can use function pointers pretty much anywhere we can use any other type—not only as the types of parameters, but also as the types of variables, the type of elements in an array, or fields in structs. In fact, as we will see later, function pointers in structures lie at the heart of object-oriented programming, although object-oriented languages hide this implementation detail from the casual programmer. 10.4 Security Hazards Improper use of strings and related functions frequently lead to security vulnerabilities in software—an opportunity for a malicious user to abuse the software and compromise the functionality of the system in some way. Depending on the type of vulnerability, the attacker

may be able to cause the system to leak information, manipulate data within the program, or even execute arbitrary code. An error that allows any of these behaviors is considered very serious. One common form of security vulnerability is a buffer overflow, in which the code provides a possibility to write a string into a array that is too small for it (typically when a string is read from the user)—overflowing the array and writing over other data. If the array resides in the frame, the data overwritten may include the return address (which we draw as a numbered circle, but is actually stored as a pointer in the frame when the computer executes the code). Overwriting the return address changes where the function returns, allowing the attacker to trick the program into executing different code at that time. To take advantage of the ability to change where the function returns, the attacker carefully crafts her input string so that it contains the machine instructions she wishes to execute. Remember, “Everything Is a Number”: letters and machine instructions are just bytes of data—as is the new return address where an attacker expects her code will end up. She then enters this input, and the program does whatever her instructions tell it to do. The ability to execute even a few instructions is sufficient to execute the command shell and run arbitrary commands. Video 10.4: An example of how a buffer overflow exploit works. The (ridiculously unsafe) gets function is used to read a string. A malicious user can craft an input string that causes the attacker’s own code to be executed by the program. Video 10.4 shows vulnerable code being exploited. In this example, a programmer has carelessly used the unsafe gets function to read a string from the user into an array. However, the gets function stops only when it reads a newline character (’\\n’), regardless of how much space is in the array it is supposed to read into—it will overwrite any other data after the array until a newline character is encountered. In this video, the attacker carefully crafts an input much longer than the intended array, which contains the instruction bytes to execute the command shell (/bin/bash). Although this may not seem terribly bad if the user is running the program herself at the shell (after all, when the program exits, she will return to the command shell anyways), if the program has higher privileges or is running on a remote system and reading input across the network, the seriousness of the security vulnerability becomes readily apparent. Another string error that can lead to security vulnerabilities is format string attacks. Recall that printf takes a format string (a string with % signs to indicate format conversions, such as %d to convert a decimal integer), and then an appropriate number of other arguments for the values to convert. A format string vulnerability arises whenever there is a possibility that the user may affect the format string in such a way that they can introduce extra format conversions. As a simple example, imagine that there were a readAString function, which reads a string from the user (we will learn how to read input from the user in Chapter 11). Consider the following vulnerable code, which attempts to read a string then print it back: 1 //BAD CODE: DO NOT DO! 2 char * input = readAString(); 3 printf(input); If an attacker inputs a string with % signs in it, it can cause the program to behave in ways it should not. Notice that the call to printf in the above code uses the input read from the user as the format string. Even though there are no arguments for format specifiers to convert, printf is not deterred. If the user input contains %-conversion, printf will take the data where these arguments should be, format them as directed, and print them. At a

minimum, the attacker can cause the program to reveal data by placing %d or %s format specifiers in his input. What information this attack reveals depends on what information resides in the place that printf looks for those extra arguments. To make this vulnerability even worse, printf has a format specifier (%n) that writes the number of characters printed so far to a memory location specified by an int * passed as the appropriate argument. A clever attacker can use this format conversion to modify the memory of the program in malicious ways, changing its behavior, and possibly executing arbitrary code. The correct way to use printf2 with a string input (or potentially affected) by the user is to use the %s conversion: 1 //CORRECT CODE 2 char * input = readAString(); 3 printf(\"%s\", input); Note that GCC will give you a warning if your format string is not a literal and you have no format arguments (i.e., the format string is the only argument to printf); however, it will not warn you if there are other arguments. This behavior may seem odd but exists for a good reason. If you have nothing to convert, you should use \"%s\" for the string. However, there may be times when you have an argument and want to compute the format string. For example, the following code is fine: 1 const char * fmt = \"%d\\n\"; 2 if (printInHex) { 3 fmt = \"%x\\n\"; 4} 5 printf(fmt, someNumber); Here, we are sure the format string is either %d\\n (print a number as decimal) or %x\\n (print a number as hex), either of which is fine to print someNumber (which we assume is an int). However, we must be cautious whenever we write code that computes a format string to ensure that the user may not affect it in malicious ways. Format string vulnerabilities fall into a larger category of security flaws where a program uses unsanitized inputs. More generally, if a program uses strings in a way that certain characters are special, it must take care to remove or escape those characters in input read from the user. In the case of format strings for printf, these special characters are % signs. If we wanted to let the user control the format string, we could do so safely if (and only if), we took care to sanitize the string first—iterating over it and modifying % signs to remove their special meaning (i.e., by removing them or converting them to %%—the format specifier that prints a literal percent sign). However, in the case of printf there is no reason to take this approach—it is simpler (and thus less error prone) to simply use the %s specifier to print the string literally. If we need format specifiers in a user-dependent way, our code should build the format string itself. There are, however, other situations where we may wish to read a string from the user and include it in some context where characters have special meanings. Two of the most common cases are commands that are passed to the command shell, and information passed to databases. The command shell considers many characters to be special, but one particularly dangerous one is ‘—text enclosed in back-ticks is executed as its own command (see Chapter B). Suppose our program reads some input from the user and passes it as an argument to a shell command—that is, it executes someCommand stringFromUser. If a malicious user enters ‘rm -rf *‘, then the command shell will perform back-tick expansion, and run the command rm -rf *, which will erase all files in the current directory. While this

command is destructive, a more insidious user could find far better commands to execute— ones that give them access to the system to gain and/or modify information. A similar problem can occur with improper use of databases, where the program passes SQL commands to the database as a string. We will not go into the details of SQL, but imagine we can illustrate the point without a full understanding of them. Suppose the program wants to run the command SELECT * from Users WHERE name=’strFromUser’, where strFromUser is a string read from the user (e.g., you have asked them for their user name, and they have entered it). If we are not careful, the user may type a ’ (terminating the literal name is matched against), and a ; to end the current command, followed by an arbitrary command of his choosing. Such a vulnerability allows the attacker to modify information in the database however he wants. The web-comic xkcd has a nice cartoon on this topic: http://xkcd.com/327/. Note that sanitizing inputs is a task that must be performed with care. A sanitization function that catches half of the cases is barely better than not sanitizing at all—a clever attacker will try all the possible special characters and eventually find the one allowing her to compromise your system. Whenever you need to sanitize your inputs, the best thing to do first is to check if there is already a function available to you, written by experts. For example, some database interfaces have prepared statements, which allow you to write the SQL query with ?s in the place of various inputs, bind values to those inputs, and then the database library ensures that there are no input sanitization issues. 10.5 Practice Exercises Selected questions have links to answers in the back of the book. • Question 10.1 : Use the man pages to find a function that: 1. Takes a string and returns its length. 2. Takes a string and a character and returns a pointer to the first occurrence of the character inside the string (or NULL if not found). 3. Takes two strings and returns a pointer to the first occurrence of the second string inside the first string (or NULL if not found). • Question 10.2 : Write the function int myatoi(const char * str), which behaves like the atoi function, except that you write it yourself (without using atoi or strtol). • Question 10.3 : Write the function int myatoiHex(const char * str), which behaves like the atoi function, except (a) it interprets the string as a hexadecimal (base 16) number rather than decimal and (b) you write it yourself without using atoi or strtol). • Question 10.4 : Write the function long mystrtol(const char * str, char ** endptr, int base), which behaves like strtol, except that you write it yourself (without using atoi or strtol) • Question 10.5 : In chess, an FEN string describes the position of the board. The string has six parts, each separated by a space, which we will describe shortly. Your job for this exercise is to write the function void printFENBoard(const char * fen), which takes an FEN string as input and prints the resulting board (along with the other information encoded in the string). We will only concern ourselves with the position information and “draw” the board it describes. The first part of the FEN string describes the layout of the pieces on the board, which you should “draw” textually. This portion of the string describes each row (from “top” to “bottom” in our perspective), separated by a slash. The contents of the row description are either letters (one of pnbrqkPNBRQK, denoting a piece: pawn, knight, bishop, rook, queen, or king) or numbers (denoting that many empty squares). You should draw the board by printing the letter for each piece and a space for each blank square. You should print a newline at the end of each row, so that the board has a square configuration.

You may assume the FEN string you are given is valid. • Question 10.6 : Consider the description of FEN strings from the previous problem. Define a structure pieces, which has a count for pawns, rooks, bishops, queens, knights, and kings. Then write the function void countPieces(const char * fen, pieces * white, pieces * black), which takes an FEN string as its first argument and two pointers to pieces structs as its second and third arguments respectively. The function should then fill in these structs with the count of how many pieces are on the board for each side. Note that capital letters (PNBRQK) indicate a white piece, while lower case letters (pnbrqk) indicate a black piece. All of the pieces are denoted by the first letter of their name, except knights which are denoted by N/n (to avoid confusion with the king). You may assume the FEN string you are given is valid. • Question 10.7 : Write the function void fenToBoard(const char * fen, char board[8] [8]), which takes an FEN string and an two-dimensional array of characters as input and fills in the board with the letters representing the pieces of the FEN string. This problem is similar to the previous problem where you were asked to print the board, but instead of printing the board, you are writing the letters into the array. You may assume the FEN string is valid. Note that you should not assume anything about the initial contents of the board array—you should fill each square with the correct character (which might be a space). • Question 10.8 : Write the function void addMatricies(double ** ans, double ** a, double ** b, int w, int h), which takes three two-dimensional arrays—one to write the answer to (ans) and two input matrices (a and b), as well as the width (w) and height (h) of all three matrices. Your function should compute the matrix sum of a + b and store the result in ans. You should assume that the matrix is laid out so that it is first indexed by the row, then by the column. • Question 10.9 : In some popular games, the board consists of pieces in a variety of colors (e.g., red, blue, green, etc.), and the player attempts to make matches by swapping them such that three (or more) of the same color are in a row or column. Imagine you are writing such a game and have an enum for the colors: 1 enum color_t { 2 RED, 3 BLUE, 4 GREEN, 5 YELLOW, 6 ORANGE, 7 PURPLE 8 }; You have a representation of your board as a array of enum color_ts. Write the function int containsMatch(const int board[10][10]), which takes in a board and determines if there is any match (three in a row—vertically, or horizontally of the same color) on it. If there is a match, this function returns 1; otherwise, it returns 0. As always, test your code extensively. • Question 10.10 : (Requires Calculus)Recall that the derivative of a function is Given a particular function, you can often take the derivative symbolically, writing down the algebraic expression for the resulting function (as you likely learned how to do in calculus class). However, you can also numerically approximate the derivative of

a function by evaluating for a very small value of —the smaller the value of , the better the approximation. For this problem, you should write a function derivative, which takes two parameters and returns a double. The first parameter is a pointer to the function to approximate the derivative of—which should take a double and return a double. The second parameter should be the value at which it should approximate the derivative. The function should return the numerical approximation it comes up with and should use 0.000000000001 as the value for . • Question 10.11 : (Requires Calculus)In the previous problem, you saw how a function pointer can be useful for writing a function that can numerically approximate the derivative of any other function (of the right type). Another important technique in calculus is integration—finding the area under a curve. As you may recall from calculus, the definite integral is defined as: We can numerically approximate this integral for a function by iterating over the range from to , computing the area of a rectangle of width and height and adding up all of these areas (we could also use trapezoids). The smaller our value of is, the better our approximation is. Write the function double integrate(double a, double b, double (*f)(double)), which numerically approximates with . • Question 10.12 : (Requires Calculus)The gradient of a mathematical function that takes multiple inputs is the generalization of the derivative into multiple dimensions. We will consider the two-dimensional case here (although the concept generalizes to any number of dimensions). For a function ( ) that takes two inputs and , the gradient ( ) is a function whose output is a two-dimensional vector. That is, is a vector pointing in the direction in which has the greatest rate of increase at the point , with a magnitude that is the slope of the graph in that direction. The gradient of the function can be computed by taking the partial derivative of the function with respect to each component. That is, the -component of the vector is and the -component is . In much the same way that we can numerically approximate the derivative of an arbitrary function at a particular point, we can numerically approximate the gradient of an arbitrary function at a particular point. Our result will, however, be a struct with two components to represent a vector. Fill in the gradient function shown below (consult the internet or a math textbook if you need more domain knowledge): 1 struct vect2d_tag { 2 double dx; 3 double dy; 4 }; 5 typedef struct vect2d_tag vect2d; 6 7 vect2d gradient(double (*f)(double, double), double x, double y) { 8 //WRITE THIS FUNCTION 9}

• Question 10.13 : The gradient (which we discussed and you implemented in the previous question) can be useful to numerically find the local maximum or minimum of a function. We can accomplish this by using gradient ascent (to find the maximum) or gradient descent (to find the minimum). Gradient ascent works by starting at a particular point and iteratively improving it by moving along the vector of the gradient at the current point. That is, if we are currently at , we select the next point by where is some factor that we scale the gradient by. In the simplest form of gradient ascent, is constant, although using adaptive values of can improve the rate at which the algorithm converges. Note that gradient descent works in much the same way but goes against the gradient by replacing the with a in the above equation. The process ends when it converges, that is, when is sufficiently close to that our answer is good enough (they will be closer as the function “levels out” as we near the local maximum, where the gradient will be ). For this problem, you will write the gradientAscent function shown below: 1 struct point2d_tag { 2 double x; 3 double y; 4 }; 5 typedef struct point2d_tag point2d; 6 7 point2d gradientAscent(double (*f)(double, double), 8 point2d startPoint, 9 double gamma, 10 double convergedDistance ) { 11 //WRITE THIS FUNCTION 12 } Here, f is the two-dimensional function you want to maximize, startPoint has the coordinates from which you should start your ascent, gamma ( ) is the constant to scale the gradient by when updating your current point, and convergedDistance is the distance between and , where we consider the algorithm to have converged (that is, when the distance between them is less than convergedDistance, we consider to be “close enough” to the maximum to be the right answer). Note: you will want to use your gradient function from the previous problem. 9 Arrays11 Interacting with the User and System Generated on Thu Jun 27 15:08:37 2019 by L T XML

I Introduction to Programming in C10 Uses of Pointers12 Dynamic Allocation

Chapter 11 Interacting with the User and System So far, our programs have had a rather limited interaction with the user or rest of the system. They have printed some results to standard output (typically to the terminal, but sometimes you have redirected it to a file) and have not taken any input from the user, taken arguments on the command line, accessed files, nor many other things we typically think of real programs as doing. Now that we have learned about topics such as strings and arrays, we are ready to learn how to do these things. 11.1 The Operating System M ost interes ting interac tions with “the Figure 11.1: Conceptual diagram of interaction with OS and hardware. world” —reading input from the user, writing a file on disk, sending data over a network, etc.—require access to hardware devices (the keyboard, the disk drive, the network card) in ways that normal programs cannot perform themselves. One key aspect of this issue is that “normal” programs cannot be trusted to access hardware directly. If your program could read the disk directly, then it could ignore the permissions system in place to protect different users’ files and read or write any data it wanted. Furthermore, an error in a program that can access the disk directly could corrupt the entire file system, destroying all data on the system. Instead, the program asks the operating system (OS)—low- level software responsible for managing all of the resources on the

system for all programs—to access hardware on its behalf. The program makes this request via a system call—a special type of function call that transfers control from the program into the operating system. The OS checks that the program’s request is within the bounds of its permissions before performing it, which is how the system enforces security rules, such as file permissions. If the request is not permissible, the OS can return an error to the program. If, on the other hand, the request is fine, then the OS performs the underlying hardware operations to make it happen and then returns the result to the program. Figure 11.1 depicts the conceptual relationship between the program, C library, operating system, and hardware. While your C code can make system calls directly, it is more common to use functions in the C library. The C library functions then make system calls as they need. The OS then interacts with the hardware appropriately. For example, suppose you call printf to write a string to standard output. The printf function is part of the C library and involves significant code that does not require system calls: it must scan the format string for % signs and perform the appropriate format conversions, building up the actual string to print. At some point, however, printf must actually write the resulting string to standard output, which requires a system call. To perform this task, printf uses the write system call. Novice programmers are often imprecise about the difference between a system call (which transfers control into the OS, requesting it to perform a task) and a library call (which calls a function found in a library, such as the C standard library). For example, calling printf a “system call” is technically incorrect, though most people will understand what you mean. Being precise with this distinction is useful for two reasons. First, the more precise you are with your terminology, the more knowledgeable you come across during interviews (if you are interviewing for a programming- related job). Second, if you need to look a function up in the man pages, knowing whether it is a system call or part of the C library tells you which section to look in—system calls are found in section 2, while C library functions are found in section 3. 11.1.1 Errors from System Calls

System calls can fail in a variety of ways. For example, you may try to read a file that does not exist or you do not have permissions for. You might also try to connect to a remote computer across the network at an address that is invalid or unreachable (the network or remote computer is down). Whenever these system calls fail in C, they (or technically their wrapper in the C library) set a global variable1 called errno (which stands for “error number”). We have not worked with global variables—and their use is typically discouraged—but they are simply variables whose scope is the entire program. They are declared outside of any function and have a “box” that is not part of any frame. You can read (or write) them just like any other variable. In the particular case of errno, it is set by a failing call and read if your program wants more information about why the call failed. If you want to check if a specific error occured, you can compare it against the various constants, which are defined in errno.h. You may also wish to print out a message describing the error for the user. Just printing the numeric value of errno is not usually useful (do you know what error 2 means?). Fortunately, the C library has a function perror, which prints a descriptive error message based on the current value of errno. The perror function takes one argument: a string it prints before its descriptive message. Note that since errno is global (there is one errno for the entire program), you must take care not to call anything that might change it before you test it or call perror. For example, 1 //BROKEN CODE //may change errno 2 int x = someSystemCall(); 3 if (x != 0) { 4 printf(\"someSystemCall() failed!\\n\"); 5 perror(\"The error was: \"); 6} Here, printf might change errno (it makes system calls), so we may not have a correct description of the error from perror. The possibility of unexpected changes from other parts of the code is one of the hazards of global variables and part of the reason to avoid them in general. 11.1.2 Further Learning

There is much more to learn about how the OS works, its interactions with the program and hardware, and various related topics. However, those are beyond the scope of this book. We strongly recommend that the serious programmer take at least one hardware class and one operating systems class. 11.2 Command Line Arguments One form of input that our programs can take is command line arguments. As you have seen from many programs that you have used by now, when you run a command from the command prompt, you can specify arguments on the command line by writing them after the name of the program. For example, when you run gcc -o hello hello.c, you are passing three arguments to GCC (-o, hello, and hello.c).2 These arguments tell GCC—which is basically the implementation of a big algorithm to compile a C program—what specific instance of the problem we want it to solve (in this case, what C source code file to read, and where to put the resulting program). We can write our programs so that they can examine their command line arguments. To do so, we must write main with a slightly different signature: 1 int main (int argc, char ** argv) { 2 //...whatever code you want goes here... 3} Here we see that main now takes two arguments. The first, int argc is the count of how many command line arguments were passed in (it stands for argument count). The second is an array of strings that contains the arguments that were passed in (it stands for argument vector). The zeroth element of argv (that is, argv[0]) contains the name of the program,3 as it was invoked on the command line (so if you wrote ./a.out, then argv[0] is the sequence of characters ./a.out\\0). We can see this behavior in a toy example: 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int main(int argc, char ** argv) { 5 printf(\"Hello, my name is %s\\n\", argv[0]);

6 return EXIT_SUCCESS; 7} This program prints out the name it was invoked with and then exits. Figure 11.2: Frame of main, for a program run with ./myProgram input.txt - n 42. argv[0] is not typically useful, but we must remember it is there if we access the other arguments so that we look for them at the correct indices. Whatever other arguments were passed to our program appear in argv[1] through argv[argc - 1].4 The arguments appear in the array in the order that they were written on the command line (so the first one is in argv[1], the second in argv[2], and so on). The exact division of the text of the command line into discrete arguments is up to the command shell but is typically done by separating the text at whitespace (note that the program could be invoked by something other than the shell, in which case, the invoking program can pass it whatever arguments it wants). The arguments are passed in as text, so if the program intends to interpret one of its arguments numerically, it must convert that text into a number (as discussed in Section 10.1.5). Figure 11.2 depicts the frame at the start of main for a program that is run with the command line ./myProgram input.txt -n 42. We access the elements of argv as we would any other array of strings. We will note that for programs that expect a particular number of arguments, they should check argc first to make sure that the user actually supplied the right number of arguments before accessing the elements of argv—failure to do so can result in the program segfaulting when the user does not provide enough arguments. The simplest access patterns to the command line arguments are iterating over the elements of argv (for programs that do the

same thing to all arguments), extracting particular information from specific indices (for example, a program may always expect an input file name as argv[1] and an output file name as argv[2]), or a mix of the two (reading specific information from the first elements, then iterating over the rest). 11.2.1 Complex Option Processing Some programs, however, perform more complex option processing —taking a variety of flags and options, some of which require arguments (and in some cases, optional arguments). Going back to our GCC example, When we write gcc -o myProgram myProgram.c, the -o option itself takes an argument—the next command line argument after it specifies what the output is exactly because -o came right before it. However, GCC does not require -o to come in this position, we could write other arguments first. For more complex option processing (such as would be required by a program like GCC), the getopt function is quite popular. getopt is part of the C library and parses the command line arguments, accounting for such considerations as options that have (potentially optional) arguments, as well as short and long name versions (for example, some programs may accept a short name, like -o and a long name like --output with the same meaning). We will not go into the details of getopt here, but should you need it, you can, of course, read about it in its man page (be sure to specify man -S3 getopt, as there is a program by the same name in section 1). 11.2.2 The Environment Pointer While much less commonly used than the command line arguments, main can potentially take a third argument: char ** envp, a pointer to an array of strings containing the values of environment variables. If your program needs to inspect its environment variables (see Section B.11 if you are not familiar with environment variables), you can include this third parameter and access this array. If you do so, the elements of the array are strings of the form variable=value (e.g., PATH=/bin:/usr/bin). You can also access the environment variables with the functions getenv, setenv, putenv, and unsetenv. See their man pages for details.

11.2.3 Process Creation While we do not want to delve into too many details of process creation, we do want to briefly mention a few points to assure you that there is no magic involved in making new programs or getting the command line arguments to main. When the command shell (or any other program—the command shell is just a normal program) wants to run another program, it makes a couple of system calls. First, it makes a call to create a new process (fork). This new process (which is an identical copy of the original, distinguishable only by the return value of the fork system call) then makes another system call (execve) to replace its running program with the requested program. The execve system call takes an argument specifying the file with the binary (or script) to run, a second argument specifying the values to pass the new program as argv (which must end with a NULL), and a third argument specifying the values to pass for envp (even if main ignores envp, these are still passed to the new program so they can be accessed by the various environment manipulation functions mentioned in the previous subsection. When the OS executes the execve system call, it destroys the currently running program (the system call only returns on an error) and loads the specified executable binary into memory. It writes the values of argv and envp into memory in a pre-agreed upon format (part of the ABI—application binary interface: the contract between the OS and programs about how things work). The kernel then sets the execution arrow to a starting location specified in the executable binary (On Linux with GCC, the entry point is a symbol called _start —but the details are platform-specific). This startup code (which resides in an object file that is linked with any C program you compile—unless you request explicitly for it not to be) then calls various functions that initialize the C library. This startup code also counts the elements of argv to compute the value of argc and eventually calls main. Regardless of how main is declared, it always passes in argc, argv, and envp—if main is declared with fewer arguments, it still receives them but simply ignores them.5 When main returns, it—like all other functions—returns to the function that called it. In the case of main, the caller is this startup

code. This code then performs any cleanup required by the C library and calls exit (which quits the program), passing in the return value of main as the argument of exit—which specifies the exit status of the program. The shell (or other program that ran the program in question) can make a system call that waits for its “child” process(es) to exit and collects their return values. 11.3 Files Another form of interaction with the outside world that we may wish to have our program perform is accessing files. We will assume that you are familiar with what the basics of what a file is and the relevant concepts surrounding it (such as a path name, access permissions, etc.)—if you do not, you should familiarize yourself with this information in Appendix B—and focus on how we can write programs that access files. 11.3.1 Opening Files The first thing we must do to access a file (whether for reading or writing) is open it. Opening a file results in a stream associated with that file. A stream (which is represented by a FILE * in C) is a sequence of data (in this case chars) that can be read and/or written. The stream has a current position, which typically advances whenever a read or write operation is performed on the stream (and may or may not be arbitrarily movable by the program, depending on what the stream is associated with). Typically, you will open a file with the fopen function, which has the following prototype: 1 FILE * fopen(const char * filename, const char * mode); This function takes two arguments, the first of which is the name of the file to open. This filename is a string (which must be null- terminated and is not modified by fopen), which is the pathname of the file to open. The pathname can either be an absolute path (starting with a /), or a path relative to the current working directory of the program. The second argument is the mode of the file— whether the file should be opened for reading and/or writing,

whether to create the file if it does not exist, whether or not existing content is cleared out, and from what position accesses to the file start. Typically, the a string literal (such as \"r\") is passed for the mode parameter (though any expression that evaluates to a valid string is, of course, legal). We will discuss the mode in more detail momentarily. Figure 11.3: Conceptual representation of the result of opening a file. Before going into more details about the mode, it is useful to see the effects of opening a file depicted. Figure 11.3 shows what happens when fopen is used to open a file and the resulting FILE * is assigned to a variable called f. The depiction of the FILE is conceptual here, as the actual struct is much more complex and does not directly contain the data from the file. However, we do not need to know what the actual FILE struct contains, only how to operate on it. In fact, even if we do know what is in a FILE struct on one particular system, we should not attempt to use such information to directly access the fields inside of it, as the implementation details are system-dependent, and thus our code would be non-portable. Our conceptual representation of the FILE struct does, however, show the relevant pieces for typical use—we can use this abstraction to think about what a program will do, and thus how to execute it by hand. There is some information about the state of the file (which file is opened, whether it can be read or written, and whether or not the program has attempted to read past the end of the file) shown in the top portion. The bottom portion shows the data in the file, along with the position of the stream (indicated by a blue cursor). Read and write operations will occur at the current position (i.e., this blue cursor) and will advance it. We will note that real FILE structs do not contain the name of the file, but rather a file descriptor—a numeric identifier returned to the program by the operating system when the program makes the system call to open the file (namely, the open system call). The C

library functions that operate on the stream pass this descriptor to the relevant system calls, which perform the underlying input/output operations for them. It is possible for fopen to fail—for example, the file you requested may not exist, or you may not have the permissions required to access it. Whenever fopen fails, it returns NULL (and sets errno appropriately). You should always check the return value of fopen to see if it is NULL or a valid stream before you attempt to use the stream. Mode Read and/or write Does not exist? Truncate? Position r read only fails no beginning r+ read/write fails no beginning beginning w write only created yes beginning end w+ read/write created yes end a writing created no a+ read/write created no Table 11.1: Summary of modes for fopen. The possible modes for fopen are summarized in 11.1 but can be found in more detail in the man page for fopen. The first column shows the possible legal values for the mode string.6 The second column shows whether the opened file can be read, written, or both. The third column shows what happens if the requested file does not exist—for some modes, it is created (if possible), and for others, the call to fopen fails. The fourth column shows whether the contents of the file are truncated to zero-length if the file already exists—that is, whether or not the existing contents of the file are discarded. The final column shows where the accesses start—at the beginning or end of the contents of the file. We note that for the a modes (which stands for append), all writes will write their data to the end of the file, even if the program explicitly moves the current position elsewhere. 11.3.2 Reading Files Once we have our file open, we might want to read input from it. We typically will use one of three functions to do so: fgetc, fgets, or

fread. Of these, fgetc is useful when you want to read one character (e.g., letter) at a time. This function has the following prototype: 1 int fgetc(FILE * stream); While you might expect this function to return a char, it returns an int so that it can return all possible chars, plus a distinct value to indicate that there are no more characters available in the stream— that the end of the file (EOF) has been reached. The value for end-of- file is #defined as the constant EOF in stdio.h. Note that reading the character advances the current position in the stream. The fact that functions that read from streams advance the position of the stream poses a minor annoyance when writing a loop. Consider the following (broken) code, which attempts to print every character from an input file: 1 //broken 2 FILE * f = fopen(inputfilename, \"r\"); 3 if (f == NULL) { /* error handling code omitted */ } 4 while (fgetc(f) != EOF) { 5 char c = fgetc(f); 6 printf(\"%c\", c); 7} 8 //...other code... This code will read one character, check if it is the end of the file, then read a different character, and print it. This code will actually print every other character from the input file, plus possibly something spurious at the end (if there are an odd number of characters in the file). The cleanest way to restructure the loop is to exploit the fact that an assignment is also an expression that evaluates to the value that is assigned. While that may sound like a technically-complex mouthful, what it means is that x = 3 is not only an assignment of 3 to x, but also an expression that evaluates to 3. We could therefore write y = x = 3 to assign 3 to both x and y—however, we typically do not do so, as it makes the code less clear than writing two assignment statements. In this particular case, however, it is OK to exploit this property of assignments, and it is in fact a common idiom. The following code correctly prints every character from the input file: 1 //fixed

2 FILE * f = fopen(inputfilename, \"r\"); 3 if (f == NULL) { /* error handling code omitted */ } 4 int c; 5 while ( (c = fgetc(f)) != EOF ) { 6 printf(\"%c\", c); 7} 8 //...other code... Observe how we assign the result of fgetc to the variable c in the while loop’s conditional expression. We then wrap that assignment statement in parentheses to ensure the correct order of operations,7 and compare the value that was assigned (whatever fgetc returned) to EOF. You may have noticed that the type of c is int, not char. If we declared c as a char, our program would have a rather subtle bug. Can you spot it? Remember that we said fgetc returns an int so that it can return any possible character value read from the file, plus some distinct value for EOF. Assigning this return value to a char then inherently discards information—we are taking possible values and assigning them to something that can hold different bit patterns (recall from Chapter 3 that in the case of char, ). On most systems EOF is -1, so in this particular case, we would not be able to distinguish between reading character number 255 and the end of the file8 —if our input had character number 255 in it, our program would prematurely exit the loop and ignore the rest of the input! You should aim to think of these sorts of corner cases when you write test cases. Video 11.1: Reading a file with fgetc. Video 11.1 shows an example of some code that uses fgetc. In particular, this code reads a file (whose name is specified on the command line) and counts the number of letters (as determined by isalpha, from ctype.h) in that file. The fgets function is useful when you want to read one line (with a maximum length9) at a time. This function has the following prototype: 1 char * fgets(char * str, int size, FILE * stream); This function takes three arguments. The first is a pointer to an array in which to store the characters read from the file. That is, fgets will write the data into str[0], str[1], str[2], and so on. The

second argument specifies how much space is available for it to write data into. That is, size specifies the size of the array str. The final argument specifies from what stream to read the data. This function returns str if it succeeds (reads data without error), in which case, the data in str is null-terminated. It returns NULL if it fails—either if it encounters the end of the file before reading any data or encounters some other error. If you need to distinguish between an error and end-of-file, you should use the feof and/or ferror functions, which specify whether something attempted to read past end-of-file, or whether some other error occured, respectively (see their man pages for details). Video 11.2 shows the use of fgets to read a file and perform some simple calculations with the data it reads—in this case, converting the textual representation of numbers into integers (using atoi) and summing them. Observe how the code must take care that it may not actually read an entire line (if the line is too long for the array passed to fgets). If we were to actually write this program, we would want a longer line size than five—we just use five to illustrate what happens when fgets cannot read the whole line. Video 11.2: Reading from a file with fgets. Now is a good time to re-mention that you should NEVER use the gets function. This function behaves somewhat similarly to fgets, but does not take an argument specifying the size of the array it reads into. This oversight means that it will continue to read data until it reaches a newline, even if it writes past the bounds of the array (it has no way to tell how big it is). The gets function therefore poses a significant security vulnerability, as it is susceptible to buffer overflows (which we discussed in Section 10.4). We may also want to read non-textual data from a file. For example, we might have an image, video, sound, or other file, where we write data in a binary format. In such a file, rather than writing the textual representation of an integer, the actual bytes for the integer are written to the file. The specific size of integer used for each piece of data is part of the file format specification. When we want to read data in this fashion, the most appropriate function is fread, which has the following prototype:

1 size_t fread(void * ptr, size_t size, size_t nitems, FILE The first argument is a pointer to the data to write—it is a void *, since it could be any type of data. The next argument specifies the size of each item. That is, if we are writing an int or an array of ints, we would pass in sizeof(int). However, if we are reading and writing files, we probably want to work with the int types defined in stdint.h, which have their sizes fixed across systems (such as int32_t or uint64_t). The third argument specifies how many such items should be read from the stream, and the final argument specifies from which stream to read. The fread function returns how many items were successfully read. As with fgets, you should employ feof and/or ferror to obtain more information if fread returns fewer items than you requested. We will note that there is also a function fscanf, which reads formatted input and performs conversions in the reverse fashion of what printf does. If you need this functionality, it is often easier to deal with errors if you use fgets (or, as we will see later, getline) and then use sscanf on the resulting string. ¡¡¡¡¡¡¡ HEAD fgets (and later getline) will read a line at a time, and then you can attempt to convert the results out, which may or may not have the desired format. In such a case, you can easily continue reading the next line. By contrast, fscanf will stop reading input as soon as it encounters something that does not match the requested format. If you want to continue reading from the next line, you must then explicitly read out the rest of the line before proceeding. If you want to know more about fscanf or sscanf, see their man pages. 11.3.3 Writing files The other operation we may wish to perform is to write to a file. As with reading from a file, there are a variety of options to write to a file. One option—useful if we are printing formatted text—is the fprintf function. This function behaves the same as the familiar printf function, except that it takes an additional argument (before its other arguments), which is a FILE * specifying where to write the output. You can also use fputc to write a single character at a time, or fputs to write a string without any format conversions.10 That is, if

you do fputs(\"%d\") it will just print %d to the file rather than attempting to convert an integer and print the result. Finally, if you want to print non-textual data, your best choice is fwrite, which has the prototype: ======= fgets (and later getline) will read a line at a time, and then you can attempt to convert the results out, which may or may not have the desired format. In such a case, you can easily continue reading the next line. By contrast, fscanf will stop reading input as soon as it encounters something that does not match the requested format. If you want to continue reading from the next line, you must then explicitly read out the rest of the line before proceeding. If you want to know more about fscanf or sscanf, see their man pages. 11.3.4 Writing Files The other operation we may wish to perform is to write to a file. As with reading from a file, there are a variety of options to write to a file. One option—useful if we are printing formatted text—is the fprintf function. This function behaves the same as the familiar printf function, except that it takes an additional argument (before its other arguments): a FILE * specifying where to write the output. You can also use fputc to write a single character at a time or fputs to write a string without any format conversions. That is, if you do fputs(\"%d\"), it will just print %d to the file directly, rather than attempting to convert an integer and print the result. Finally, if you want to print non-textual data, your best choice is fwrite, which has the prototype: ¿¿¿¿¿¿¿ master 1 size_t fwrite(const void * ptr, 2 size_t size, 3 size_t nitems, 4 FILE * stream); The arguments are much the same as those given to fread, except that the data is read from the buffer pointed to by ptr and written to the stream (whereas fread reads from the stream and writes into the buffer pointed to by ptr). All of these methods write at the current position in the file, and advance it accordingly. Furthermore, any of these methods of writing to a file may fail, some of which are detected immediately,

and others of which are detected later. See the relevant man pages for the functions you are using to see how they might fail and what values they return to indicate failures. The reason that the failures may be detected later is that the C library functions may buffer the data and not immediately request that the OS write it. Even once the application makes the requisite system calls to write the data, the OS may buffer it internally for a while before actually writing it out to the underlying hardware device. The motivation for not writing immediately is performance: making a system call is a bit of a slow process, and writing to a hard disk is quite slow. Furthermore, writing to a disk becomes less efficient as you write smaller quantities of data to it—there are fixed overheads to find the location on the disk, which can be amortized over large writes—so the OS tries to buffer up writes until there is significant data that can be written at once (we will see this in a bit more detail later in Video 11.4, when we learn more about closing in the next section). Video 11.3: Writing to a file. Video 11.3 shows an example of using fprintf to write data to a file. In particular, this piece of code takes three command line arguments: a start and end number, and an output file name. It then prints the squares of each number in the range from start to end (inclusive) to the specified file. 11.3.5 Closing Files After you are finished with a file, you should close it with the fclose function, which has the following prototype: 1 int fclose(FILE * stream); This function takes one argument, specifying which stream to close. Closing the stream sends any buffered write data to the OS and then asks the OS to close the associated file descriptor. After calling fclose on a stream, you may no longer access it (a call to fgetc, fprintf, etc. is erroneous, though exactly what will happen is undefined). Observe that fclose returns an int. This return value indicates the success (0 is returned) or failure (EOF is returned, and errno is

set accordingly) of the fclose operation. The fclose operation can fail for a variety of reasons, the most serious of which arise in circumstances where the data cannot actually be written to the underlying hardware device (e.g., disk drive)—for example, the disk is full, or the file resides on a remote file system and network connectivity has been lost. Failure of fclose for a file you have been writing to is a serious situation—it means that the data your program has tried to write may be lost. You should therefore always check the return value of fclose to see if it failed. However, what you do in response to the failure of fclose is a bit of a difficult question. You cannot try again, as performing any operation on the stream you attempted to close—including another call to fclose—is erroneous (and results in undefined behavior). What you do, however, is highly situation-dependent. In an interactive program, you may wish to inform the user of the problem, and she may be able to take corrective action before proceeding. For example, suppose you are writing an editor (like Emacs). If the user attempts to save their work but the disk is full, she would much rather be told that the save failed (and why). The user could then proceed to free up disk space and save again (which would involve fopening the file again, fwriteing all the data, then fcloseing that stream—not retrying to fclose the original stream). By contrast, if the editor ignored the return value of fclose and failed silently—not informing the user of the problem, she may quit, losing all of her work. In other situations, you may not be directly interacting with the user (or a user capable of remedying the situation: imagine if you are writing some web service—the user you are interacting with typically has no ability to administer the system). You still will want to detect the problem and take some sort of corrective action. For exercises in this book, we will not concern ourselves with complex corrective actions when fclose fails—printing an error message suffices. However, you should get in the habit of checking its return value. This way, when you are working on real programs, you will check the return value by habit, and at least think about what you should do if it fails. Video 11.4: Closing a file and writing buffered data down to the OS and disk.

Video 11.3 shows some more details of what happens when we make the call to fclose at the end of the previous video example. Here, we show the data movement to the OS kernel as the C library makes the underlying write system call before closing the file. Then we see how the OS then writes the data to the underlying hardware, (e.g., hard disk drive) when the file is closed. Note that any of these pieces may write the data out sooner but are not (typically) required to. We also note that the representation of the kernel structures and the interactions of the kernel with the disk drive are shown in high level abstractions—and are actually quite complex, but we are not concerned with those details here. 11.4 Other Interactions Sometimes programs interact with the rest of the system or outside world in ways other than reading from/writing to files. UNIX tries to make as many of these access types as are reasonable appear to be similar to accessing files—presenting the same interface, and thus allowing the use of familiar functions to perform these operations. For operations conforming to this model, the underlying system call to initiate access returns a file descriptor, which is then passed to other appropriate system calls (such as read or write). If the user wants to use the IO functions from stdio (fprintf, fgets, fgetc,…), she can use the fdopen library call to get a FILE * corresponding to the file descriptor. One example of an interaction that “looks like a file” is reading input from the user and printing it to the terminal. You have already printed things to the terminal with printf, which prints the output to stdout, a FILE * that is connected to “standard output.” By default, standard output is the terminal; however, as you learned in Appendix B, you can redirect the output so that it goes to an actual file instead. You can also use fprintf to print to stderr, which is another FILE * that also goes to the terminal by default. While stdout and stderr both print to the terminal by default, they serve different purposes: one is for output and the other is for errors.11 You can also read from the terminal to get input from a user by reading from stdin. Each of these FILE *s is declared in stdio.h. They are all open when your program starts (the C library opens them before main), and they correspond to file descriptors 0 (stdin), 1 (stdout), and 2 (stderr). You should not ever close these FILE *s, as the C library is responsible for them, not your code.

Another example of an interaction that “looks like a file” is transferring data across the network. The program obtains a file descriptor for a socket—the logical abstraction over which data is transferred—via the socket system call. Depending on the network protocol the program desires, additional setup may then be required to specify the destination, establish the connection, etc. However, once the socket is set up, data can be sent across the socket by using the write system call or read from the network by using the read system call (which, if no data has been received, will block— cause the program to wait—until data arrives). Of course, if the fdopen system call has been used to set up a FILE *, then library functions like fprintf or fgets can be used (which make write and read system calls on the underlying file descriptor). Another form of interaction that looks like a file is a pipe. The name “pipe” may sound familiar from the similarly named shell construct (as in cmd1 | cmd2 at the shell), which uses this type of communication. A pipe is a one-way communication channel between two processes. One process writes data into one “end” of the pipe, and the other process reads from the pipe, obtaining the data that was written in by the first process (or blocking if no data is available). This communication looks exactly like reading/writing a file to each process (as they again, read/write the file descriptors, or use library functions that do so). The shell uses this when you use the pipe operator, as it sets up a pipe, and arranges for the standard output file descriptor of the first process to be the writing end of the pipe and the standard input file descriptor for the second process to be the reading end of the pipe. Another way that UNIX provides access to things that are not traditional files in a way that looks like files is through device special files. These appear as files in the file system (you can see them with ls, for example) but have a special file type indicating that the OS should not attempt to read/write data from/to the disk (or other media), but should instead perform special functionality. These files are typically found in the /dev directory. For example, on Linux, the “file” /dev/random provides access to the secure pseudorandom number generator provided by the kernel. You can open this file for reading with fopen (or open) and read from it with whatever method you prefer. However, when you perform a read on this file, the kernel recognizes that it should perform a random number generation routine to supply the data,

rather than reading the disk. The kernel will generate random numbers according to its algorithms and return that as the data read by the system call. The read operation may block if the kernel’s entropy model indicates it needs more entropy to generate numbers securely.12 The /dev/urandom device can be used instead to generate numbers with the same algorithm but without regard to if there is sufficient entropy available for security-sensitive purposes. There are, however, things that do not fit into the “everything is a file” model. These are typically handled by system calls, but may not involve file descriptors. For example, if you need your program to determine the current time, you can use the gettimeofday system call, which just returns the time of day. There are also system calls to create a new processes (fork), replace the currently running program with another (execve), exit the current program (exit is the library call typically used for this purpose, _exit provides access to the underlying system call, which is rarely needed), and many more things. In fact, there are a few hundred system calls. As you gain experience programming, they will become more familiar to you. One other form of interaction is when the OS needs to inform the program of something asynchronously—not at a time that the program explicitly asks for it, but rather at any time during its execution. Here, unlike with a system call, the OS is initiating the communication with the program. UNIX-style OSes support many signals (each has a number and a symbolic name, indicating what it represents). Most signals are fatal to the program by default—if the OS needs to deliver a fatal signal to the program, it will kill the program in question. We have already seen an example of one fatal signal— although we have not discussed it as a signal. When your program segfaults (which happens when your program accesses memory in certain invalid ways), the OS sends it SIGSEGV, which kills the program. Some other signals have a default action of being ignored, in which case nothing happens if the OS delivers that signal. Programs can change what happens for each particular signal (except for signal 9, which is SIGKILL, which is always fatal). One option for the new behavior of the signal is to have the OS cause the program to run a particular function (the program specifies which function when it makes the system call asking the OS to modify its behavior for that signal). We are not going to go into the

details of signals, signal handling, and related topics here, but you should at least know they exist and anticipate learning about them in the future. We will note that setting your program to just ignore SIGSEGV because you cannot get it to work (and it keeps segfaulting) is a Bad Idea—remember you never want to hide an error—you always want to fix it. 11.5 Practice Exercises Selected questions have links to answers in the back of the book. • Question 11.1 : Write a program called myEcho, which prints all of its command line arguments, each separated by a space. After all of these, it should print a newline. That is, your program is essentially a simplified version of the echo program. • Question 11.2 : Expand on your myEcho program by making it accept the optional -n and/or -e options that the real echo program accepts. If your program is given the -n option, it should not print the trailing newline character after printing its arguments. If your program is given the -e option, it should interpret backslashed escape sequences, as described in the echo man page. • Question 11.3 : Write a program called myCat, which treats each of its command line arguments as an input file name, reads the input files in the order they appear, and prints them all to standard output. If no command line arguments are specified, myCat should read standard input and print it to standard output. This program effectively behaves like a simplified version of the cat program. • Question 11.4 : Expand on your myCat program so that it accepts the -n option, causing it to number the output lines. • Question 11.5 : Write the program myCp, which takes two command line arguments and copies the file named by the first to the second file name. Note that this is effectively a simple version of the cp program. • Question 11.6 : Expand your myCp program to allow an arbitrary number of arguments, as long as the last one names an existing directory, in which case, all but the last argument name files to copy into the directory (named by the last argument).

Consult man -S2 stat for information about how to determine if a file is a directory or not. • Question 11.7 : Expand your myCp program further to accept the -r option, which causes it to recursively copy the contents of a directory. That is, if one of the source files is a directory, it will copy the directory, and all of its contents—if some of that contents is also a directory, it will copy that recursively as well. Consult man opendir to see how to find out what is in a directory. Note that there will always be entries for “.” and “..”, which you need to treat specially. • Question 11.8 : Write a program called fileSum, which takes 0 or 1 command line arguments. If 0 arguments are specified, this program reads from stdin. If one command line argument is specified, it reads from the file named on the command line. This program then reads lines of input, each of which should contain an integer number, and sums them. At end of input, your program should print the resulting sum. If the input contains anything that is not a valid number, your program should print an error message to stderr, then exit. • Question 11.9 : Write a function that reads a text file which is an “image” of a chess board (i.e., the output of your code in Question 10.5) and prints out the position information for the corresponding FEN string. The file should have exactly eight lines of text, each of which should have exactly nine characters (eight “board symbols” and one newline). If the file does not match this format, you should print an error and exit. 10 Uses of Pointers12 Dynamic Allocation Generated on Thu Jun 27 15:08:37 2019 by L T XML

I Introduction to Programming in C11 Interacting with the User and System13 Programming in the Large

Chapter 12 Dynamic Allocation Recall from Section 9.5.3 the task of writing a function that takes an integer, creates an array of the size specified by the integer, initializes each field, and returns the array back to the caller. Given the tools we had thus far, our code (which did not work!) looked like this: 1 //broken code: do not do 2 int * initArray(int howLarge) { 3 int myArray[howLarge]; 4 for (int i = 0; i < howLarge; i++) { 5 myArray[i] = i; 6} 7 return myArray; 8} The reason this code will not work is that the array is created on the stack. Variables on the stack exist only until the function ends, at which point, the stack frame essentially disappears.1 While it may not seem that important from this example to be able to create an array and return it, programmers often want to write functions that perform more complex creation tasks (and have the results persist beyond the function that created them). Suppose you needed to read information from a file (possibly with a complex format). You might want to write a function to read the information, allocate memory to hold the results in some combination of arrays and structs, and return the result to the caller. Fortunately, there is a way to do exactly this: dynamic memory allocation.

Figure 12.1: Highlighting the heap: where dynamic memory is allocated in program memory. Dynamic memory allocation allows a programmer to request a specific amount memory to be allocated on the heap (highlighted in purple in Figure 12.1)—not the stack. Because the memory is not in the stack frame, it is not freed when the function returns. Instead, the programmer must explicitly free the memory when she is done using it. When looking at Figure 12.1, notice how the heap has an arrow indicating that it grows (in fact, it grows upwards, while the stack grows downwards). Unlike the code and static data segment, the heap changes sizes as the program runs—thus the term “dynamic memory allocation.” The memory allocation library manages the free memory in the heap, and when an allocation request cannot be satisfied from the existing free blocks of memory, the allocation library requests (by making a system call) that the upper boundary of the heap be increased—causing the heap to grow. The allocation library can then use the newly allocated region of the heap to satisfy the allocation request. As we alluded to, dynamic memory allocation involves both allocating memory (with the malloc function— discussed in Section 12.1) and freeing that memory when

you no longer need it (with the free function—discussed in Section 12.2). Programmers may also wish to reallocate a block of memory at a different size (for example, you may think an array of eight elements is sufficient then read some input and find that you need 16). The realloc function (the topic of Section 12.3) allows a programmer to do exactly this—asking the standard library to allocate a new (larger or smaller) block of memory, copy the contents of the original to the new one, and free the old one (although the library may optimize this procedure if it can expand the block in place). For all three of these functions, #include <stdlib.h>. We will also see a wonderful function, getline, for reading strings of arbitrary length using dynamic allocation. 12.1 malloc Figure 12.2: The signature of malloc. The most basic function for dynamic memory allocation is called malloc (which performs memory allocation). Calling this function is how you allocate memory dynamically. The malloc function, shown in Figure 12.2, takes one argument telling it how much memory is needed, and it returns a pointer to that allocated memory in the form of a void *. Many beginning programmers are intimidated by the concept of a void *, but you should not be! Recall that a void * just means a pointer, but we do not know what type of thing it points to. If malloc instead returned something more specific (for example, an int *), we would need a new version of malloc for every data type. This would be both unwieldy and (in the context of user-defined

data types) impossible. Just remember that you can assign a void * to any other pointer type—so just assign the return result of malloc to whatever pointer you want to initialize. 12.1.1 How Many Bytes? malloc requires that you tell it how much memory you need in bytes—but how do you know how many bytes something is? You may think you know that an int is four bytes (or eight bytes, or whatever) and that a particular struct you just wrote is 100 bytes—but writing a specific number of bytes is incorrect in almost all cases (it is never correct for anything you will do in this book). There are two reasons why writing a specific number of bytes is never correct. The first is portability—the ability to compile your code on a different system and still have it work correctly. Even if you are absolutely sure that an int is four bytes on your computer (with the particular compiler you are using), you may want to compile and run your code on a different computer (or with a different compiler) where an int may be a different number of bytes. The second reason is maintainability—the ease with which you can make changes to your code and still have it work correctly. Even if your struct is 100 bytes now, what happens if you add a field to it, and now it is 104 bytes? You would have to go find and change every place in the code where you assumed the size is 100 bytes. Instead, you should let the C compiler calculate the size of the type for you with the sizeof operator. Recall from Section 9.6, that the sizeof operator takes one operand (either a type or an expression) and evaluates (at compile time) to the number of bytes that type (or the type of that expression) requires. If you want to malloc space of an int, you could do malloc(sizeof(int)). If you want to allocate an array of things, you can determine the size of the entire array by multiplying the number of elements you

need by the size of each element. So, for example, to allocate enough memory for six integers, you could call malloc(6 * sizeof(int)). Sometimes, novice programmers (even after having been warned that they should use sizeof), think “I know that integers are four bytes, and I don’t ever need to run this on any other machine… I bet if I simplify that to int *myArray = malloc(24) my code will be faster, since it won’t be computing sizeof nor multiplying…” This line of reasoning is flawed in two ways. First, you should never sacrifice correctness in an attempt to improve speed. Second, no performance improvement is actually made by this “simplification.” The sizeof operator is evaluated at compile time, not run-time, and any decent compiler will, as part of its optimization process, evaluate arithmetic expressions that have constant operands. You should write correct code and let the compiler make it fast2 However, we can do even better in terms of writing good code—specifically, more maintainable code. The very best way to call malloc would be int * myArray = malloc(6 * sizeof(*myArray)). This way, if someone decides later that the array should actually be of type char or double, the call to malloc would continue to be correct with no additional changes—the compiler will evaluate the type of *myArray as part of evaluating the sizeof expression and come up with the right type, and thus right size for the array elements. 12.1.2 Video Example Video 12.1: Stepping through a simple call to malloc. A simple example of how to call malloc is shown in Video 12.1. Notice how the memory allocated by malloc is outside of the stack—it does not belong to any frame.

12.1.3 Failure It is possible that the heap could run out of space and there is not enough memory to fulfill the current request. In such cases, malloc will return NULL instead of a valid pointer to a location on the heap. As such, it is a good idea to check the value returned by malloc and make sure it is not NULL before trying to use the pointer. If the value is NULL, the program should gracefully abort with an error message explaining that a call to malloc failed (or if it can recover from the situation and continue—that is even better). This is preferable to the alternative: a mysterious segmentation fault. 12.1.4 Fixing initArray With malloc at our disposal, we are finally able to correctly implement the task introduced at the beginning of this chapter: 1 // this code does work! 2 int * initArray(int howLarge) { 3 int * array = malloc(howLarge * sizeof(*a 4 if (array != NULL) { 5 for (int i = 0; i < howLarge; i++) { 6 array[i] = i; 7} 8} 9 return array; 10 } Note that in this function, if malloc fails (i.e., returns NULL), then the function returns NULL—this pushes the task of handling the error up to whoever called this function. Whenever you write a function where you would not know how the error should be handled, making the caller handle the error is a good strategy.

12.1.5 mallocing More Complex Structures Even though our examples so far have shown mallocing arrays of ints, we can, of course, malloc any type we want. We can malloc one of a thing if we need (rather than an array) or any number of things (as memory permits). We can form complex data structures in the heap by mallocing structs that have pointers, and then setting those to point at other locations in the heap (which themselves point at blocks of memory allocated by malloc). We state this explicitly because it is important; however, you could also realize that all of this is possible due to the principle of composability (recall from Section 4.5.1)—we can put all these different pieces together to make larger things. For example, we might write 1 struct point_tag { 2 int x; 3 int y; 4 }; 5 typedef struct point_tag point_t; 6 struct polygon_tag { 7 size_t num_points; 8 point_t * points; 9 }; 10 typedef struct polygon_tag polygon_t; 11 12 polygon_t * makeRectangle(point_t c1, point 13 polygon_t * answer = malloc(sizeof(*answe 14 answer->num_points = 4; 15 answer->points = malloc(answer->num_point 16 answer->points[0] = c1; 17 answer->points[1].x = c1.x; 18 answer->points[1].y = c2.y; 19 answer->points[2] = c2; 20 answer->points[3].x = c2.x; 21 answer->points[3].y = c1.y; 22 return answer; 23 } Here, we have a function that mallocs space for a polygon (one struct), which itself has a pointer to an array

of points. This particular function makes a rectangle, so it mallocs space for four points and fills them in before returning its answer to the caller. 12.1.6 Shallow vs. Deep Copying Suppose we had a polygon_t * p1 pointing at a polygon we created (e.g., by calling makeRectangle), and we wanted to make a copy of the polygon it points to. If we just wrote the following, we would only copy the pointer—we would not actually copy the object it points to: 1 polygon_t * p2 = p1; //just copy pointer Figure 12.3: Copying only a pointer. Figure 12.3 illustrates the (hopefully now familiar) effects of this statement. After assigning the pointer p1 to the pointer p2, both point at the exact same memory location. The only new box that was created was the box for the pointer p2, and if we change anything about the polygon through one pointer, we will see the change if we examine the values through the other pointer—since they point at the same values. If we were to use malloc, we could create a copy. For example, we might write: 1 polygon_t * p2 = malloc(sizeof(*p2)); 2 *p2 = *p1;

Figure 12.4: A shallow copy. Figure 12.4 illustrates the effects of this piece of code. Now, we have two polygons, but only one array of points. We have created a shallow copy of the polygon—we have made a copy of the polygon, by exactly copying the fields inside of it. Each pointer in the shallow copy points at exactly the same location in memory as the corresponding pointer in the original. In some cases, a shallow copy may be what we want. However, if we did p1- >points[0].x = 42;, we would change the x of p2’s zeroth point, since p1->points points at the same memory as p2- >points. Notice that we must also be careful when freeing an object that has had a shallow copy made of it—we need to take care to only free the array of points when we are done with both shallow copies. As they share the memory, if we free the points array when we are done with one then try to use the other copy, it will have a dangling pointer. If we want two completely distinct polygon objects, we want to make a deep copy—in which we do not just copy pointers, but instead allocate new memory for and make deep copies of whatever the pointers point to. To make a deep copy of our polygon_t, we would write: 1 polygon_t * p2 = malloc(sizeof(*p2)); 2 p2->num_points = p1->num_points; 3 p2->points = malloc(p2->num_points * sizeof(*p2->po 4 for (size_t i = 0; i < p2->num_points; i++) { 5 p2->points[i] = p1->points[i]; 6}

Figure 12.5: A deep copy. Figure 12.5 illustrates the effects of the deep copy from this fragment of code (which again, should not be surprising —as always, it follows the same rules you have learned). Here we have created two completely distinct polygons, which have the same values for their points but their own memory. If we change the x or y of one polygon’s points, the other remains unaffected, as they are two completely distinct data structures. Similarly, we can now completely free one polygon when we are done with it without worrying about anything else sharing its internal structures. 12.2 free Figure 12.6: The signature of free. Unlike memory allocated on the stack (which is freed as soon as the function associated with that stack frame returns), memory on the heap must be explicitly freed by the programmer. For this, the C Standard Library provides the function free. The free function, whose signature is shown in Figure 12.6, takes one argument: the starting address of the memory that needs to be freed. This starting address should match the address that was returned by

malloc. As a good rule of thumb, every block of memory allocated by malloc should be freed by a corresponding call to free somewhere later in the execution of the program. When Video 12.2: Mechanics of free(p). you free memory, the block of memory you freed is deallocated, and you may no longer use it. Any attempt to dereference pointers that point into that block of memory is an error— those pointers are dangling. Of course, as with all dangling pointers, exactly what will happen is undefined. When you execute code by hand, and you need to free memory, you should erase the block of memory that is being freed. Specifically, if the code says free(p), you should follow the arrow for p (which should reach a block of memory in the heap, or be NULL) and then erase that entire block of memory. If p is NULL, nothing happens. If p points at something other than the start of a block in the heap, it is an error and bad things will happen (your program will likely crash, but maybe something worse happens). Video 12.2 illustrates these basic mechanics. Note that in the video, p and q both point into the same block of memory (even though not at the same exact box). After free(p), q is also dangling—any attempt to dereference q would be an error. Note that free only frees the memory block you ask it to. If that memory block contains other pointers to other blocks in the heap, and you are done with that memory too, you should free those memory blocks before you free the memory block containing those pointers. In our polygon example, we would free a polygon like this (although better would be to write a freePolygon function with the two calls to free in it): 1 polygon_t * p = makeRectangle(c1, c2); 2 //stuff that uses p 3 //... 4 //done with p and its points

5 free(p->points); 6 free(p); Note that doing free(p) followed by free(p->points) would be wrong: p would be dangling at the second call, and thus we should not dereference it. 12.2.1 Memory Leaks When you lose all references to a block of memory (that is, no pointers point at it), and the memory is still allocated, you have leaked memory (or you might say your program has a memory leak). For the small programs you write in this book, a memory leak may not seem like a big deal—all of the memory allocated to your program will be released by the operating system when your program exits, so who cares if you have a few hundred bytes lying around? In small programs that run for at most a few seconds, a memory leak may not have much impact. However, in real programs, memory leaks present significant performance issues. Do you ever find that certain programs get slower and slower as they are open longer? Maybe you have a program that, if open for a day or two, you have to restart because it is annoyingly sluggish. A good guess would be that the programmers who wrote it were sloppy, and it is leaking memory. You, however, are not going to be a sloppy programmer. You are going to free all your memory. When you write a program, you should run it in Valgrind (see Section D.3—and be sure to use it!), and be sure you get the following message at the end: All heap blocks were freed -- no leaks are possible Video 12.3 shows code that allocates memory but does not free it—leaking the memory. Notice how, when p

goes out of scope, there are no more references to that block of memory, but it remains allocated. The memory cannot be reused for future allocation requests (as it has not been freed) but is not needed by the program any longer (so it should have been freed). The video concludes by fixing the code by adding a call to free. Video 12.3: Code that leaks memory and how to fix it with free. 12.2.2 A Dynamic Memory Allocation Analogy malloc and free can be confusing to novice programmers, but they are crucial to producing correct, efficient, and clean code. To help you understand them, consider the following analogy: You are at the bus depot and there are 50 lockers available for rent. To request a locker, you simply tell the worker at the window how many lockers you need. You will be given a contiguous stretch of lockers, and you will be told which is the first locker that is yours. For example, you might say “Five lockers, please,” and you might be told “Your starting locker is number 37.” At this point, you have been given lockers 37 through 41. You might also be told “No, sorry,” because there are not five contiguous lockers available for rent.3 In response to your request, the worker at the window records that five lockers are in use, starting at locker 37. When you are done using your lockers, you return to the window and tell the worker “I’m done with the lockers starting at 37.” and those five lockers now become available to someone else behind you in line. When you return your lockers, you free all or none of them. You can’t return a subset of your request. Also, you need to keep track of your starting locker (37) because that is how the worker has recorded your booking. In technical terms, you

may call free only with a pointer that was returned by malloc. Furthermore, you cannot return your lockers twice. Even if you and your partner are both using the lockers, only one of you should return them. Again, in technical speak, you may call free only once, even if there are multiple pointers to that location in memory. Freeing the same location in memory multiple times is illegal. 12.2.3 Common Problems with free Our locker analogy made references to two common errors that programmers make when using malloc and free. Trying to “free” the same lockers twice is a problem. In the case of memory allocation, trying to free the same block of memory more than one time is called double freeing. Generally, your program will crash (segfault); although, other more sinister behaviors can occur. A segfault on the line where the double free happened is nice—it makes debugging easier. However, you may get stranger symptoms, including your program crashing the next time you call malloc. In general, if malloc crashes, an earlier error in your code has corrupted its bookkeeping structures, and you have just now exposed the problem. Run your code in Valgrind, and it is quite likely to help you expose the error sooner. Another common problem, also alluded to in the locker analogy, is freeing something that is not at the start of the block returned by malloc. If the locker attendant gave you lockers 37–41, you cannot go back and say “I’m done with 38.” This may seem silly: why can’t the locker attendant just figure out that when you say you are done with 38, you mean the block from 37–41? For a human tracking lockers, this may seem like a silly rule; however, it makes much more sense for malloc and free. Neither of these functions is magical (nothing in your computer is—as you should have learned by now). They

need to do their own bookkeeping to track which parts of memory are free and which are in use, as well as how big each block that is in use is. Bookkeeping requires memory: they must store their own data structures to track the information—but where do they get the memory to track what memory is in use? The answer is that malloc actually allocates more memory than you ask for, and keeps a bit for itself, right before the start of what it gives you. You might ask for 16 bytes, and malloc gives you 32—the first 16 contain its information about the block, and the next 16 it gives you to use. When you free the block, the free function calculates the address of the metadata from the pointer you give it (e.g., subtract 16). If you give it a pointer in the middle of the block, it looks for the metadata in the wrong place. Going back to the locker analogy, this would be as if the locker attendant gives you lockers 37–41 but then puts a note in locker 36 that says “this block of lockers is five long.” When you return locker 37, he looks in locker 36 and finds the note. If you instead tried to give back locker 38, he would look in locker 37 and become very confused. A third common mistake is freeing memory that is not on the heap. If you try to free a variable that is on the stack (or global), something bad will happen—most likely, your program will crash. Video 12.4: Three common problems when using free. Video 12.4 illustrates these problems. 12.3 realloc Suppose a program initially asks for n bytes on the heap but later discovers it needs more than n bytes. In this case, it is not acceptable to simply reference past the size of the

initial malloc request. For example, if an array has four elements that are indexed via array[0] to array[3], it would not be acceptable to simply write into array[4] just because the program’s space requirements for the array have changed. In locker-speak, this is the equivalent to realizing you need a sixth locker and taking locker 42 even though it was not given to you to use. (Locker 42 might be in use by someone else, or it might be given to another person at a later time.) The proper way to respond to this increased space needs is to use realloc. Figure 12.7: The signature of realloc. realloc effectively resizes a malloced region of memory. Its signature is shown Figure 12.7. The arguments to realloc are the pointer to the region in memory that you wish to resize4 and the new size you wish the region in memory to have. If successful, realloc will return a pointer to the new, larger location in the heap that is now at your disposal. If no area in the heap of the requested size is available, realloc returns NULL. Video 12.5 steps through a simple example. Keep in mind that the new location in memory does not need to be anywhere near the original location in the heap. In terms of our locker analogy, if you return to the window and say “I have the lockers starting at locker 37, but I need six lockers now,” the worker may not be able to give you locker 42. Instead the worker may respond “Okay, your new starting locker is 12.” Conveniently, the worker will move the contents of lockers 37–41 into lockers 12–16 for you.