Pointers and Memory Allocation

Goals

This laboratory exercise provides practice with basic elements of pointers, addresses, values, and memory allocation in C.

Part A: Printing Memory Addresses

Write a short C program that declares and initializes (to any value you like) a double, an int, and a string. Your program should then print the address of, and value stored in, each of the variables.
1. Use the format string "%lu" to print the addresses as long unsigned integers.
  
  To avoid compiler warnings, you will need to expicitly cast the address values used as arguments to printf as unsigned long
  
  Reminders:
  - You can use the & character to find addresses
  - 1 byte = 8 bits, and a 32-bit integer requires the space of 4 bytes.
2. Draw a small memory diagram showing the location of each of the variables in your program. Are they allocated in the same order that you declared them? Is there any empty space between them?
3. Modify your program by rearranging the variable declarations and/or changing the length of the string. (In particular, try a string that uses 5 or 7 bytes, including the null terminator.) Does this change the results you got previously?

The take-home message:

Small changes within a program can change how memory is laid out for a given program. The compiler will try to arrange memory for optimal performance, and this may include aligning variables with 4-byte boundaries. For C programmers, this can sometimes mean that a program which appears to work correctly (but in fact overwrites the end of an array), can suddenly stop working due to seemingly innocuous changes—for example, changing the order in which variables are declared.

Part B: Writing a Swap Function

Consider the following code segment that swaps the values of two variables x and y.

/* declare and initialize variables x and y */
double x = 5.5;
double y = 7.7;

/* swap values for x and y using a temporary intermediate */
double temp = x;
x = y;
y = temp;

Include the above code segment in a program as follows.
1. Check that the given code does indeed swap the values of x and y, and describe how it works; what is the purpose of the variable temp?
2. Explain what is wrong with the following alternative code segment
```
/* declare and initialize variables x and y */
double x = 5.5;
double y = 7.7;

/* WRONG --- but why to swap values for x and y */
x = y;
y = x;
```
Separate the code for swapping x and y into a swap function. The function should have two parameters of type double.
1. Will the parameters have to pass values by value or by reference? Why will one approach work, while the other approach will not?
2. Complete the code for the function swap.
3. Write a driver function (i.e., main) to test your swap routine to be sure it works.

Part C: Arrays Names are Pointers Too

Review the program max-min.c from Step 6 of the lab on arrays. In that lab, you wrote a function find_stats that computed the maximum, minimum, and average of the values in an array.
1. In a few sentences, explain how the function works and how it is called.
  
  Remember: The name of an array is simply a pointer to the first element of the array.
2. Expand the main program, so that it calls the same function with several arrays, printing the results each time. (That is, the function has one array parameter, but it is called in the main program several times with arrays of different names.)

Part D: Allocating and Freeing Memory

When arrays were first discussed, an early application was to use the Scribbler 2 to take 3 pictures and then display those pictures in the order they were taken. Program scribbler-movie.c expands the former program slightly to take n pictures, display them in order, and then display them in reverse order.

Copy and run scribbler-movie.c, and then review how the program works.

Program scribbler-movie.c takes advantage of a "Variable-Length Array (VLA)" option within 1999 Standard C. The size of an array is a variable (numPics), and a value is assigned to this variable before space for the array is allocated. This technique allows the user to specify the size of an array at run time; but once the array is declared, its size cannot be changed.

In this problem, we explore an alternative strategy using dynamic memory allocation.
1. Within scribbler-movie.c, replace the declaration
```
  Picture pics[numPics];
```
  with the lines
```
  Picture* pics;
  pics = malloc (numPics * sizeof (Picture));
```
  Notes:
  - In this revised declaration, pics is a pointer to an array of pictures. That is, pics identifies the location of an array where each element has type Picture.
  - In the first line above, pics only indicates a location for an array. Thus the program must allocate space for the array separately, in the second line. The malloc statement asks the C library to perform this memory allocation.
  - Once declared and initialized, references to the pics array are exactly the same as in the original version.
2. Recompile and run the revised program scribbler-movie.c.
3. Draw a diagram of main memory for both the original and revised versions of scribbler-movie.c. In the diagram, show what variables are stored on the run-time stack and what information (if any) is stored elsewhere.
Modify scribbler-movie.c further to obtain scribbler-movie-10.c, so that every time the Scribbler 2 robot takes 10 pictures, it displays all of the pictures (from the first to the most recent). This version of the program should not display the pictures in reverse order.

Consider a problem where the Scribbler 2 is to take a long sequence of pictures. After each picture, the robot is to turn left slightly. When a multiple of 10 pictures has been taken, all pictures are to be displayed (from the first to the last).

