Lab 3: Dynamic Memory Allocation

stack and heap, malloc() and free(), representing images

Goals

After this lab you will be able to

1. State the difference between heap and stack memory allocation.
2. For any variable declaration, determine whether it will be allocated on the stack or the heap and why.
3. Use malloc() and free() to manage heap memory
4. Used sized integer types.
5. interpret integer arrays as images and operate on them.
6. write loops over arrays in your sleep.

Requirements

Guide

Raster Images

In computer graphics, images are usually represented as arrays of pixels (picture elements). Each pixel describes the color of a single point in the image. For grey-level images - regular people call them "black and white" images - a range of 256 shades of grey, smoothly varying from 0=black to 255=white is enough to produce good-looking results.

We can conveniently and compactly represent a grey-level image as a one-dimensional array of unsigned chars of size (image_width * image_height). To interpret the array as a two dimensional image, we assume that each row of pixels is stored consecutively in the array. By convention, image coordinates have the origin in the top left, and y values increase downwards. We map image coordinates (x,y) to array indices thus:

 index = x + y * image_width

The pixel indices of an image of width=5, height=4 are therefore:

A corresponding array declaration could be:

unsigned int width = 5;
unsigned int height = 4;
unsigned char img[ width * height ];

or, using the manual memory allocation described in detail below:

unsigned int width = 5;
unsigned int height = 4;
unsigned char* img = malloc( width * height * sizeof(unsigned char) );

Images represented this way are known as raster images, from the latin rastrum (a rake) from the days when images were drawn on the screen of a CRT monitor by steering an electron beam in the same line-by-line pattern. They are also called bitmaps from the days when each pixel was only a single bit representing black and white.

For speed, C does not initialize the values of array elements for you. If you want an all-black image, you must set the pixels to zero:

for( int i=0; i<width*height; i++ )
  img[i] = 0;	      

It can be faster to set all the pixels at once using the standard library function memset() instead:

  memset( img, 0, width * height * sizeof(img[0]) );

See the memset() manpage for details.

Standard fixed-size integer types

Since the sizeof(int) varies with machine architecture, it is often useful to specify the size of your integer variables exactly. Then your code will use predictable variable sizes no matter which machine you run it on. The header file stdint.h defines a set of sized integer variable types for you, including:

 int32_t   (32 bit signed int)
uint32_t   (32 bit unsigned int)
 int64_t   (64 bit signed int)
uint64_t   (64 bit unsigned int)
  int8_t   (8 bit signed int)
 uint8_t   (8 bit unsigned int)

In this lab we will use uint8_t in place of its exact equivalent unsigned char for brevity. (It is C convention that the suffix _t denotes a type. More on types next week.)

Reminder/primer: Computer architecture memory layout

The memory layout for a process varies a bit by CPU architecture and OS, but the scheme used by Linux on X86 is pretty typical, and shown below. The program's text (compiled code) and static data exist in low memory, the function call stack in high memory, growing downwards, and the "heap" storage space in between. Ignore the "memory mapping segment" for now.

[Image reproduced from an excellent online description of the memory layout of Linux by Gustavo Duarte]

Storage for "automatic" variables

In C terminology, a function's local variables are called "automatic variables" because the storage for them is allocated automatically when the function is called. Similarly, when the function returns, all that storage is automatically freed. C implements this very efficiently by allocating all the space for local variables in the stack frame for the function. When the function returns, the stack pointer returns to its previous value, thus "freeing" all the local variables at small and near-constant cost.

Consider this code, that contains a common and nasty C bug:

#include <stdio.h>
 
char* get_name( void )
{
  printf( "Please enter your name: " );
 
  // should be enough space for a name
  char line[1024];
  
  // reads at most 1023 chars from stdin, up to first newline, 
  // EOF or error.
  if( fgets( line, 1024, stdin ) == 0 ) // we ALWAYS check for I/O errors
  {
    perror( "failed to read a name" );
    exit(1) 
  }
  
  return line; 
}	
 
int main( void )
{
  char* name = get_name();
 
  printf( "Your name is %s\n", name );
 
  return 0;
}	       

The image below shows a sketch of the function call stack for a run of this program up to and including line 23. When the program begins (1), the frame for main() is on the stack, and its local variables use stack memory for storage. The "stack pointer" keeps track of the current "top" of the stack (growing downwards).