This problem is similar to the revised scribbler-movie-10.c program, except that the user does not specify an initial bound on the number of pictures to be taken. Because computers have a finite-sized memory, eventually the space required for the pictures will be exhausted. However, this process could go on for some time before memory-allocation issues would be expected to arise. (In what follows, we largely will ignore this issue.)

This type of problem is not uncommon on various Web sites which display pictures of recent activities. For example, weather forecasting sites may display the radar images for a region from the past half hour, hour, or longer.

One approach to this problem utilizes an array to store pictures, just as in scribbler-movie-10.c.

The program starts with a Picture array of a specified size (e.g., space for 5 pictures).
Pictures are added to the array until it is full.
When all elements of current the array designate pictures:
- new memory is allocated for twice the space of the previous array
- pictures are copied from the old array to the new memory
- the old space is deallocated (freed)
- the pics variable is updated to refer to the new array

Modify scribbler-movie-10.c to implement this new approach for handling many pictures without an initial designation of how many pictures might be taken.

Part E: Memory Leaks and Other Problems

Consider the following program.
```
#include <stdio.h>
#include <stdlib.h>

const int FALSE = 0;
const int TRUE  = 1;

int main()
{
  int done = FALSE;
  int j=0;

  while (!done)
    {
      int n = 100000000;
      int* a = (int*)malloc(n * sizeof(int));
      
      int i;
      for (i=0; i < n; i++)
        a[i] = i;
      
      j++;
      printf("%d\n", j);
    }
  
  return 0;
}
```
1. What is wrong with the program? What do you expect it to do when run?
2. Now copy the program and run it. On my machine, it prints numbers up to around 30 before it crashes. How about yours? Do you understand why it crashes?
3. Add the following code immediately after the malloc call to confirm your understanding.
```
if (a==NULL)
  {
    perror("Error allocating memory");
    exit(EXIT_FAILURE);
  }
```
  The library function perror(), declared in stdio.h, prints a message regarding the most recent error that occurred in any system or C library call. Thus, with this placement, perror will print any error that may occur related to malloc. (We will discuss system calls later in the course.)
  If you still are not sure why the error occurred, please ask.

For interested readers who have time

In the next few exercises, you will experiment with a (non-GNU) Linux tool named Valgrind that can detect and report on several types of errors related to dynamic memory management. Actually, Valgrind is a suite of debugging tools; the specific Valgrind tool we will use is called Memcheck. According to the documentation at http://valgrind.org, Valgrind is pronounced with a short i (like grinned), and the origins of the name are related to Norse mythology.

Valgrind is a "virtual machine", which means that you will run Valgrind, and it will invoke your executable code line by line. This allows it to monitor your use of memory and report related errors. It also adds a lot of overhead, so you may notice that it runs slowly.

Modify your program from the previous exercise so that it allocates (and fails to free) only ten arrays or so.
Run your program with Valgrind, using a command like the following. (For future reference, if your program takes command-line arguments, you can simply add these to the end of the command line.)
```
valgrind --leak-check=yes ./myprog
```
Your output will include some header information about Valgrind, then the output of your program, and then some diagnostic information about the memory leak.

Do not be misled by the line that says
```
"ERROR SUMMARY: 0 errors from 0 contexts"
```
This apparently relates to specific error types. Continue reading, and you should see
```
"malloc/free: 10 allocs, 0 frees"
```
and also the following.
```
==22813== LEAK SUMMARY:
==22813==    definitely lost: 0 bytes in 0 blocks.
==22813==      possibly lost: 400,000,000 bytes in 10 blocks.
```
Modify your code from the previous exercise to free the memory you have allocated. Note that you will need a call to free in each loop iteration, so that you can free the memory before you lose the pointer to it!

Now rebuild your code, and run it with Valgrind to see the improved output message.
In this exercise, you will experiment with a few more memory-related errors Valgrind can catch.
1. Add an extra call to free() somewhere in your program. Then rebuild your program and take a look Valgrind's output. (After you have done so, remove the offending call again.)
2. Another common error that Valgrind can catch is accessing memory after it has been freed. To test this, you can add statements such as the following immediately after your call to free(). Go ahead and try it, noting that Valgrind tells you the line numbers where the errors occur, and then remove the offending code.
```
a[0] = 5;
printf("a[0]=%d\n", a[0]);
```
3. Valgrind can also tell you when you access elements that are out-of-bounds of an allocated memory block. Modify your program to test this, noting what information Valgrind gives you about the error. (Then remove the error afterwards.)
  
  Unfortunately, Valgrind can not detect out-of-bounds errors with statically allocated arrays. It can only do this for dynamically-allocated memory.
Look at the on-line documentation for Valgrind: http://valgrind.org. In particular, I suggest reading quickly through the "Quick Start" information, and also Sections 4.1 and 4.3 in the "User Manual".