When get_name() returns (2)--(3), the stack pointer is simply replaced to the end of calling function main()'s stack frame. The space used by get_name() will be reused by the next function call.

This mechanism explains:

1. why you must declare all your variables in C: the compiler has to decide how large a function's stack frame needs to be before the function runs;
2. another reason why C programs can be very fast: memory allocation, and particularly deallocation, are very cheap for automatic variables.

Do not return a pointer to an address in your stack frame!

The problem is the pointer returned by get_name() points to data inside that function's stack frame. When the function returns, that pointer is no longer valid. This sketch illustrates what happens:

At (2) the return value of get_name() is determined to be the address of the line character string. At (3) main()'s name variable is set to the return value of get_name() and that function's stack frame is popped from the stack and thus forgotten. At (4) name points into the forgotten stack frame. This is a nasty bug, since the correct data might still be there! At (5) the function call to printf() was entitled to overwrite the old data. There's a good chance that name now points to garbage.

This kind of bug is one of the main reasons people complain about C. The code looks like it should work: the intent is clear; it compiles; it might even work in testing. Yet details of the implementation mean that the code is fatally bugged. This is undoubtedly a bad thing. The fact that it may work in testing is particularly awful.

The good news is that modern compilers will generate a helpful warning if you return a pointer to memory allocated for an automatic variable. Read your warnings. Better still, always use -Wall and fix all warnings in your builds, every time.

$ gcc -Wall get_name.c

First Solution: Allocate in caller

There are two different approaches to fixing this problem. The simpler and faster solution - and thus the best one when you can use it - is to have the calling function allocate the array and pass in a pointer to it, like so:

#include <stdio.h>
#include <stdlib.h>
 
void get_name( char line[], int maxlen )
{
  printf( "Please enter your name: " );
 
  // reads at most maxlen-1 chars from stdin, up to first newline, 
  // EOF or error.
  if( fgets( line, maxlen, stdin ) == 0 ) // we ALWAYS check for I/O errors
  {
    perror( "failed to read a name" );
    exit(1);
  }
}	
 
void stuff()
{
  // store some random values in my stack frame
  int stuff[1000];
  
  for( int i=0; i<1000; i++ )
    stuff[i] = rand();
}
 
int main( void )
{
  char name[1024];
  get_name( name, 1024 );
 
  // we don't need to be lucky this time
  printf( "Your name is %s", name );
 
  stuff();
 
  // we still don't need to be lucky
  printf( "Your name is %s", name );
 
  return 0;
}	       

This time get_name() receives a pointer to array name which is stored inside main()'s stack frame. Since this is guaranteed to exist longer than the call to get_name() this will work correctly.

$ gcc -Wall get_name_parent.c

Second solution: Explicit memory allocation

The above method requires you to know how large an array your function call will need at most, and to allocate that much memory in advance. It is quite possible that you just don't know how much data to expect. Also, if the amount of data you expect is usually very small, but could be very large, it would be wasteful to always allocate a huge array just in case.

In these cases, we must allocate memory explicitly, using the system call malloc(). This allocates memory on the heap, and returns a pointer to it. The allocation will persist until explicitly de-allocated by a call to free(). Because the allocation is on the heap, it is available to any function that has knows its address, regardless of the current state of the stack.

Here is a simple example, omitting error checking for clarity:

// choose a random array length
int len = rand();

// allocate memory for an array of len ints
int* array = malloc( len * sizeof(int) );

// array is now a pointer to an array of len integers on the heap
// OR zero (null pointer) if the allocation failed

// ...
// (use the array)
// ...

// I am defintely finished with the array
free( array );

// make sure to cause a segfault if I use 
// it again by mistake
array = 0; 

The argument to malloc() is a size in bytes, so we almost always use sizeof(some_type) as a multiplier. It returns a special type: a void* (pronounced "void pointer"). By default C allows a void pointer to be assigned to any other kind of pointer without having to be converted explicity. All pointers are just memory addresses, after all.

$ gcc -Wall randomrandom.c

Limited stack size

Once again, it is a downside of C that you must think about things like this. As usual, it's the price you pay for speed and control.

How large is too large for the stack?

The answer is system-dependent, but anything over a few KB should probaly go on the heap.

Say that again?